Slashdot Mirror
Your Favorite Math/Logic Riddles?
shma asks: "Whether you're involved in the Sciences, Mathematics, or Engineering, you undoubtedly enjoy finding simple solutions to seemingly difficult problems. I'm sure you all have a favorite mind-bender, and who better to share it with than the Slashdot community? Post your own problems and try to solve others. Just one request: If you have figured out the solution, link to it in a post, rather than write it out where anyone can see it." What brain benders tickle your fancy?
"Here's a sample to consider: You're in a dark room with 50 quarters, 18 of which are heads up. You are allowed to move around the coins or flip some or all of them, if you wish. Problem is, it's too dark to tell what you're moving or flipping (no, you can't figure it out by touch either). Your job is to split the coins into two groups, each of which has the same number of heads up coins. How do you accomplish this?"
You find yourself before indistinguishable two doors, each with a statue. One door will lead to salvation, the other to death. The statue that guards the door to salvation always tells the truth, the statue to the door to death always lies. You may pose only one question to only one statue. What do you ask to determine which door is which?
Answer(ROT13): Nfx nal dhrfgvba gb juvpu lbh nyernql xabj gur nafjre. Gb qrgrezvar juvpu qbbe vf juvpu lbh arrq gb xabj gur eryngvbafuvc bs gur nafjre lbh ner tvira gb gur gehgu. Gur guvat V yvxr nobhg guvf evqqyr vf vg sbeprf lbh gb pbafvqre gur bcrengbe va gur ybtvpny fgngrzrag gb or gur inevnoyr. Nqqvgvbanyyl crbcyr nera'g hfrq gb nfxvat dhrfgvbaf jura gurl nyernql xabj gur nafjre fb gurl graq abg gb or noyr gb guvax bs n fbyhgvba evtug njnl. Gur jubyr guvat orpbzrf boivbhf jura lbh cbfr n dhrfgvba fhpu nf "Ner gurer gjb fgnghrf urer?"
Simply place any 18 coins into the second group and flip those over.
If you flip a coin over that was heads, it is now tails and is eliminated from consideration. If you flip a coin over that was tails, it marks with heads a coin selected that was not heads. Therefore after 18 coins are flipped, the number of heads in the second pile is equal to the number of heads that are left in the first pile.
I came up with this solution in the shower. It has no pretense of being the optimal solution. Don't just say it's wrong; please reply with disproofs (especially the poster of the problem).
This solution requires that each prisoner is guaranteed to be called to the room infinite number of times. Otherwise, if there's a maximum number of times t that a prisoner can be called to the room, then the king could select k = number of prisoners, call each one t times in a row, resetting the chalice to original position every t-th time (the last time he calls in any given prisoner). This would guarantee that every prisoner wouldn't be able to see any changes to the chalice made by any other prisoner. Thus they wouldn't be able to know if anybody has been to the room but then.
1. Chalice has two states: 0 and 1.
2. Without loss of generality, assume 0 as the initial state. (Suppose k = k'. Assume initial state = 0 and k = k' + 1. If originally the initial state is 1, that's equivalent to the king using the extra flip out of k' + 1).
3. There is one head prisoner and n other prisoners.
4. The head prisoner always sets the chalice to 1.
5. The simple prisoners set the chalice to 0 the first M times they visit the room and see the chalice set to 1; they don't touch it afterwards.
6. The head prisoner declares that all prisoners have visited the room after he sees the chalice in 0 state N times.
Let's find out what M, and N are depending on k and n.
7. When the head prisoner sees the chalice in 0 state for the N-th time, the chalice has been set to 0 by simple prisoners at least N - k times and at most N + k times.
8. We know that N - k > M*(n - 1), otherwise one simple prisoner might have never visited the room.
9. We also know that M*n > N + k, otherwise the simple prisoners may stop setting the chalice to 0 before the head prisoner ever gets to see 0 state for the N-th time.
10. Playing with the above inequalities:
N + k > M*(n - 1) + 2k (from 8)
N + k >= M*(n - 1) + 2k - 1
M*n > M*(n - 1) + 2k - 1 (from 9 and prev. inequality)
M + M*(n - 1) > M*(n - 1) + 2k - 1
M > 2k - 1
Let's choose M = 2k
11. Then N - k > 2k*(n - 1) (from 8)
N - k > 2k*n - 2k
N > 2k*n - k
N > k*(2n - 1)
Let's choose N = k*(2n - 1) + 1
That's it! What do you think? =)
I know lots of people have commented on using the hot/cold method to determine which bulb is which, there's another problem with that as well: You don't know the initial state of the bulbs.
Say for example all the bulbs are initially ON, and you flip two of the switches to what you think is on. Then when you flip one of them to what you think is "off" and wait a while, and go in to the room, you'll find two bulbs on, but you'll misidentify them because the one you thought you switched to "off" you actually turned "on". Not to mention they could be in mixed states initially..
what's the next line?
5.
No finite sequence determines the subsequent.
As such, "math puzzles" of the "what is the next number?" kind are not math puzzles at all--they are psychology and common-knowledge puzzles. They should be stated, "I'm thinking of a number. To me, the number is the next in the following sequence: (...). Your job is to guess, based on what you know of me (or people like me), of mathematics, and of common knowledge, which of the infinite number of mathematical relationships betweeen the numbers in that sequence is the one that is important to me."
People who work in numerical methods are only too aware of how little information finite sequences contain beyond their own bounds. Interpolation is hard enough. Extrapolation is virtually impossible. Even simple sequences like "1,2,3,4..." can have literally anything as the next value--it is trivial to come up with generating functions that give integers for the first few integer arguments and wildly varying irrational values after that. Unless you know what the generating function is, the finite sequence tells you nothing. Guessing the generating function from a finite sequence is all about guessing what the questioner knows and what kind of generating function a person with their knowlege (or common knowledge) is likely to choose that would produce the given sequence.
A modicum of mathematical knowledge is still required, but far more psychology is necessary.
Blasphemy is a human right. Blasphemophobia kills.