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.
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:
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.
Subscribe to:
Posts (Atom)
