Puzzle thread? Puzzle thread.

[Xei]

As anybody who frequents chat knows, I freakin' love puzzles. Everybody loves puzzles! But there's a lot of crap out there, and there's nothing more annoying than spending hours steaming your noodles only to find that it's some kind of lame trick question. So I thought it'd be a good idea to create a thread where we can share really good ones and tackle them together. Puzzles involving creative or clever thinking are what we want. There should be one answer, and you should know it when you get it. The best ones should seem impenetrable, until you receive a sudden flash of inspiration. Word riddles are fine, as long as they satisfy the above. I'll post a few favourites off the top of my head to get the ball rolling. Please don't spoil any you've seen before. The field and the farmer You love sweetcorn. You're sat in the middle of a circular sweetcorn field, eating some sweetcorn. There is a path around the circular sweetcorn field, upon which rides an angry old sweetcorn farmer with a pitchfork, on a tricycle. The tricycle moves 4 times as fast as you do, but it cannot go off-road. Can you definitely escape? The prisoners and the light There are 20 prisoners in a prison. The warden of the prison is slightly insane, so one day, he takes all the prisoners outside into the yard and tells them the following. From now on, once every day, he will select a random prisoner, and take them from their cell to a disused bathroom. In the room is a switch; this switch turns the room's light on and off. Then he'll take the prisoner back to their cell. At any time, any prisoner may say to the warden, "we have all been to the bathroom now". If that prisoner is right, they're all freed. If the prisoner is wrong, they're all fed to the prison dogs. They all have an hour to talk to each other and form a plan, before they're taken back inside the prison, where they can't communicate. What do they do? The coins and the table You are blindfolded in a room with a table in the middle. Scattered across the floor are several thick gold coins. You're told that half are heads up and half are tails up, but you don't know and can't tell which each individual coin is. To win the coins, you must put some of them on the table, in such a way that the number of heads on the table is the same as the number of heads on the floor. Can you do it?

[tommo]

First one. Spoiler for ewrwe: No, I don't think so. If I start at one edge and run to the other (maximising the distance he must go, while also minimising the distance I must go), say it is 10m diameter. He will have to go (c= pi X d)/2 which is 15.7m and I will go 10m, obviously. At 1m p/s it will take me 10 seconds to get to the other side. At 4m p/s it will take him 3.9 seconds.

[Arra]

