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?
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:
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.
Circles On Circles
New puzzle time? I guess it must be, its certainly not new solution time. Though I think I still have left that cats and dogs game hanging, one day I'll have to revisit that. Anyway, I found this puzzle on the xkcd forums, but its initially from the cofoundry:
There are 16 overlapping circles in a plane with the following proerties:By "overlapping circles" I really mean that circle N can share some interior points with circle N+1, it just helps to say it that way to imagine the setup. If you have forgotten your grade school geometry you may want to look up what a chord of a circle is on wikipedia or something.
Circle 1 has radius 1
The diameter of circle 2 is a chord of circle 1
The diameter of circle 3 is a chord of circle 2
...
The diameter of circle 16 is a chord of circle 15
What is the maximum distance from a point in circle 16 to the center of circle 1?
True And False
I suppose the True or False puzzle from last time has been up long enough, so I should probably get around to the solution. Like I said, my solution will basically be following the derivation that Tanya Khovanova did on her blog, because she did a better job of it than I expect to be able to anyway.
Alright, remember last time I said it is important to solve the simpler case of 5 questions with 4 attempts, so lets assume that we already have the ability to do that (I will show how later) and then use that to solve the problem of 30 questions. Without any loss of generality, we might as well have Victor answer "true" to all the questions first, to establish a base case. Next, we can submit the first 5 as "false" and the other 25 as "true" to get a base case for the first 5 questions (which we can then solve independently in 4 attempts), next we do the next batch of 5 as "false" with the rest "true" to get a base case for the next 5 and solve those in 4 more attempts. When we get to the last batch of 5, we don't need to do a final base case for those ones, as we already had our initial base case to tell us how many true answers are on the test in total, and we knew how many true were in each other block of 5, so we have already found our base for the last 5 questions. This argument shows quite generally that if you can do Q questions in N attempts then you can do MQ questions in MN attempts (for our case Q=5, N=4, M=6).
Now, how do we do 5 questions in 4 attempts? First we spend one attempt on our base case to see how many answers are "true", so we submit TTTTT. For the other 3 attempts, we will switch some of the answers to "false". There is no need to switch 3 of them to "false", as you get the same information by taking the compliment and switching the other 2 of them to "false". Similarly switching 4 or 5 to "false" is also meaningless, so we need only worry about 1 or 2. If we use FTTTT for our second attempt, we will get the answer to the first question and have 2 more attempts to solve out the remaining 4 questions, seems sort of hard (is in fact impossible, but I'm not going to prove that), so for our second attempt we must flip two answers to "false". Thus we can use FFTTT as our second test.
For our third test, we can basically choose between TTFFT ad FTFTT, depending on if we want our third attempt to have any overlap with our second attempt. But TTFFT is the same information as FFTTF which along with our second attempt gives the same information as TTTTF with only one "false" is probably a bad idea. Thus for our third attempt we should use FTFTT. By a similar logic we can use FTTFT for our fourth attempt.
So our exams are TTTTT, FFTTT, FTFTT, FTTFT. The first one give us the number of "true" answers. Adding up the second, third, and fourth mod 2, we can determine the answer to question 5 (as a "true" in one of the first four question contributes 0 mod 2, while a "false" contributes 1 mod 2). Next, going from TTTTT to FFTTT you either gained 2 points, lost 2 points, or stayed the same If you gained or last 2, you know the answers to the first two questions and finishing things off is easy, if you stayed the same then exactly one of the first two questions is true while the other is false. Similarly, TTTTT and FTFTT tells you if questions 1 and 3 are both true or false (easy to solve) or 1 of each. And same for questions 1 and 4. The only hard case is if your score never went up or down, but in that case exactly one of 1 and 2 is true, exactly one of 1 and 3 is true, and exactly one of 1 and 4 is true, thus the only cases are TFFF or FTTT and our base case will distinguish those.
This completes the proof that you can do 30 questions in 24 attempts. Note that this strategy was non-adaptive, in the sense that I never used the information gained from submitting one exam to decide my questions for the next exam. I could have just submitted my 24 exams in any order and then studied them to get my answers. One can in theory make more powerful strategies by using adaptive strategies, by using information you gain along the way to adjust what you are doing, but then the strategy tree is way harder to figure out, because it is theoretically very large.
Alright, remember last time I said it is important to solve the simpler case of 5 questions with 4 attempts, so lets assume that we already have the ability to do that (I will show how later) and then use that to solve the problem of 30 questions. Without any loss of generality, we might as well have Victor answer "true" to all the questions first, to establish a base case. Next, we can submit the first 5 as "false" and the other 25 as "true" to get a base case for the first 5 questions (which we can then solve independently in 4 attempts), next we do the next batch of 5 as "false" with the rest "true" to get a base case for the next 5 and solve those in 4 more attempts. When we get to the last batch of 5, we don't need to do a final base case for those ones, as we already had our initial base case to tell us how many true answers are on the test in total, and we knew how many true were in each other block of 5, so we have already found our base for the last 5 questions. This argument shows quite generally that if you can do Q questions in N attempts then you can do MQ questions in MN attempts (for our case Q=5, N=4, M=6).
Now, how do we do 5 questions in 4 attempts? First we spend one attempt on our base case to see how many answers are "true", so we submit TTTTT. For the other 3 attempts, we will switch some of the answers to "false". There is no need to switch 3 of them to "false", as you get the same information by taking the compliment and switching the other 2 of them to "false". Similarly switching 4 or 5 to "false" is also meaningless, so we need only worry about 1 or 2. If we use FTTTT for our second attempt, we will get the answer to the first question and have 2 more attempts to solve out the remaining 4 questions, seems sort of hard (is in fact impossible, but I'm not going to prove that), so for our second attempt we must flip two answers to "false". Thus we can use FFTTT as our second test.
For our third test, we can basically choose between TTFFT ad FTFTT, depending on if we want our third attempt to have any overlap with our second attempt. But TTFFT is the same information as FFTTF which along with our second attempt gives the same information as TTTTF with only one "false" is probably a bad idea. Thus for our third attempt we should use FTFTT. By a similar logic we can use FTTFT for our fourth attempt.
So our exams are TTTTT, FFTTT, FTFTT, FTTFT. The first one give us the number of "true" answers. Adding up the second, third, and fourth mod 2, we can determine the answer to question 5 (as a "true" in one of the first four question contributes 0 mod 2, while a "false" contributes 1 mod 2). Next, going from TTTTT to FFTTT you either gained 2 points, lost 2 points, or stayed the same If you gained or last 2, you know the answers to the first two questions and finishing things off is easy, if you stayed the same then exactly one of the first two questions is true while the other is false. Similarly, TTTTT and FTFTT tells you if questions 1 and 3 are both true or false (easy to solve) or 1 of each. And same for questions 1 and 4. The only hard case is if your score never went up or down, but in that case exactly one of 1 and 2 is true, exactly one of 1 and 3 is true, and exactly one of 1 and 4 is true, thus the only cases are TFFF or FTTT and our base case will distinguish those.
This completes the proof that you can do 30 questions in 24 attempts. Note that this strategy was non-adaptive, in the sense that I never used the information gained from submitting one exam to decide my questions for the next exam. I could have just submitted my 24 exams in any order and then studied them to get my answers. One can in theory make more powerful strategies by using adaptive strategies, by using information you gain along the way to adjust what you are doing, but then the strategy tree is way harder to figure out, because it is theoretically very large.
Bulls And Cows
I suspect that there might be only finitely many logic puzzles in the universe that I find interesting, because they seem to be running out at an alarming rate. Anyway, Tanya Khovanova had an interesting one a few weeks back that I might as well put here:
Naturally one can generalize this puzzle to Q questions and N attempts at the test. This game is actually just mastermind with two colours. One important simpler case is 5 questions, 4 attempts, I say that case is important because you can use it to solve this one of Q=30, N=24.
Tanya actually did a very nice explanation of the answer and some side calculations, when I post my answer I will basically just be copying what she wrote, but I like having an archive of stuff I find interesting, so I want this puzzle to be posted here.
A test consists of 30 true or false questions. Victor will take the test but starts off having no idea what any answers are. After taking the test, Victor gets his score: the number of correct answers. He is allowed to re-take the same test several times. Can Victor work out a strategy that guarantees that he can figure out all the answers after the 24th attempt?Note that Victor does not need to get everything right on the 24th attempt, just that he needs to know all the correct answers (so that on a 25th take, he would get them all right).
Naturally one can generalize this puzzle to Q questions and N attempts at the test. This game is actually just mastermind with two colours. One important simpler case is 5 questions, 4 attempts, I say that case is important because you can use it to solve this one of Q=30, N=24.
Tanya actually did a very nice explanation of the answer and some side calculations, when I post my answer I will basically just be copying what she wrote, but I like having an archive of stuff I find interesting, so I want this puzzle to be posted here.
Subscribe to:
Posts (Atom)
