I've got a great job offer for you. You can even choose the salary plan. You can get a £100 on the first day and each day you work, you get £50 pounds more than the day before. Or a different plan. I double your salary every day but you start on £1 on day one. The question is, how long do you want to work for us and what payment plan do you want? Is too good to be true? Okay. It's just a story I know, but we can still look at the figures. Have you made a decision? How do we actually site? You could get your spreadsheet out and try it. I'll get mine. Let's put in all the data from these payment plans. So, I've got a column here for the days of work and the first payment plan and the second payment plan. So, first payment plan, we start with a £100 on day one, and on the second day, is the payments we had on the previous day with extra £50 on top. So that means, we get a 150 on day two, 200 on day three, 250 on day four and so on, so we get all of that. Let's see how many days we need, but will put 28 for now. Now, on the second option, you start on £1, so we start on £1. On the second day, we go with doubling what we earned on the previous day, and we carry on in that fashion, so we're going to double. Now, is that a good table to help us make a decision? Let's see. We're earning really low amount on the second payment plan, we go £1, £2, £4 day eight, we are in a £128. Not bad and it keeps doubling so we're just making really serious money on day 10, and it looks like we're catching up with the £550 we get on a first payment plan. Now, so, how many days should I work? On day 11, I'm already earning more on the second plan than on the first. Is that how I should make my decision? Yeah, I can hear you screaming there. It's not enough just to compare that, we need to say how much money do you make in total when we need to tally up all of this, so let's do that. We have that value and then the new one, let's add up, and we're just adding up the money you've earned up to that day, all the payments you received up to that day. So, that we are and then let's do the same on this one, and let's copy that formula. Okay, pick numbers, there we are. We have then the accumulation of salaries. Let's highlight this column here. So, we're actually comparing the sums of these, and looking at that in detail, the first day, the income of Plan B overtakes Plan A is when you earn 8,191 against 5,212. So, the day before, we're still making more money on the first payment plan but we are ahead from the 13th day onward. Why am I talking about that? We are going to pay attention to sequences of earnings and sums of earnings, but let's look at another example. I've got another story for you. The inventor of the game of chess, this was before the seventh century in India, presented the game to the emperor. Now, having enjoyed the new game, the emperor praised the inventor and offered a generous reward: whatever you want. She asked for one grain of rice for the first square of the board, two for the second square, four grains of rice for the third square, eight for the next and so on. The emperor approved the payment, probably dismissing it as a humble request from this inventor and not giving it much more thought. Well, in the end, it's just a few grains of rice for an emperor. Then treasurer in charge of the transaction later returned to the emperor informing them the reward would add up to more rice than they could ever ever, ever have grown. What is going on? You know the chessboard is eight by eight, so we have 64 squares surely adding 1 plus 2 plus 4 plus 8 all the way to two to the power of 63 grains of rice, that can't be that much, can't it? Now, if you want you can go and find out how much do we produce in the world in rice in terms of grains, but I leave you to that, and I have another problem for you. The traveling maths presenter problem. I'm taking bookings for touring with my new show, and here's my schedule for the next summer together with a travel costs. So initially, I'm going to London Manchester in Edinburgh and I need to travel between all these cities and, yeah, London to Manchester. I'm seeing the vessel a £100 fare. London to Edinburgh, a £150 fare. Manchester to London, yes, trains in Britain is a little bit more expensive, it's a £120, and Manchester to Edinburgh, a bargain £50. Edinburgh to London, a £130. Edinburgh to Manchester £50. So, there's what I'm expected spend so far now. I have to visit all the cities and come back to the starting point, of course, in the cheapest way possible, but no cities are to be repeated apart from the start and end. I do want to end up at home. We can attack the problem by trying out all the possible trips in my tour: could do London to Manchester to Edinburgh, of course, back to London. London Edinburgh Manchester back to London Manchester London Edinburgh and so on. These six trips to check and surely, we can add up the totals and calculate the cheapest trip, doesn't sound difficult. But it turns out, I just got another booking coming in. I'm going to Cardiff and here's my updated table with my costs. Now, with this extra city, the trips I'm to make to travel. I could do Cardiff, London, Manchester, Edinburgh, back to Cardiff. Cardiff, London, Edinburgh, Manchester, back to Cardiff and so on. So, I could just put a Cardiff at the beginning of all the trips I've studied before, that gives me maximum six of them. But I could go to Cardiff seconds, couldn't I? here's the list. Or I could go to Cardiff in the third place, on the fourth place, and so on. How many trips do I have now with this extra city? It turns out it's 24. So, with these cities, six trips that I can consider. With four cities we now have 24 trips. How many trips for n cities? I'm expecting a big tour. The trips to consider with one more city is the same as the trips I had with my old number of cities times the new number, so trips of n plus 1 cities is the same as n times the trips with n cities. So, trips on three cities is six. Trips in four cities is four times trips of three, which is 4 times 6 equal to 24. Trips with five cities is five times of trips of four which we have just done: it's five times 24 which is a 120. So, I can expand this as the trips for n cities as n times n minus 1 times n minus 2 times a smaller as well number times 3 times 2. We could analyze the costs of all these trips, couldn't we? But how long does it take to do that job to cost and analyze all these possibilities as the number of cities increases. Yes. As I get more and more bookings, this approach to finding the cheapest store becomes unmanageable. I hear you cry. Surely, we can use computers. The number of options to look at grows fairly fast as we increase the number of cities to visit. So fast that this brute force approach of checking every option is not okay, not even with computers. In the case of the traveling maths present a problem, also known in the literature as the Traveling Salesperson Problem, there is no known algorithm to give the optimal solution. Yes, this is why in a computing degree, you study problem solving math, algorithms, complexity, and get to learn why some algorithms just do not accomplish the task within our lifetime. Not even with all computers in the world linked up working on the same task. We touched on this before when we talked about factorizing large numbers and deciding of a number being prime. In this topic, we will be looking at some tools for understanding sequences of numbers, like the ones we saw earlier, their growth and summation. We will not cover all possibilities but we will introduce key tools that will allow you to make sense of the behavior of sequences.
