You have four pointlike frogs on an infinite two-dimensional plane. The frogs begin situated at the corners of a square, and at any time a legal move for the frogs is to jump over another frog to exactly the opposite side, such that the other frog was exactly in the middle of the jump. Show whether it is possible to ever have a configuration such that three frogs lie in a single straight line.I probably don't need to clarify much, but just in case I'll give an example; a frog located at (1,1) jumping over a frog located at (3,4) would jump to (5,7), since (3,4) is exactly in the middle of (1,1) and (5,7).
Frogs On A Plane
New puzzle time, I first found this one in the math club room on KGS:
Odd Coins
So, apparently I just stop blogging when I have a semi-academic job, but don't have an office to go with it. Anyway, its about time for the solution to the coin puzzle from last time.
So, I suspect that somebody who works with the Fibonacci numbers alot will not really have much of a problem with this puzzle, there are a reasonable number of relationships the Fibonacci numbers obey that make the puzzle quite straightforward. First of all, I will give my definition of the Fibonacci numbers for the purpose of this puzzle:
f1=1 f2=2 fk=fk-1+fk-2I call this "my definition for the purpose of this puzzle" because nobody would ever normally start the Fibonacci numbers off with 1 and 2, 1 and 1 is most common, and 0 and 1 sometimes, but 1 and 2 is being chosen for this so that there are no repeats in the sequence {fk} for k>0. Next, I will derive an identity that will be needed for the solution:
2fk=fk+fk-1+fk-2 =fk+1+fk-2A short derivation, but an important one. Alright, now suppose the set of Fibonacci numbers is not a greedy set. Then there is a number C such that C can be expressed as a sum of K Fibonacci numbers {fi1,fi2,...fiK} and the greedy algorithm uses at least K+1 such numbers. We will assume that C is chosen to be the smallest such number (if any exist, there must be a smallest one). Naturally C is not one of the fn, so let M be the largest number such that fM<C. I claim that fM is not in the list {fi1,fi2,...fiK}. If it were, then the greedy algorithm would use the coin fM and then optimize C-fM. However, the list {fi1,fi2,...fiK} adds to C and so if it contains fM then C-fM can be expressed using K-1 Fibonacci numbers, but the greedy algorithm would be able to optimize this, as C was the smallest counterexample. Alright, so we have proven that the list {fi1,fi2,...fiK} does not contain fM. It is also obvious that it does not contain two consecutive Fibonacci numbers (if it did, we could make it more efficient). Finally, it can be made to not contain the same number twice, for if it did we could use our earlier identity to replace 2fk with fk+1 and fk-2. I claim that a list of Fibonacci numbers fj with J less than M with no consecutive numbers and no repeats cannot add to larger than fM. This can be proven as follows:
fM=fM-1+fM-2 =fM-1+fM-3+fM-4 =fM-1+fM-3+fM-5+fM-6Continue on this logic, until you get down to f1. We see that our list {fi1,fi2,...fiK} cannot add to larger than fM, but C was larger than fM, so we have a contradiction, proving there is no smallest counterexample. Thats all I got for now, I might post the full solution to the greedy sets of the form {1,a,b} next time, or I might just move on to a new puzzle, we will see.
Greedy Coins
Time for a new puzzle. As seems to be the constant state these days, I am running out of puzzles and as such I am digging up all the weird ones I remember. Actually, I rather enjoyed this one, but it is more mathematical than most of my puzzles. I first learned this one from Bart:
Consider the problem of making change for a certian amount of money, given a set of coins that you can select from. You have a target number x, and you wish to construct x by using elements from a set S (so S could be the set {1,5,10,25} for example). In particular we wish to reach the target number using a few coins as possible, so making 23 with 10+10+1+1+1 is considered more optimal than using 10+5+5+1+1+1. This is known as the change-making problem. There are plenty of good solutions for the change-making problem, but let us consider a special style of solution, which is known as the "greedy algorithm". This algorithm is to always take the largest available coin that is smaller than your target number and the reduce the target number by that amount. As an example of this algorithm, lets try to make 28 is the set {1,5,10}, we first take 10, now we want to reach 18, so we take another 10, now we want to reach 8 so we take 5 and finally to get 3 we use 1 three times, thus the algorithm gives us the solution 10+10+5+1+1+1, which you can convince yourself is optimal for this case. For another example we can consider the set {1,4,5} and try to reach target number 8. The greedy algorithm gives us 5+1+1+1, but we can see that 4+4 is a better solution, so in this case the greedy algorithm does not give us the optimal solution. With some sets of numbers, such as {1,5,10,25} the greedy algorithm will always give the optimal solution, but with others such as {1,4,5} it will not (lets not ask what happens if the number 1 is not in our coin set). With some sets, like reaching 4 with {1,2,3} the greedy algorithm gives an optimal solution, but not the only solution, so 4=1+3 but also 4=2+2. We will call a set of natural numbers "greedy" if the greedy algorithm always gives an optimal solution for the change-making problem. Consider the set of numbers that occur in the Fibonacci sequence, call this set F. The puzzle is prove that F is a greedy set.If you don't know what the Fibonacci sequence is then I am astounded that you are even reading this blog, but anyway, it should be pretty easy to look it up on the internets somewhere. One can ask the much more general question of "classify all greedy sets", but that is actually really hard and if you can do that, I suggest you publish. You can try to solve out the classification of all greedy sets of the form {1,a,b} though, that actually has a somewhat nice answer.
Lines On A Plane
So, when I posted that dots puzzle from last time (like a month ago, you may remember) I hadn't fully thought out the solution and didn't realise just how simple it could be. Anyway, lets take a look at it now.
The original puzzle was worded to have 10 dots such that they "made 5 lines of 4," which struck me as slightly ambiguous, and my initial solution was just using 8 dots in a row and the 5 lines of 4 were all colinear. The initial intended solution is to place the dots at the vertices of a 5-pointed star, a rather pretty solution and if you don't think about it too much seems like it might be the unique solution.
When I was working on it, the solution I found was to place 4 points down vertically, call them a,b,c,d. Next put 3 horizontal from d, call them e,f,g. Next draw lines from a to e, b to f, and c to g (and set things up so that those three lines don't all intersect at a point). The three intersections of those lines define where to put the other three of our ten points. Not a particularily elegant solution, but its what I did.
To try for the general class of solution first let us consider that we have a solution and we number the lines 1 through 5. Now, count the points as the lines go through them. It must be the case that you counted 20 points, as each of the 5 lines went through 4 points, so on average each point was counted twice. With all the solutions we have seen so far we have each point touched by exactly 2 lines, is it poissible to have one touched by 1 or 3?
If it is possible to have a point that has 3 lines going through it, then let us assume lines 1,2, and 3 go through that point and call it O. Line 1 also goes through a,b,c,O, line 2 also goes through d,e,f,O (def must be distinct from abc or line 1 and line 2 would have two points in common and therefore be the same line) and line 3 goes through g,h,i,O (again distinct from abc and def) This accounts for all ten of our points. Now a fourth line cannot go through two of a,b,c, also cannot go through two of d,e,f, and also cannot go through two of g,h,i, which means it cannot go through four points, a contradiction.
This proves that each point must be met by exactly two of the lines. Actually, the problem is much trivialized if you just try to place the lines first. Place any 5 lines on the plane such that no three of them share a point (if you place them randomly, it will almost certianly be good) and those lines define 10 points (thats 5 choose 2). So those 10 points are where you put your points.
If you wanted to obfuscate this problem a little, it would probably be best to reword it as "Place 10 unique points on the plane such that one could place 5 unique lines on the place with each line passing through 4 points." You could also generalise the problem to N lines and N choose 2 points, but that would probably be contrary to the goal of obfuscation.
Dots On A Plane
Alright, time for a new puzzle, its a bit of a weird geometry one I learned from Brandon, but its sort of neat:
Place 10 distinct points and 5 distinct lines on an infinite plane such that each line goes through exactly 4 points.Fairly simple to word, note that the lines must be infinte and go through exactly 4 points so that having 5 points in a row does not count as two lines going through 4 points. If you want to do a more advanced version, try to classify the set of all possible solutions to this puzzle, I still haven't done this but hopefully I will before I get around to posting the solution.
Halfway
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.
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.
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.
Same As Before
Ok, time to solve out the weighing medals problem from last time.
First, its easy to see that the gold medal will never be on the scale, there is nothing to balance it against, so we might as well throw it away and if we can't find the fake in the others then the fake was the gold medal. Next, note that we can't leave all the silvers off the first weighing, because then they must all go on the second weighing (since the gold is never being weighed, we must weigh everything else at least once or we can't find the fake) and there is no way to divide up the 3 silvers into two piles. Similarly, we must put at least one bronze on the first weighing.
It makes the most sense to weigh 2 bronze and 1 silver against 2 bronze and 1 silver for our first one, this way, if one side is heavy we have immediately identified 2 bronze and 1 silver as the "suspect group". We can use our second measurement to weigh the two suspect bronze against eachother and figure our which of the three medals is the fake.
If our first measurement comes out balanced, we have the gold, 1 bronze, and 1 silver as our suspect group. We put the suspect bronze with a genuine silver on the left against the suspect silver and a genuine bronze. Now 'left heavy' 'right heavy' and 'balanced' all point to a unique medal.
This solves the problem, and as stated isn't very difficult. What I found sort of cool was if you reconsider that solution without the different types of medals. It is just the 9 coins and 2 weighings problem and you start by weighing 3 vs 3 to get a suspect group of size 3. Of course, if the solution to the different medals problem is to work for arbitrary values of masses of genuine medals mbronze, msilver, mgold, then it must work in the particular case where all those m's are equal (I suppose this isn't true if your solution divided by mbronze-msilver or something, but we aren't doing that).
Anyway, thats all I got.
First, its easy to see that the gold medal will never be on the scale, there is nothing to balance it against, so we might as well throw it away and if we can't find the fake in the others then the fake was the gold medal. Next, note that we can't leave all the silvers off the first weighing, because then they must all go on the second weighing (since the gold is never being weighed, we must weigh everything else at least once or we can't find the fake) and there is no way to divide up the 3 silvers into two piles. Similarly, we must put at least one bronze on the first weighing.
It makes the most sense to weigh 2 bronze and 1 silver against 2 bronze and 1 silver for our first one, this way, if one side is heavy we have immediately identified 2 bronze and 1 silver as the "suspect group". We can use our second measurement to weigh the two suspect bronze against eachother and figure our which of the three medals is the fake.
If our first measurement comes out balanced, we have the gold, 1 bronze, and 1 silver as our suspect group. We put the suspect bronze with a genuine silver on the left against the suspect silver and a genuine bronze. Now 'left heavy' 'right heavy' and 'balanced' all point to a unique medal.
This solves the problem, and as stated isn't very difficult. What I found sort of cool was if you reconsider that solution without the different types of medals. It is just the 9 coins and 2 weighings problem and you start by weighing 3 vs 3 to get a suspect group of size 3. Of course, if the solution to the different medals problem is to work for arbitrary values of masses of genuine medals mbronze, msilver, mgold, then it must work in the particular case where all those m's are equal (I suppose this isn't true if your solution divided by mbronze-msilver or something, but we aren't doing that).
Anyway, thats all I got.
Subscribe to:
Posts (Atom)