First one. Spoiler for ewrwe: No, I don't think so. If I start at one edge and run to the other (maximising the distance he must go, while also minimising the distance I must go), say it is 10m diameter. He will have to go (c= pi X d)/2 which is 15.7m and I will go 10m, obviously. At 1m p/s it will take me 10 seconds to get to the other side. At 4m p/s it will take him 3.9 seconds. Yeah, but you're discounting alternatives. Like if you run to almost the end, and he follows you, then at the last moment you run another direction. I haven't figured this one out yet, but I have a feeling it has an answer. Oh, and, for the second two, I do have 'answers' but I think they're likely bs. I started typing them out once and gave up. For the prison one, how about every person just make a scratch on the wall when they go in? Then when someone sees 19 scratches, he'll know that he's the last. For the coin one, just put all the coins on the ground in the same area, then turn the table upside down onto those coins. Then all the coins will be on the table and on the ground. (Or gather up all the coins, and then 0 will be on the table and on the ground, but that may not be allowed since you said 'you must put some of them on the table'.

[Xei]

Hah, the table thing's genius. Though if that was the answer, I'd've thought the person asking it was a bit of an asshole, 'cos that's kinda a trick question. No, it's too heavy to lift or whatever, and the coins have to either be on the table or be on the floor. Moving them about is all you can do. If that was the answer to the prisoner one I'd definitely be an asshole. No, you can't make any marks or anything. It's all about the light. Light on and light off is the only information involved. First one. Spoiler for ewrwe: No, I don't think so. If I start at one edge and run to the other (maximising the distance he must go, while also minimising the distance I must go), say it is 10m diameter. He will have to go (c= pi X d)/2 which is 15.7m and I will go 10m, obviously. At 1m p/s it will take me 10 seconds to get to the other side. At 4m p/s it will take him 3.9 seconds. Good try, but like Dianeva says, there are alternatives. Though it seems sensible, it turns out that the assumption that the shortest path is the best you can possibly isn't right. If anybody knows any good ones please share, I don't want this to be a "Xei knows the answer and you are dumb" thread.

[Kraom]

Well, the question for the last one says, "can you do it." So, yes, by luck, puzzle solved.

[Chimpertainment]

My guesses: Field and Farmer: Go to the edge where the farmer comes close to you, then run the opposite direction he is facing so he has to go around the entire circle to catch up... 20 prisoners: If they are in the same block, they could count each time they hear the doors to their cells open. Coins on the table: Flip all the coins...put half on the table and half on the floor... Random Riddle from the intarwebs... "A farmer challenges an engineer, a physicist, and a mathematician to fence off the largest amount of area using the least amount of fence. The engineer made his fence in a circle and said it was the most efficient. The physicist made a long line and said that the length was infinite. Then he said that fencing half of the Earth was the best. The mathematician laughed at the others and with his design, beat the others. What did he do?"

[tommo]

Yeah, but you're discounting alternatives. Like if you run to almost the end, and he follows you, then at the last moment you run another direction. Yes, I was thinking this as I was going to sleep last night. But.... still I don't know if that would work. It really depends how he follows you. I mean if you run in a tiny circle, and he constantly tries to keep the shortest distance to you by going around the entire circle, then yeah, you could maybe get out while he's still trying to catch up. But that would just stupid. So assuming it's a real person, that for some reason can't go inside the circle, and not an automaton, then you can't. I mean even if I take a 1cm step in one direction, he goes around to the side I'm closest to, and then I run in the other direction, it will still take me 5 seconds and him 3.9 seconds. Good try, but like Dianeva says, there are alternatives. Though it seems sensible, it turns out that the assumption that the shortest path is the best you can possibly isn't right. Well, the assumption was the shortest path while maximising the length of his path. Prison light one "What do they do?" Kill the guard when he takes the first guy to the bathroom. Spoiler for seriously though it's quite simple: Assuming he can't take the same prisoner twice. After twenty days the prisoner taken on that day can go to the bathroom and then tell him they've all been there

[Arra]

This is so frustrating. I can't stop thinking about these puzzles. I was just playing a 2 hour game of l4d and was terrible because I was just thinking about that fucking light switch one the whole time. For the first, I've realized it's hard to come up with a solution without knowing the algorithm the farmer is following. Does he always stay as close to you as possible? Or if he sees you running in a direction, will he assume you're headed for the other side in a straight line and head for the other end? Or are you just supposed to assume he could go anywhere? If so, there can't be a solution using any definite path, as he could always just place himself at your planned point of exit, from the beginning. So the solution may be some algorithm that will depend on where he goes, which would get complicated. The prisoners. I may have somewhat of a solution which is probably inadequate. Spoiler for Prisoners solution: They consider time in segments of some number of days. The greater the number of days, the longer it will take, but it will be more likely that it will end up working eventually. I'll pretend it's a month, but it should probably be more than that. If this is the first time the person has been to the bathroom with the light off when he entered, he leaves the light on for the next person. Otherwise, the person leaves the light unchanged. At the end of the month, the last person turns the light off. This way, each month, if someone new has been to the bathroom, everyone who went after he did will know because they saw the light on. So each person just has to wait until they've witnessed the light on in 19 separate months. But this isn't a perfect solution. Not only would it take a really long time (19 months minimum), but it isn't guaranteed to work. Like if the warden chose to focus on the same group of 10 people for one month, then the next 10 the next month, and keep alternating, then neither group could be aware of the other being there. EDIT: !!! This is getting so fucking complicated! I've realized that might not really work well unless someone near the beginning of the month turns the light on. Because if the person on the last day or so turns the light on, there will be hardly anyone to see it before it's turned off again. But there's no way to signal that the whole process should start over if the light isn't turned on early enough.... maybe each prisoner should turn the light on his first time in the bathroom with the light off, only if it's in the first few days of the month. Otherwise he should save his statement for a time he's chosen earlier in the month, so more people will see it. I suppose you could use math to come up with some span of days that will make it extremely likely that at least one person will witness all 19 switches being turned on... I don't feel like doing that now though. And the coin one... I don't see how there can be a solution to that. No matter what you do to the coins, you can never know which ones are heads. I can't even think of some indirect way to do it. If you pick up more than half of them, you know that you have at least one heads and one tails. That's about as far as I can imagine knowing something that might seem unintuitive. I don't know where you could go from there though. "A farmer challenges an engineer, a physicist, and a mathematician to fence off the largest amount of area using the least amount of fence. The engineer made his fence in a circle and said it was the most efficient. The physicist made a long line and said that the length was infinite. Then he said that fencing half of the Earth was the best. The mathematician laughed at the others and with his design, beat the others. What did he do?" Don't do anything, say the fenced area is infinitely small but it's really the outside and everything outside of it (ie. all space) is being fenced off?

[tommo]

Actually just realised a possible solution to the coin one as well Spoiler for efwe: put all the coins on their edges like _O_ that, standing up, there are 0 heads on the table and 0 on the floor.

[Xei]

I'm glad you're enjoying them. The light switch one pestered me for about two days and nights, lol. Though I simplified the puzzle slightly. My guesses: Field and Farmer: Go to the edge where the farmer comes close to you, then run the opposite direction he is facing so he has to go around the entire circle to catch up... The farmer can turn around. He can also slow down and stop of course, as can you. 4 times your max speed is his max speed. 20 prisoners: If they are in the same block, they could count each time they hear the doors to their cells open. But they might just hear the same person going 20 times. The light is their only means of communication. Coins on the table: Flip all the coins...put half on the table and half on the floor... Half are heads and half are tails. If you flip them all this is still the case. But the half you put on the table could all be heads, for instance. Then all the heads would be on the table, and no heads on the floor. Random Riddle from the intarwebs... "A farmer challenges an engineer, a physicist, and a mathematician to fence off the largest amount of area using the least amount of fence. The engineer made his fence in a circle and said it was the most efficient. The physicist made a long line and said that the length was infinite. Then he said that fencing half of the Earth was the best. The mathematician laughed at the others and with his design, beat the others. What did he do?" I can't really tell what the physicist is supposed to have done... and I don't know what "fence off the largest about of area using the least amount of fence" means. Who wins if one person has a larger area but lots of fence and another has a small area but a small amount of fence? My vague guess at the moment is basically what Dianeva said. I mean even if I take a 1cm step in one direction, he goes around to the side I'm closest to, and then I run in the other direction, it will still take me 5 seconds and him 3.9 seconds. That's all true, and you're thinking along the right lines, but perhaps there is a better technique. After twenty days the prisoner taken on that day can go to the bathroom and then tell him they've all been there. The prisoners are selected at random - so repeats are allowed. Though you can be sure that they'll all be picked eventually. It may take a very long time... but you can assume that the prisoners don't die by then. put all the coins on their edges like _O_ that, standing up, there are 0 heads on the table and 0 on the floor. Dang, that's another good answer. I shouldn't have mentioned that the coins are thick, it's actually irrelevant. So... yeah, say that have curved edges or whatever and can't be balanced. Heads or tails only, sorry. I promise it is possible with a few simple steps. It's probably a good idea to focus on this one first, actually. For the first, I've realized it's hard to come up with a solution without knowing the algorithm the farmer is following. Does he always stay as close to you as possible? Or if he sees you running in a direction, will he assume you're headed for the other side in a straight line and head for the other end? Or are you just supposed to assume he could go anywhere? If so, there can't be a solution using any definite path, as he could always just place himself at your planned point of exit, from the beginning. So the solution may be some algorithm that will depend on where he goes, which would get complicated. Yeah these are all good questions and insights. Basically the farmer may use any of those plans. But there may be a way to beat him no matter what he does. That's what the question's asking for. Can you always beat him no matter what he does? Or can he always beat you no matter what you do? I promise the answer doesn't use a complicated algorithm. Just a simple idea. The prisoners. I may have somewhat of a solution which is probably inadequate. Spoiler for Prisoners solution: They consider time in segments of some number of days. The greater the number of days, the longer it will take, but it will be more likely that it will end up working eventually. I'll pretend it's a month, but it should probably be more than that. If this is the first time the person has been to the bathroom with the light off when he entered, he leaves the light on for the next person. Otherwise, the person leaves the light unchanged. At the end of the month, the last person turns the light off. This way, each month, if someone new has been to the bathroom, everyone who went after he did will know because they saw the light on. So each person just has to wait until they've witnessed the light on in 19 separate months. But this isn't a perfect solution. Not only would it take a really long time (19 months minimum), but it isn't guaranteed to work. Like if the warden chose to focus on the same group of 10 people for one month, then the next 10 the next month, and keep alternating, then neither group could be aware of the other being there. EDIT: !!! This is getting so fucking complicated! I've realized that might not really work well unless someone near the beginning of the month turns the light on. Because if the person on the last day or so turns the light on, there will be hardly anyone to see it before it's turned off again. But there's no way to signal that the whole process should start over if the light isn't turned on early enough.... maybe each prisoner should turn the light on his first time in the bathroom with the light off, only if it's in the first few days of the month. Otherwise he should save his statement for a time he's chosen earlier in the month, so more people will see it. I suppose you could use math to come up with some span of days that will make it extremely likely that at least one person will witness all 19 switches being turned on... I don't feel like doing that now though. Yes, the really big problem with this method is that, even if a new prisoner turned the light on at the start of the month, it seems quite unlikely that any one prisoner would get to visit the bathroom every single month (it's around 1% I think), and so there would be at least one prisoner they didn't count. In any case, it's definitely not certain. Even if you changed it from a month to a year, you still couldn't be certain. The answer uses quite a simple idea which will certainly work, but it took me a long while to stumble across it. But it looks like you're thinking along the right lines.

[reci]

Hm.. is the farmer one, Spoiler for possible solution: No, you cannot escape because r > pi*r/4 => 1 > ~0.785. This assumes you start in the center and dart opposite the direction of the farmer's initial position. Right? Or, Spoiler for ...: would the optimal path be a spiral? Though, you still probably wouldn't be able to escape, but don't ask to prove this; I've forgotten my polar maths.

[Arra]

Hm.. is the farmer one, Spoiler for possible solution: No, you cannot escape because r > pi*r/4 => 1 > ~0.785. This assumes you start in the center and dart opposite the direction of the farmer's initial position. Right? I don't know the answer but I know this isn't it, since you can't make assumptions. Unless it really is impossible. Or, Spoiler for ...: would the optimal path be a spiral? Though, you still probably wouldn't be able to escape, but don't ask to prove this; I've forgotten my polar maths. I was thinking that too but that wouldn't work either. If the farmer could do anything he could just go to your point of exit, so no planned path would work.

[Nelzi]

For the coins: just place half of them on the table and flip them (only those on the table). I liked it, had a big smile on my face, when I got that insight Wow the farmer is cool too : lets say the radius is 100 m, then: -> the farmer's circle has a length of 628,3 m -> go out 22 m from the center. You are now on a smaller circle with total length 138,2 m, which is less than one fourth of the farmers total length. So you can get on his opposite side by following your smaller, inner circle, even though he is 4 times as fast! -> now your shortest path to freedom is 78 m, while the farmer still has to travel half his circle to reach that point. While you run the 78 m, he will travel 78 x 4 = 312 m on his path, which is about 2 m less than half his circle! -> hope his pitchfork is less than 2 m long! The prisoner lights will keep me awake though (why post insomnia inducing riddles in a dreaming forum btw?). I enjoy this thread, will try to find riddles also...

[DuB]

Farmer problem My first thought was that you could not escape the farmer, because he can outpace you by a factor of pi or greater. So he can ride further than the circumference of a semicircle in the same time that it takes you to run the radius of that same circle. If you simply run in a straight line, he will always catch you. But then I scrolled down and read Xei's hint about running in a straight line not necessarily being the best strategy. After considering this hint, I believe I have a solution. The solution is quite easy to visualize, but turned out to be slightly long and complicated to explain in words, or at least to do so in any kind of thorough way. Some of this could probably be simplified, but it's late... Spoiler for farmer solution: TL, DR: The path that you end up running to escape the farmer involves running an outward-spiraling curve from the center to just past pi/4 radius lengths from the center, at which point you can turn and dash in a straight line directly away from the center and out of the corn field. We have already established that running in a straight line away from the farmer's initial position will not work. However, if you had a "head start" such that you did not have to run the full radius of the circle, but instead only had to run less than pi/4 of the radius of the circle, then from there you could escape the farmer by running in a straight line. So if we can show that there is a way to get yourself into the position of being pi/4 radius lengths from the edge of the circle, and with the farmer on the edge directly opposite the center of the circle from you, then we will have shown that you can escape the farmer. Let's call this position the "safe zone." It turns out there is a way to successfully get to the safe zone. The trick is to run not in a straight line, but instead to run along a path such that, at any given instant, you are headed directly away from the farmer's current or instantaneous position. This leads to you running a curved, outward-spiraling sort of path. (The curve arises because the farmer will presumably be racing around the edge of the cornfield trying to get closer to you, rather than just sitting still. Obviously the problem is trivial if he just sits still.) But of course, you can't keep up this spiraling sort of path the entire way out to the edge of the circle. Because the farmer's pace exceeds yours, there will necessarily be a point in this spiral path at which you will no longer be able to approach the edge of the circle, at any angle, and still also be running directly away from the farmer's instantaneous location. Basically, there is a smaller, inner circle within which you can run on such a path, and outside of which you are not physically able to do so. Let's call this inner circle the "spiral zone," for lack of a more creative name. If there is any overlap between the spiral zone and the safe zone, then you can always reach the safe zone by using this spiraling strategy, and therefore you can always escape the farmer. Below I show that the spiral zone and the safe zone do in fact overlap. Letting r = the radius of the circular corn field, the distance from the center of the circle to the safe zone is r - pi*r/4 = r(1 - pi/4). The circle defining the spiral zone has radius r/4. We know this because the farmer can outpace you by a factor of 4, so in the time it takes him to travel the circumference of his circle (or any fraction thereof), you can in that same time travel the circumference of a circle (or any fraction thereof) that has at most 1/4 the radius of his circle. That smaller circle, of course, is what defines the spiral zone. So anyway, this all means that the distance from the center of the circle to the edge of the spiral zone is r/4. We can rewrite r/4 as r(1 - 3/4), which makes it easy to compare to r(1 - pi/4), which was the distance from the center of the circle to the safe zone. Because pi > 3, the distance from the center to the edge of the spiral zone exceeds the distance from the center to the safe zone, therefore the safe zone and the spiral zone overlap (barely in this case), therefore you can always escape the farmer. The path that you end up running to do so entails running an outward-spiraling curve from the center to just past pi/4 from the center, at which point you run in a straight line away from the center and out of the corn field. I will probably look at the others later. As of now I haven't even looked, to prevent myself from spending time trying to solve them right now... I am supposed to be pulling an all-nighter getting important work done, not solving silly puzzles

[GooseMan]

So much math for the farmer problem o.o How about this for the farmer one: Spoiler for The Answer!: What if you take the sweetcorn and lay it across the path. He wouldn't be able to go over it because he can't go offroad. So just make a path for yourself to walk on that is thick enough so you don't get stabbed by his pitchfork.

[Arra]

For the coins: just place half of them on the table and flip them (only those on the table). I liked it, had a big smile on my face, when I got that insight Kind of mad at myself for not getting this one earlier. The answer was so simple.

[DuB]

Just looked at Nelzi's farmer solution. I didn't check the exact figures but it appears to be basically the same idea that I elaborated. I guess you won't be surprised to hear that I think it's missing some rather important details, but then maybe I am just overly verbose . Maybe I'm missing something but I don't see how Nelzi's coin solution does the trick. It clearly works in expectation -- that is, the most likely number of heads remaining on the floor after you pick up half of the coins is 1/2 of the original total -- and likewise the most likely number of heads on the table after you flip that half of the coins is again 1/2 of the total -- but for any one particular attempt there is no guarantee that the two numbers of heads will be equal. In fact, if the total number of coins is large, the strategy will very rarely work on any given attempt. My feeling right now is that anything involving flipping the coins is not going to be a good way to go, because it introduces additional uncertainty into the situation. But I'll think on it some more. Edit: I see that reci hit on one of my ideas for the farmer solution as well.

[DuB]

I've got the coin one. Spoiler for coin solution: Take each coin and place it on the table, without turning it over, one at a time so that, one by one, you eventually transfer every coin from the floor to the table. No matter which coins you pick in which order, at some point the number of heads on the table has to equal the number of heads on the floor, assuming that there are an even number of heads (which I guess we can assume, because the task is impossible if there are an odd number of heads). Of course, you won't be aware at exactly what point you have satisfied the task, since you can't see the coins... Edit: ....actually this solution doesn't work in the general case. It works under the assumption that I state, but I see now that my reasoning in justifying the assumption is wrong, and the assumption need not hold.

[Darkmatters]

^ I think you're overcomplicating it. No matter how I figure it, putting half the coins on the table and flipping them works. Let's say you have 20 coins in all - 10 heads, 10 tails on the floor to begin with. Pick up 1 head and 9 tails, leaving 9 heads and 1 tail on the floor. Of course, when you flip the ones you picked up, you have the same on the table. Pick up 2 heads and 8 tails - same thing happens. It leaves 8 heads and 2 tails on the floor, and that's what you get on the table when you flip them. Without actually running through it for every possible combination, it seems clear this will happen every time.

[DuB]

Oh, I see, I was misunderstanding what you meant by "flip." I assumed you meant to "toss" the coin (i.e., so that it lands with an equal chance of head or tails), but I guess you actually just mean to "turn it over" to the other side. Well, in that case, I like Nelzi's solution better than mine

[Darkmatters]

Hahaha yeah, if you had to literally flip them that would complicate things!

[DuB]

I also just figured out that my proposed coin solution is flawed... I edited the post. I will take all of this as a sign that I need to put the puzzles down and get back to work...

[Arra]

I want to figure out the light switch solution. If anyone posts that one I'm not going to look at it.

[Nelzi]

LOL guys... funny how you are still guessing on solutions after reading mine, because they actually work. To convince yourself of the coin solution, just pick some examples, just like Darkmatters did. And the farmer example I gave does also work, no matter what the farmer does... and yes it is basically the same idea as DuB had. For clarity (and without numbers - for GooseMan), the important insight is that you can find a small circle inside the field (with the same center as the field, think this is the 'spiral zone' suggested by DuB) with a circumference less than than one fourth of the field's circumference. So your speed in angle/time is greater than the farmers angle/time and you can get a head start equal to the inner circle's radius, which is enough to make it in the shortest path.

[Arra]

Well for the coin one, as DuB said he misunderstood what you meant by 'flip' (gets it now). No one else has tried to re-answer that one, so what are you talking about?