I guess its about time I post the solution to the coin puzzle from last time. I guess I could solve out the n=1 case first and then generalize, but it isn't particularly interesting to do that, so I think I'll just solve the general problem outright.
So we have 4n+1 coins and in a single step we can find the median of 2n+1 of them, and we have n+2 steps to work with. Now, the goal is to identify the median coin, which I shall call M. We will know a particular coin is coin M if there are exactly 2n coins heavier than it and 2n coins lighter than it.
Begin by selecting any 2n+1 coins and putting then in the machine (there is no other first step, of course), take the median coin and paint it red (I will be painting coins as we move along so that I can refer to particular groups of coins). Set the red coin aside and grab any other coin to measure with those same 2n coins. Repeat this process until you have done n+1 measurements and have n+1 red coins. Paint the other 2n coins involved in those measurements yellow, and the remaining n coins blue.
I claim that if you sorted the yellow and red coins by weight, the order would be n yellow coins, followed by all n+1 red coins, followed by the other n yellow coins, that is to say that each red coin has exactly n yellow coins lighter than it and n yellow coins heavier than it. This happens because if you were to start with the 3n+1 yellow and red coins and measure any 2n+1 of them, each time a coin from the middle n+1 of them will come out, that is, by finding medians and setting them aside, you find the middle n+1 of them, and those are the ones we are calling the red ones.
Now, with our last measurement, measure the n+1 red coins with the n blue ones, and call the median of that measurement P. I claim the P is the median coin M. We can see this in two cases, first if P is red, we know that P has n yellows above it and n yellows below it in weight. But P also has n non-yellows above and n non-yellows below it in weight (because it was the median of the final measurement), proving P is M. If P is blue, then it must lie strictly between two reds, since there must be n non-yellows above it and n non-yellows below it and n+1 of the non-yellows are red. Since it lies between two reds, it must have n yellows above it and n yellows below it. So this coin is had n yellows and n non-yellows above it, and also n yellows and n non-yellows below it.
Fun stuff.
Median Coins
Where the heck did that month go? Anyway, I finally managed to get another puzzle to put up. Technically, its a varaint of one I found on Tanya Khovanovas math blog:
And a somewhat generalized version:
In Tanyas version, Baron Münchhausen identifies the coin of median weight ahead of time, and you must use the machine no more than n+2 times to confirm if he is right. When I found my solution to the problem though, I noticed that I didn't need that extra information, I could simply confirm if he was right by using my method and checking if his median was the same as mine. Anyway, I guess its still possible I did something stupid and am wrong, so if you are unable to solve the problem as I posted it try Tanyas version instead, mine might just be impossible.
You have 5 coins of distinct weights, and you have a machine that if you put in 3 coins of distinct weights it will identify the coin of median weight. Of the 5 coins, find the coin of median weight using the machine no more than 3 times.
And a somewhat generalized version:
You have 4n+1 coins of distinct weights, and you have a machine that if you put in 2n+1 coins of distinct weights it will identify the coin of median weight. Of the 4n+1 coins, find the coin of median weight using the machine no more than n+2 times.
In Tanyas version, Baron Münchhausen identifies the coin of median weight ahead of time, and you must use the machine no more than n+2 times to confirm if he is right. When I found my solution to the problem though, I noticed that I didn't need that extra information, I could simply confirm if he was right by using my method and checking if his median was the same as mine. Anyway, I guess its still possible I did something stupid and am wrong, so if you are unable to solve the problem as I posted it try Tanyas version instead, mine might just be impossible.
Up Is Down
Remembering to post solutions to stuff takes alot of work. Anyway, I guess its time to do my semi-incomplete solution to the card puzzle from last time. I managed to think more about the puzzle to come up with a slightly better solution than I had before, apparently there is a 26 card solution, but I only know of a 25 card one.
First of all, note that in any solution we can easily get the last card trivially just by counting. We can even get the last two cards easily, if they are the same then we know that, and if they are different we can use the second last card as 'up' if they appear in alphabetical order and 'down' if they appear in reverse alphabetical order. This can be appended to any strategy to get the last two cards, so we don't need to worry about them.
For the remaining cards, we can group them into threes in a similar method as the Sam and Ray problem. We spend our first card to specify the most common colour of the next three (up for black, down for red, say) and then on each of those three cards we use the back of the card to specify exactly which suit it is (up for clubs or hearts, down for spades or diamonds). On the one that is off colour (the one black on the group of red), there is no reason for the assistant to specify the suit (the psychic will get it wrong anyway), so he uses that one to specify the most common colour of the next group of three. If none of the three are off colour, we will simply use the third card instead (so the psychic knows if he gets the first two of three right, then the third one is going to be spent on that).
Using this strategy we get the first card wrong, followed by two of three right for the next 11 sets of three (that is 22 right of 33 cards) and then we get the last two right using the earlier strategy. This gives us 24 correct, and this was as much as I was able to get without reading comments from Tanya's blog.
The next thing to do is to make use of a 'surprise' in our strategy, we have the assistant purposely get something wrong and use that to communicate further (actually I have since learned that this can be used in the Sam and Ray problem to get a much simpler solution). So, this time we get our first card wrong, and then use 8 groups of 3 cards (we should be able to get 16 right, but the assistant will mess exactly one of those up, so we will only get 15 right). Thats 25 cards so far, and we have gotten 15 of them right, we will also get the last two right, so we have 9 cards left and we had better be able to get at least 8 of them right if we want this to actually be an improvement. How much can we specify with our 'surprise' strategy? We get 1 of the 16 cards wrong, so that is 4 bits in just choosing which card, and we also have 1 bit from the last card we got wrong (that one that would be specifying the next group of three). So with 5 bits and 9 cards left, what can we do?
It is natural to try to divide the 9 cards into 3 groups of 3, but I wasn't able to do anything with that, in particular I couldn't find a way to get 8 of them right. What I found did work was to split the 9 cards into 5 and 4, use our 5 bits to specify the colours of the next 5 cards, and use the backs of those cards to specify the exact cards. We can get all 5 of those right at the cost of our 5 bits, but then we use another surprise strategy. On one of those 5 cards, we arrange to get one of them wrong, allowing us to specify a number between 1 and 5, but also we can get it wrong in one of three ways (if we order the suits as clubs, diamonds, hearts, then spades, then when we get the suit wrong we can be off by 1, 2, or 3 full steps). Thus we can specify as many as 3*5=15 unique things. We also had the option to not get one wrong at all, that being a 16th choice. Using all of this, we can spend 5 bits on 5 cards to get 4 (or maybe 5) of them right and come out the other end with 4 bits. Those 4 bits can be spent to give the colours of the 4 remaining cards, and then we use the backs of those cards to get them right. Finally we have the last two cards by the earlier method.
This is the best solution that I know of, getting 25 of the 36 cards. On Tanya Khovanova's blog she says there is a 26 card solution, but I haven't found it yet.
First of all, note that in any solution we can easily get the last card trivially just by counting. We can even get the last two cards easily, if they are the same then we know that, and if they are different we can use the second last card as 'up' if they appear in alphabetical order and 'down' if they appear in reverse alphabetical order. This can be appended to any strategy to get the last two cards, so we don't need to worry about them.
For the remaining cards, we can group them into threes in a similar method as the Sam and Ray problem. We spend our first card to specify the most common colour of the next three (up for black, down for red, say) and then on each of those three cards we use the back of the card to specify exactly which suit it is (up for clubs or hearts, down for spades or diamonds). On the one that is off colour (the one black on the group of red), there is no reason for the assistant to specify the suit (the psychic will get it wrong anyway), so he uses that one to specify the most common colour of the next group of three. If none of the three are off colour, we will simply use the third card instead (so the psychic knows if he gets the first two of three right, then the third one is going to be spent on that).
Using this strategy we get the first card wrong, followed by two of three right for the next 11 sets of three (that is 22 right of 33 cards) and then we get the last two right using the earlier strategy. This gives us 24 correct, and this was as much as I was able to get without reading comments from Tanya's blog.
The next thing to do is to make use of a 'surprise' in our strategy, we have the assistant purposely get something wrong and use that to communicate further (actually I have since learned that this can be used in the Sam and Ray problem to get a much simpler solution). So, this time we get our first card wrong, and then use 8 groups of 3 cards (we should be able to get 16 right, but the assistant will mess exactly one of those up, so we will only get 15 right). Thats 25 cards so far, and we have gotten 15 of them right, we will also get the last two right, so we have 9 cards left and we had better be able to get at least 8 of them right if we want this to actually be an improvement. How much can we specify with our 'surprise' strategy? We get 1 of the 16 cards wrong, so that is 4 bits in just choosing which card, and we also have 1 bit from the last card we got wrong (that one that would be specifying the next group of three). So with 5 bits and 9 cards left, what can we do?
It is natural to try to divide the 9 cards into 3 groups of 3, but I wasn't able to do anything with that, in particular I couldn't find a way to get 8 of them right. What I found did work was to split the 9 cards into 5 and 4, use our 5 bits to specify the colours of the next 5 cards, and use the backs of those cards to specify the exact cards. We can get all 5 of those right at the cost of our 5 bits, but then we use another surprise strategy. On one of those 5 cards, we arrange to get one of them wrong, allowing us to specify a number between 1 and 5, but also we can get it wrong in one of three ways (if we order the suits as clubs, diamonds, hearts, then spades, then when we get the suit wrong we can be off by 1, 2, or 3 full steps). Thus we can specify as many as 3*5=15 unique things. We also had the option to not get one wrong at all, that being a 16th choice. Using all of this, we can spend 5 bits on 5 cards to get 4 (or maybe 5) of them right and come out the other end with 4 bits. Those 4 bits can be spent to give the colours of the 4 remaining cards, and then we use the backs of those cards to get them right. Finally we have the last two cards by the earlier method.
This is the best solution that I know of, getting 25 of the 36 cards. On Tanya Khovanova's blog she says there is a 26 card solution, but I haven't found it yet.
Psychic Suits
I'm still blogging, who says I'm not? Anyway, there was a cool puzzle over at Tanya Khovanova's math blog that I've been wanting to post for a while, but I wanted to get a complete solution first. Anyway, it turns out its crazy hard, but I know enough of a solution to make it worth posting as is. Alright, here we go:
There is a deck of 36 cards, 9 cards in each of four suits. The deck is in a face-down pile in front of a psychic, who is going to guess the suits of the cards and turn them over one at a time.So, as an example strategy, we can get every other card easily: each two cards is two bits of information, so we simply use them to specify the suits of every other card. For example up-up means spades, up-down means hearts down-up means diamonds and down-down means clubs. With this strategy it is guaranteed that the psychic can get every other card correct, giving us 18 out of the 36 cards. Try to make a strategy that guarantees at least 19 cards. I know of a strategy that will get 24, one can also do more than that, but I don't know how, I'll give more info on that next time.
The psychic makes a guess about the suit of the next card and then turns it over to see if they were correct, then proceeds to do that again on the next card. The backs of the cards are asymmetric, so it is possible to tell which way is up, and the psychic can see the back of each card before making the guess for that card. The psychic has an assistant who is allowed to orient the cards however he wants after the deck is shuffled (but he is not allowed to rearrange the cards in the deck). Before the deck is shuffled, the psychic and the assistant may communicate to plan a strategy.
What is the maximum number of cards the psychic can guarantee to get correct?
Weird Answer
Alright, time to post the solution to the limit from last time. To start with, let us consider the following function
f(x)=sin(2πx)for our puzzle, we have to worry about x=N!e. Clearly f is periodic in x with period 1, and so for this function only the non-integer part of x matters. That is f(2.7)=f(0.7), f(5749.276)=f(0.276), and f(x+N)=f(x) for integer N. Now consider
limN->∞f(N!r)for N going to infinity along the integers and r any rational number. Since r is rational, r=p/q for p and q integers. Once N is greater than q we will have that N!r will always be an integer, so the limit will necessarily be zero. This proves that
limN->∞f(N!(e+r))=limN->∞f(N!e+N!r) =limN->∞f(N!e)Proving the statement I made last time. Of course, since e is irrational, we must be a bit more careful. To proceed, we must use the following formula for e
e=Σ1/k!Summing k from 0 to infinity. If you don't recall this formula, you can derive it from the taylor expansion for ex and sub in x=1. Anyway, so N!e then looks like
N!e=ΣN!/k! =N!/0!+N!/1!+N!/2!+...N!/N!+N!/(N+1)!+N!/(N+2)!+... =M+1/(N+1)+1/(N+1)(N+2)+...For M being some integer. So, we must have
f(N!e)=f(M+1/(N+1)+1/(N+1)(N+2)+...) =f(1/(N+1)+O(1/N2))The O(1/N2) means terms like 1/N2 or smaller (as N is going to be large). We know that sin(x+O(x2))=x+O(x2) for small x though, so we must have
f(N!e)=2π/(N+1)+O(1/N2)Which means that
limN->∞ N sin(N!2πe) =limN->∞ 2πN/(N+1)+O(1/N2) =2πEnding the problem. Essentially the proof comes down to the fact that N!e gets arbitrarily close to integer values for large N (as we have seen, it gets within 1/N of an integer). Actually, if you try to do this limit on any computer it almost certainly won't work, as the computers approximate value of e will explode terribly when multiplied by N!. I recall that wolfram alpha can't handle this limit (or at least I have never found a way to coax it into getting this limit).
Weird Limit
I guess its new puzzle time. I do have a new puzzle to post, but I haven't fully solved it out yet, and I don't like posting puzzles I don't have full solutions to, since I'm worried it will take longer than I expect. Instead I'm going to post a limit I saw a few years ago that I thought was really neat. Thats right, its time for math. Anyway,
where the limit of N is taken along integer values (which is why I can use factorial instead of gamma or something). Its interesting as the coefficient out front is just going to diverge linearly, and the argument of the sin function is just seemingly random numbers, so it should be random numbers times a huge number, its actually amazing that the limit exists at all.
Anyway, the limit does exist as a nonzero real number, I'll show it next time, but it turns out it converges by the magic of e. Well, not quite just e, if you replaced e by e+r with any rational number r, this limit would still exist (that is a bit of a hint for you).
limN->∞ N sin(N!2πe)
where the limit of N is taken along integer values (which is why I can use factorial instead of gamma or something). Its interesting as the coefficient out front is just going to diverge linearly, and the argument of the sin function is just seemingly random numbers, so it should be random numbers times a huge number, its actually amazing that the limit exists at all.
Anyway, the limit does exist as a nonzero real number, I'll show it next time, but it turns out it converges by the magic of e. Well, not quite just e, if you replaced e by e+r with any rational number r, this limit would still exist (that is a bit of a hint for you).
Circles In A Line
Been a month since I put up the circles puzzle last time, I guess its time to solve it out now.
Its easy to see that we lose nothing by just having all the circles in a line along the x-axis (say) and we will specify a circle by giving the distance between its center and the previous circle, we will call this di. Circle i will also have radius ri, and we know r0=1 from the setup (I'm numbering the circles 0 to 15 now, cause thats how I roll). The goal is to maximize d1+d2+d3+...+d15+r15. Given d1, r1 gets specified, by d12+r12=1 (if this isn't clear to you, draw circles 0 and 1 and do some trig, its pretty simple). We can similarly see that di2+ri2=ri-12. So,
For some sense of completeness, we might as well add on a d16 which equals r15, and r16 is zero. So we have to maximize Σdi while holding Σdi2=1. You probably just know this max is achived when the di are all equal, but lets solve it by Lagrange multipliers, because I haven't done that in years.
The maximum of f(xi), subject to g(xi)=K will occur at dg/dxi=λdf/dxi for each i. So, if f is the sum of x's and g is the sum of x2's, we get xi=λ/2, they are all the same, good.
Anwyay, so for our problem, this means that di=A, and since the sum of their squares is 1, they much each be 1/√16=1/4. Summing di to find the answer, we get 16/4, which is 4 for the maximum distance.
Its pretty easy to see that with N circles the answer will simply be √N, surprisingly fast asymptotically, but there you go.
When I told this problem to Sean, he suggested attempting the greedy algorithm. That is, just place the second circle to solve the two circle problem, and place the third circle to solve the local problem (which is a two circle problem again, but scaled down in size) and so on. Looking at the answer we got, its clear that the greedy algorithm won't work to give the optimal answer, but lets see what it does give.
The circles will again have radii given by ri and the centers will be spaced a distance di from eachother. r0=1 of course, and d1 will be such that d1+r1 is maximized while d12+r12=1. So, we have d1=1/√2=r1. Next d2 will be such that d2+r2 is maximized while d22+r22=1/2. So, we have d2=1/√22=r2. Next d3 will be such that d3+r3 is maximized while d32+r32=1/22. So, we have d3=1/√23=r3.
Clearly we will get di=1/√2i=ri, and the sum of the di will be the sum of 1/√2i. The infinite sum of ai starting at 1 is a/(1-a), so when a=1/√2 we get 1/(√2-1) which is the same as 1+√2, so about 2.41. The greedy method asymptotes to a constant, neat.
Anyway, thats all I got.
Its easy to see that we lose nothing by just having all the circles in a line along the x-axis (say) and we will specify a circle by giving the distance between its center and the previous circle, we will call this di. Circle i will also have radius ri, and we know r0=1 from the setup (I'm numbering the circles 0 to 15 now, cause thats how I roll). The goal is to maximize d1+d2+d3+...+d15+r15. Given d1, r1 gets specified, by d12+r12=1 (if this isn't clear to you, draw circles 0 and 1 and do some trig, its pretty simple). We can similarly see that di2+ri2=ri-12. So,
d12+r12=1And so on, until we have
d12+d22+r22=1
d12+d22+d32+r32=1
Σdi2+r152=1As our restriction.
For some sense of completeness, we might as well add on a d16 which equals r15, and r16 is zero. So we have to maximize Σdi while holding Σdi2=1. You probably just know this max is achived when the di are all equal, but lets solve it by Lagrange multipliers, because I haven't done that in years.
The maximum of f(xi), subject to g(xi)=K will occur at dg/dxi=λdf/dxi for each i. So, if f is the sum of x's and g is the sum of x2's, we get xi=λ/2, they are all the same, good.
Anwyay, so for our problem, this means that di=A, and since the sum of their squares is 1, they much each be 1/√16=1/4. Summing di to find the answer, we get 16/4, which is 4 for the maximum distance.
Its pretty easy to see that with N circles the answer will simply be √N, surprisingly fast asymptotically, but there you go.
When I told this problem to Sean, he suggested attempting the greedy algorithm. That is, just place the second circle to solve the two circle problem, and place the third circle to solve the local problem (which is a two circle problem again, but scaled down in size) and so on. Looking at the answer we got, its clear that the greedy algorithm won't work to give the optimal answer, but lets see what it does give.
The circles will again have radii given by ri and the centers will be spaced a distance di from eachother. r0=1 of course, and d1 will be such that d1+r1 is maximized while d12+r12=1. So, we have d1=1/√2=r1. Next d2 will be such that d2+r2 is maximized while d22+r22=1/2. So, we have d2=1/√22=r2. Next d3 will be such that d3+r3 is maximized while d32+r32=1/22. So, we have d3=1/√23=r3.
Clearly we will get di=1/√2i=ri, and the sum of the di will be the sum of 1/√2i. The infinite sum of ai starting at 1 is a/(1-a), so when a=1/√2 we get 1/(√2-1) which is the same as 1+√2, so about 2.41. The greedy method asymptotes to a constant, neat.
Anyway, thats all I got.
Subscribe to:
Posts (Atom)
