Solution o'clock! Hopefully you have all solved out the balls in boxes problem from last time. Given that you probably have, writing a solution is a totally pointless act, done simply to amuse myself. Here we go.
First of all, lets find some N for which we cannot always win. Specifically, consider that N=1 and there are 1000 balls. Box 999 might have 500 of them and box 1000 has the other 500 of them. In this case we have no legal moves and cannot win. What is the largest N can be so that we still might have no legal moves? To put it another way, when is N big enough to guarantee that we always have a legal move?
The most balls we can have with no legal move is 1 ball in box 2, 2 balls in box 3, 3 balls in box 4,..... k-1 balls in box k. If we have any more balls than that it will be guaranteed that we always have at least one legal move. That number of balls is 1+2+3+4+..+999 = 999*1000/2. So if N is larger than 999/2, so 500 or more, then we always have a legal move. If N is less than 500 we might have no legal moves, thus we may have started in a position with no legal moves.
Now, if N is 500 or larger, we know we always have a legal move, is this enough to guarantee that we can eventually wander our way to a solution? First note that if all the balls were in box 1, we would basically be done, we can move balls from box 1 to any target box simply by moving them 1 at a time. In fact, if we want to move balls from box i to box j, it costs us nothing to move from box i to box 1 then from box 1 to box j, so we might as well only consider moves to and from box 1.
So, assume N is 500 or larger, we have some boxes that have enough balls in them such that we can perform a move. Make all the moves you can from those boxes to box 1, such that when we are done the only legal moves we have left are from box 1. When we are done this box 1 must be nonempty, for if box 1 was empty we would have no moves, and that is impossible for N at least 500. Now, either all the balls are in box 1 or they are not, if all the balls are in box 1 we are done, we can solve the problem as mentioned earlier. If not all the balls are in box 1, there exists some k and x where box k has x balls in it, with k>1, k>x, and x>0. One can see that box 1 has at least k-x balls in it, this is apparent because if it did not I could move all the balls from box 1 into box k and leave myself with no legal moves (which is impossible). So, we can move k-x balls from box 1 into box k, bringing box k up to k balls, and we may then move all the balls from box k to box 1. We repeat this process for each nonempty box k with k>1. In the end all the balls are in box 1 and the game is trivially won.
I'm not sure why I liked this problem so much, I guess I was just pleasantly surprised to see something so simple on a Putnam. I cannot say that their questions lack creativity, but this particular problem is just the kind of creativity I like.
Balls In Boxes
New puzzle o'clock! I should probably be working instead of blogging, but blogging is so much more fun. Anyway, I found something of a neat puzzle on the Putnam 2010 exam. Usually those exams are just filled with semi-impossible math problems involving stupid functions, but there was one question on that exam I thought was pretty cool as a puzzle:
Naturally, the fundamental nature of the solution is not particularly sensitive to the number 1000, in the actual Putnam they used 2010, cause thats how they roll.
There are 1000 boxes, labelled 1 through 1000. There are 1000*N balls in the boxes, distributed randomly between the boxes. You will be playing a 1 player game, trying to average out the balls in the boxes, so that each box has exactly N balls in it.
The only legal move in the game is to select a number K and move exactly K balls from box K into any other box. So you could go to box 247 and move exactly 247 balls from that box into any other box. If box 247 has fewer than 247 balls in it, you cannot do this, so you don't get to move any of them. You are allowed to keep making legal moves as long as you like, and you win if every box has exactly N balls in it.
Given that in total there are 1000*N balls in the 1000 boxes, for what values of N is it always possible to win, regardless of the initial configuration of the balls?
Naturally, the fundamental nature of the solution is not particularly sensitive to the number 1000, in the actual Putnam they used 2010, cause thats how they roll.
Correlated Hats
Well, my thesis is essentially done, now its just time for the eternal editing of the damn thing (also, its only like 65 pages, somehow I had hoped for more). Anyway, time to post the solution the the hat problem from last time.
For the first part of the puzzle, consider that the logicians have some sort of strategy, which must be based on the hats of their fellow logicians and possibly some constant which varies for each individual logician and possibly some random variable. You get into the room ("you" being one of the logicians) and you check your strategy, and it says to say that your hat was white. OK, great, but since your strategy is independent of your own hat colour, your hat colour could randomize as we do this and your answer won't change. Thus you are 50% to be correct, no matter what. This is true for each and every logician. This means that no strategy can save more than 50% on average. In fact, no strategy can save less than 50% either. All strategies have an expectation value of saving 50 of the logicians.
You might think that is weird, since in so many other hat puzzles it has been that case that the logicians pull off something amazing with no information about their own hat colours. If you check carefully though, in all of those, when they were going to guess they were 50% chance to be correct, the most they ever pulled off was correlation with the other logicians being right.
Alright, now, is there a strategy that guarantees saving 50? Note that if the logicians knew if the total number of white hats was even, they could always guess their own hat, and similarly if they knew the total number of white hats was odd. So, the strategy is to have half of the logicians assume the total number of white hats is even, the other half assume that it is odd. Exactly one of those two groups will be right, and you will save 50 of them.
Finally, a strategy that saves all or none of them. This is simple given the last paragraph, simply have everybody assume the total number of white hats is even (or odd, if you prefer). They will either all be correct or all be wrong, with 50-50 chance.
For the first part of the puzzle, consider that the logicians have some sort of strategy, which must be based on the hats of their fellow logicians and possibly some constant which varies for each individual logician and possibly some random variable. You get into the room ("you" being one of the logicians) and you check your strategy, and it says to say that your hat was white. OK, great, but since your strategy is independent of your own hat colour, your hat colour could randomize as we do this and your answer won't change. Thus you are 50% to be correct, no matter what. This is true for each and every logician. This means that no strategy can save more than 50% on average. In fact, no strategy can save less than 50% either. All strategies have an expectation value of saving 50 of the logicians.
You might think that is weird, since in so many other hat puzzles it has been that case that the logicians pull off something amazing with no information about their own hat colours. If you check carefully though, in all of those, when they were going to guess they were 50% chance to be correct, the most they ever pulled off was correlation with the other logicians being right.
Alright, now, is there a strategy that guarantees saving 50? Note that if the logicians knew if the total number of white hats was even, they could always guess their own hat, and similarly if they knew the total number of white hats was odd. So, the strategy is to have half of the logicians assume the total number of white hats is even, the other half assume that it is odd. Exactly one of those two groups will be right, and you will save 50 of them.
Finally, a strategy that saves all or none of them. This is simple given the last paragraph, simply have everybody assume the total number of white hats is even (or odd, if you prefer). They will either all be correct or all be wrong, with 50-50 chance.
Friendly Hats
Been some time since I have done an actual hat puzzle. There was one recently on Tanya Khovanova’s Math Blog that I had assumed I had done before, since it was so basic. Interestingly enough, I have never actually done this one, so I might as well put it up now:
Thats simple enough, there are a few follow up questions that Tanya also added though:
and,
Fairly simple if you have been following all the other hat posts, most of the basic results you need to solve this out have been proven somewhere or another on this blog.
There is a room of 100 logicians wearing hats. Each hat can be either black or white, and standard hat rules apply. The logicians must simultaneously guess what colour hat they have. Every logician who guesses right is released and every one that guesses wrong is killed.
Before the hats are assigned, they logicians may get together and plan. What strategy maximizes the number of logicians you can save on average?
Thats simple enough, there are a few follow up questions that Tanya also added though:
Suppose the maximum you can save on average is N, is there a strategy that guarantees that you will save N of them?
and,
Suppose the logicians are close friends, and they do not want to see their friends die, they would rather die with them. Is there a strategy that guarantees that they will all live together or die together?
Fairly simple if you have been following all the other hat posts, most of the basic results you need to solve this out have been proven somewhere or another on this blog.
Going In Circles
Alright, some time ago I promised to do more on the dots on a line puzzle, so I guess I'll do that now.
On the puzzle page over at cut-the-knot, they had a few writeups of possible ways to arrive at the solution. They varied in their degree of rigour, but they certainly were all more elegant than my method. One in particular led me to examine a few other things about the puzzle (that I honestly do not understand the implications of), and I will go over them here.
This solution was put forward by Stuart Anderson, and it beings by assuming that the dots do not necessarily follow a uniform distribution. Suppose x is the length of an interval between adjacent points, and let f(x)dx be the probability that a particular interval has length between x and x+dx. F(x) will be the cumulative probability distribution, so F'(x)=f(x) and F(x) ranges from 0 to 1, as x ranges from 0 to 1.
We will call an interval "small" if it is smaller than both its neighbours, "large" if it is larger than both its neighbours, and "medium" otherwise. Intervals that are small get painted twice, and medium ones get painted once, while large ones are unpainted. Lets try to find out how many of each region we have and how large each type is. Suppose we have an interval with size x, that occurs with chance f(x)dx, and its left hand neighbour will be smaller than it with chance F(x) (F(x) being the cumulative distribution function, it is the integral of f(y) from 0 to x). Similarly, the right hand neighbour will be smaller with chance F(x), so the total chance that we have a large region is
Where we have used f(x)=F'(x). The limits of integration are 0 to 1, since that is what F ranges over. Thus we get 1/3 for the chance an interval is large. A similar calculation shows that you also get 1/3 for small and medium intervals. This means that if an interval is selected at random, it is equally likely to be small, medium, or large, and this is independent of the probability distribution that the points are selected with.
The fact that P(small)=P(large) is somewhat obvious if you consider doing a plot of interval lengths. Small intervals will be a local minimum of the plot, while large intervals will be local maxima. For any two local minima, there must be a local maxima in between and vice-versa, so the number of small intervals must be the same as the number of large intervals (well, within 1 anyway), so in the infinite limit they will have the same probability. It is not clear why medium intervals would be equally likely, but there is probably some underlying reason.
Moving on, the expected length of a large interval is given by
which we can integrate by parts. Let u=x and v=F(x)3-1, so then we have
v was chosen so that the first term would vanish at the endpoints, so that last integral gives us the average size of a large interval.
One can do a similar calculation for small and medium intervals, and the expressions are only slightly uglier, but this is as far as we can go without giving a specific form to the function F(x).
To proceed, assume that we have distributed the N dots on the line, and we scale things up by a factor of N, so there is on average 1 dot per unit length, then one can show that the function F(x) will tend to 1-e-x for large N (I cannot really prove this, it makes sense, but people who wrote the solutions quoted at cut-the-knot took this result as obvious, so I suspect it is some elementary thing that I simply am unfamiliar with (to be honest, its why I found their solutions unconvincing and did my own awful one, I couldn't get past this point)).
Anyway, using that F for the integral, one gets that the average size of a large interval is 11/18. This must be multiplied by N to account for the fact that there are N intervals, but then divided by N because we scaled everything up by a factor of N.
A similar calculation gives that the average size of a medium interval is 5/18 and small intervals are 2/18.
So the ratio of small:medium:large intervals is 2:5:11. the small+medium intervals account for (2+5)/18 of the total length, giving the answer to the original problem. Note that if the small intervals are counted twice, then the total amount painted is (2+2+5)/18, which is exactly 1/2. I have not yet found a way to explain why this answer would be so clean.
When I first found out about the fact that small, medium, and large segments all appear with equal probability, I was inspired to try a slightly different problem. Suppose we take the unit circle and place 3 points on it, that will divide the circle into 3 parts, one small, one large, and one medium. On average, what is the relative sizes of these three parts?
This is simple enough to calculate, let the points be located at 0, x and y where x and y vary from 0 to 1 (1 being the full circle). By the symmetry of the problem, lets assume that x is smaller than y, and lets assume that the interval between 0 and x is the smallest. So y varies from 2x to 1-x and x varies from 0 to 1/3. The average length can be found from the integral
over the regions specified. We also need to divide by the integral of 1 over that same region, to divide by the probability that the region is actually a small one, essentially just normalizing properly.
Naturally, you can do a similar calculation for the largest interval and for the other one. In the end, you get the answers 2/18, 5/18, 11/18, unsurprising given that I chose to bring this whole thing up. So one does not need to work in the infinite case, somehow only using 3 points and 3 intervals gives the correct answer, but I have no idea why.
On the puzzle page over at cut-the-knot, they had a few writeups of possible ways to arrive at the solution. They varied in their degree of rigour, but they certainly were all more elegant than my method. One in particular led me to examine a few other things about the puzzle (that I honestly do not understand the implications of), and I will go over them here.
This solution was put forward by Stuart Anderson, and it beings by assuming that the dots do not necessarily follow a uniform distribution. Suppose x is the length of an interval between adjacent points, and let f(x)dx be the probability that a particular interval has length between x and x+dx. F(x) will be the cumulative probability distribution, so F'(x)=f(x) and F(x) ranges from 0 to 1, as x ranges from 0 to 1.
We will call an interval "small" if it is smaller than both its neighbours, "large" if it is larger than both its neighbours, and "medium" otherwise. Intervals that are small get painted twice, and medium ones get painted once, while large ones are unpainted. Lets try to find out how many of each region we have and how large each type is. Suppose we have an interval with size x, that occurs with chance f(x)dx, and its left hand neighbour will be smaller than it with chance F(x) (F(x) being the cumulative distribution function, it is the integral of f(y) from 0 to x). Similarly, the right hand neighbour will be smaller with chance F(x), so the total chance that we have a large region is
∫F(x) F(x) f(x) dx
=∫F(x)2 dF
Where we have used f(x)=F'(x). The limits of integration are 0 to 1, since that is what F ranges over. Thus we get 1/3 for the chance an interval is large. A similar calculation shows that you also get 1/3 for small and medium intervals. This means that if an interval is selected at random, it is equally likely to be small, medium, or large, and this is independent of the probability distribution that the points are selected with.
The fact that P(small)=P(large) is somewhat obvious if you consider doing a plot of interval lengths. Small intervals will be a local minimum of the plot, while large intervals will be local maxima. For any two local minima, there must be a local maxima in between and vice-versa, so the number of small intervals must be the same as the number of large intervals (well, within 1 anyway), so in the infinite limit they will have the same probability. It is not clear why medium intervals would be equally likely, but there is probably some underlying reason.
Moving on, the expected length of a large interval is given by
∫x F(x) F(x) f(x) dx
which we can integrate by parts. Let u=x and v=F(x)3-1, so then we have
x(F(x)3-1)+∫(1-F(x)3) dx
v was chosen so that the first term would vanish at the endpoints, so that last integral gives us the average size of a large interval.
One can do a similar calculation for small and medium intervals, and the expressions are only slightly uglier, but this is as far as we can go without giving a specific form to the function F(x).
To proceed, assume that we have distributed the N dots on the line, and we scale things up by a factor of N, so there is on average 1 dot per unit length, then one can show that the function F(x) will tend to 1-e-x for large N (I cannot really prove this, it makes sense, but people who wrote the solutions quoted at cut-the-knot took this result as obvious, so I suspect it is some elementary thing that I simply am unfamiliar with (to be honest, its why I found their solutions unconvincing and did my own awful one, I couldn't get past this point)).
Anyway, using that F for the integral, one gets that the average size of a large interval is 11/18. This must be multiplied by N to account for the fact that there are N intervals, but then divided by N because we scaled everything up by a factor of N.
A similar calculation gives that the average size of a medium interval is 5/18 and small intervals are 2/18.
So the ratio of small:medium:large intervals is 2:5:11. the small+medium intervals account for (2+5)/18 of the total length, giving the answer to the original problem. Note that if the small intervals are counted twice, then the total amount painted is (2+2+5)/18, which is exactly 1/2. I have not yet found a way to explain why this answer would be so clean.
When I first found out about the fact that small, medium, and large segments all appear with equal probability, I was inspired to try a slightly different problem. Suppose we take the unit circle and place 3 points on it, that will divide the circle into 3 parts, one small, one large, and one medium. On average, what is the relative sizes of these three parts?
This is simple enough to calculate, let the points be located at 0, x and y where x and y vary from 0 to 1 (1 being the full circle). By the symmetry of the problem, lets assume that x is smaller than y, and lets assume that the interval between 0 and x is the smallest. So y varies from 2x to 1-x and x varies from 0 to 1/3. The average length can be found from the integral
∫∫x dy dx
over the regions specified. We also need to divide by the integral of 1 over that same region, to divide by the probability that the region is actually a small one, essentially just normalizing properly.
Naturally, you can do a similar calculation for the largest interval and for the other one. In the end, you get the answers 2/18, 5/18, 11/18, unsurprising given that I chose to bring this whole thing up. So one does not need to work in the infinite case, somehow only using 3 points and 3 intervals gives the correct answer, but I have no idea why.
Shaking Hands
Alright, the thesis is currently sitting at 40 pages, so I'm happy enough with my progress that I deserve to take a break. Naturally a break comes in the from of posting solutions to logic puzzles, because I have no sense of fun. So, lets look at the solution to the crazy ass number problem from last time.
First of all, if you played around with it a bit, you probably determined that for any starting N, only one final M was ever possible. As far as I am concerned, that fact was in of itself neat enough to make this puzzle pretty cool, but lets look at it a bit more.
First, if you just split N into N-1 and 1, and then N-1 into N-2 and 1 and just keep splitting off 1 all the way down, then you end with having written N-1, N-2, N-3,..., 2, 1 on board two, so the total sum is N(N-1)/2. Thus, if for any N there is only one possible value of M, that value must be N(N-1)/2. Note a particular edge case, that of N is 1, we take the value of M to be zero, later we will see that this is important for consistency.
Alright, so let us conjecture the solution to the puzzle:
Initially I wanted to prove this by induction, and one almost can, but actually to do it properly you need to break out strong induction, which I will talk briefly about first.
Induction is used if you want to prove some statement S(n) for all natural numbers n (and for the purpose of this post, the naturals start at 1 (and it pains me to write that)). You prove the statement is true by first showing that S(1) is true, and then showing that S(k-1) implies S(k) for k>1, good stuff, and the intuition behind it is pretty obvious for anybody who would actually read this blog.
For strong induction, you instead prove S(n) by proving S(1) and then show that [S(j) for all j less than k] implies S(k) for k>1. Intuitively, its not really any different from regular induction, the assumption is technically a bit different, but it still works. Naturally, one can reformulate any induction proof as a strong induction proof, as the strong induction assumption of [S(j) for all j less than k] is a stronger assumption than S(k-1), but there are some strong induction proofs that cannot be recast as regular induction, since you needed the stronger assumption. Strong induction is also used for proving statements about the ordinals, since some of those are not successors to other ones.
Anyway, let us prove our earlier conjecture by strong induction. It is easy to see that it holds for small N (I'm not sure about proving it for N=1, but lets just start with 2 or something). Now, assume that it is true for all j less than k for some k. Lets say that k is written on the board and calculate the possible values of M. We break k into p and k-p, for some p less than k. We then write p(k-p) on board 2, and are left with p and k-p on board 1. Naturally breaking up p results in us writing numbers summing to p(p-1)/2 on board 2 (by strong induction assumption) and breaking up k-p results in us writing numbers summing up to (k-p)(k-p-1)/2 onto board 2. Note that if p=1 or p=k-1, then having a 1 on board one does not result in any additional numbers on board 2, good.
So, on board 2, we have p(k-p) and a bunch of other numbers that sum to p(p-1)/2 and (k-p)(k-p-1)/2. Adding those up, we get k(k-1)/2 for any choice of p, proving the conjecture.
On the xkcd forums, somebody posted a much simpler solution than mine, and its cool enough that I will give it here.
Consider that we have N people in a room, and breaking N up into p and N-p is splitting people up into smaller groups. Before we split people up, they all shake hands with the people in the other group and say goodbye. For example, when we split 8 into 5 and 3, the 5 people each shake hands with the 3 people, so there are 15 handshakes. Board 2 is just keeping track of handshakes. The steps halt when everybody has been fully divided up and everybody must have said goodbye to everybody else. How many handshakes were there? There must have been N choose 2 of them, which is N(N-1)/2.
First of all, if you played around with it a bit, you probably determined that for any starting N, only one final M was ever possible. As far as I am concerned, that fact was in of itself neat enough to make this puzzle pretty cool, but lets look at it a bit more.
First, if you just split N into N-1 and 1, and then N-1 into N-2 and 1 and just keep splitting off 1 all the way down, then you end with having written N-1, N-2, N-3,..., 2, 1 on board two, so the total sum is N(N-1)/2. Thus, if for any N there is only one possible value of M, that value must be N(N-1)/2. Note a particular edge case, that of N is 1, we take the value of M to be zero, later we will see that this is important for consistency.
Alright, so let us conjecture the solution to the puzzle:
When N is the starting value, then N(N-1)/2 is the unique final value of M.
Initially I wanted to prove this by induction, and one almost can, but actually to do it properly you need to break out strong induction, which I will talk briefly about first.
Induction is used if you want to prove some statement S(n) for all natural numbers n (and for the purpose of this post, the naturals start at 1 (and it pains me to write that)). You prove the statement is true by first showing that S(1) is true, and then showing that S(k-1) implies S(k) for k>1, good stuff, and the intuition behind it is pretty obvious for anybody who would actually read this blog.
For strong induction, you instead prove S(n) by proving S(1) and then show that [S(j) for all j less than k] implies S(k) for k>1. Intuitively, its not really any different from regular induction, the assumption is technically a bit different, but it still works. Naturally, one can reformulate any induction proof as a strong induction proof, as the strong induction assumption of [S(j) for all j less than k] is a stronger assumption than S(k-1), but there are some strong induction proofs that cannot be recast as regular induction, since you needed the stronger assumption. Strong induction is also used for proving statements about the ordinals, since some of those are not successors to other ones.
Anyway, let us prove our earlier conjecture by strong induction. It is easy to see that it holds for small N (I'm not sure about proving it for N=1, but lets just start with 2 or something). Now, assume that it is true for all j less than k for some k. Lets say that k is written on the board and calculate the possible values of M. We break k into p and k-p, for some p less than k. We then write p(k-p) on board 2, and are left with p and k-p on board 1. Naturally breaking up p results in us writing numbers summing to p(p-1)/2 on board 2 (by strong induction assumption) and breaking up k-p results in us writing numbers summing up to (k-p)(k-p-1)/2 onto board 2. Note that if p=1 or p=k-1, then having a 1 on board one does not result in any additional numbers on board 2, good.
So, on board 2, we have p(k-p) and a bunch of other numbers that sum to p(p-1)/2 and (k-p)(k-p-1)/2. Adding those up, we get k(k-1)/2 for any choice of p, proving the conjecture.
On the xkcd forums, somebody posted a much simpler solution than mine, and its cool enough that I will give it here.
Consider that we have N people in a room, and breaking N up into p and N-p is splitting people up into smaller groups. Before we split people up, they all shake hands with the people in the other group and say goodbye. For example, when we split 8 into 5 and 3, the 5 people each shake hands with the 3 people, so there are 15 handshakes. Board 2 is just keeping track of handshakes. The steps halt when everybody has been fully divided up and everybody must have said goodbye to everybody else. How many handshakes were there? There must have been N choose 2 of them, which is N(N-1)/2.
Splitting Up Numbers
Time to take a break from thesis writing to blog. I won't have much time to blog for the next little while, due to said thesis, but I found a new puzzle recently I really wanted to post. I still intend to post the follow-up to my post from last time about other solutions to the birds on a wire problem, but I don't have the time to give that a full write up right now. Anyway, this puzzle is really weird to word properly, so if you don't get it the first time read the example I give after and then try reading it again. I first learned this puzzle on the forums at xkcd.
Alright, so as example, let us assume N=8. Now, we select a number of the board (there is only 8, so we choose it) and select that i and j are 5 and 3. We cross out 8 and write 5 and 3 on the first blackboard, and write 15 on the second one.
Next step we select 3, crossing it out and writing 1 and 2 on the first blackboard, writing 2 on the second blackboard. On the first board there is now (1,2,5) and on the second one there is (15,2)
Next step we select 5 and cross it out and write 2 and 3 on board one, writing 6 on board two. Board one has (1,2,2,3) board two has (15,2,6)
Next step we select 2, writing 1 and 1 in its place, and write 1 on board two. The boards are (1,1,1,2,3) and (15,2,6,1)
Next select 2, write 1 and 1 in its place, writing 1 on board two. The boards are (1,1,1,1,1,3) and (15,2,6,1,1)
Next select 3, writing 2 and 1 in its place, writing 2 on board two. The boards are (1,1,1,1,1,1,2) and (15,2,6,1,1,2)
Next select 2, writing 1 and 1 in its place, writing 1 on board two. The boards are (1,1,1,1,1,1,1,1) and (15,2,6,1,1,2,1)
Finally we stop, board one has no numbers greater than 1. We calculate M by adding up the numbers on board two, se we see M=28.
So we see that when N=8, it is possible for M to be 28. The puzzle is asking what other values of M are possible for N=8? What about other values of starting N?
There are 2 blackboards, and on the first one a natural number N>1 is written, the second board starts empty. You are going to do a calculation in a series of steps. A step is defined as follows:
If there are no numbers greater than 1 on the first blackboard, stop. Otherwise select one of the numbers greater than 1, call it k. Select two natural numbers i and j smaller than k such that i+j=k. Cross out k from the first black board, and write i and j on the first blackboard. On the second blackboard, write the product i*j. Then do another step.
When you are done doing steps (because all the numbers on the first blackboard are equal to 1), and add up the numbers on the second blackboard, call this sum M.
The puzzle is, given the initial value of N, what are the possible values of M?
Alright, so as example, let us assume N=8. Now, we select a number of the board (there is only 8, so we choose it) and select that i and j are 5 and 3. We cross out 8 and write 5 and 3 on the first blackboard, and write 15 on the second one.
Next step we select 3, crossing it out and writing 1 and 2 on the first blackboard, writing 2 on the second blackboard. On the first board there is now (1,2,5) and on the second one there is (15,2)
Next step we select 5 and cross it out and write 2 and 3 on board one, writing 6 on board two. Board one has (1,2,2,3) board two has (15,2,6)
Next step we select 2, writing 1 and 1 in its place, and write 1 on board two. The boards are (1,1,1,2,3) and (15,2,6,1)
Next select 2, write 1 and 1 in its place, writing 1 on board two. The boards are (1,1,1,1,1,3) and (15,2,6,1,1)
Next select 3, writing 2 and 1 in its place, writing 2 on board two. The boards are (1,1,1,1,1,1,2) and (15,2,6,1,1,2)
Next select 2, writing 1 and 1 in its place, writing 1 on board two. The boards are (1,1,1,1,1,1,1,1) and (15,2,6,1,1,2,1)
Finally we stop, board one has no numbers greater than 1. We calculate M by adding up the numbers on board two, se we see M=28.
So we see that when N=8, it is possible for M to be 28. The puzzle is asking what other values of M are possible for N=8? What about other values of starting N?
Subscribe to:
Posts (Atom)
