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?"

Re:Riddle

[st0rmshad0w]

None, just keep the sprinkles on the side as an option.

Re:Riddle

[iamdrscience]

At least 20, but as many as 34 cupcakes, right?

40 people = 20 teenagers (1/2) 10 adults (1/4) and 10 babies (remaining 1/4)

Half the babies (5 people) don't like cupcakes and one fifth of the babies left (1 person, 1/5 of the five babies left after the 5 that don't like cupcakes). This leaves 34 people who are still wanting cupcakes.

Chocolate cupcakes and sprinkled cupcakes are not exclusive of each other because you can have chocolate cupcakes with sprinkles, so you can disregard the whole thing about who likes cupcakes with sprinkles and who likes chocolate cupcakes as long as you make all the cupcakes chocolate and with sprinkles.

Truth vs. Lies

[sheetsda]

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?"

Re:1 = 0 "paradox"

[LeonGeeste]

What the fuck is that in response to?

Re:Answer to the Sample Question

[Stalus]

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.

Re:Answer to the Sample Question

[c4miles]

If you balance all of the quarters on their edge you can choose any two arbitrary groupings - no coins would be heads up.

But I prefer your solution.

Re:Lightbulb problem

[oGMo]

...or that the lightbulbs heat significantly (what if it's an LED?). This isn't really a math/logic problem.

Two favorites from math olympiads

[jks]

The following two problems appeared in IMOs 1993 and 1994 (you can find the answers using Google, but I won't give a direct link).

A solitaire game is played on an infinite square grid. Initially, there are n^2 pieces in an n*n square formation. On each move, the player moves a piece either horizontally or vertically over an immediately adjacent piece into the square beyond, which must be unoccupied, and removes the piece that was jumped over. The objective is to end up with only one piece on the board. For which values of n is this possible?

Show that there exists a set A of positive integers with the following property: given any infinite set S of prime numbers, there are positive integers k>=2, n and m such that both n and m are the product of k primes in S, n is in the set A and m is not in the set A.

Re:Math and science are obsolete

[Krid(O'Caign)]

Oh, yes, the 'Laffer curve' is real to the extent that 0% of any number is 0, and 100% of 0 is also 0. However, arguments based on it presume that we are ABOVE the ideal tax level - a claim for which there is no supporting evidence. http://en.wikipedia.org/wiki/Laffer_curve [wikipedia.org]

Re:Math and science are obsolete

[LeonGeeste]

You're actually making a better point than your toxic attitude would otherwise suggest. The rich can much more easily avoid taxes, legally or otherwise, than the average person, so raising their taxes really won't help revenue. (Also, shoving the tax load onto them removes any popular support for restraining government, but that's another issue.) If the rich see that one nation's attitude toward them has changed, they all just revise all future plans about investment. In the extreme case, since the rich, being rich, really don't need to work, if their taxes are too high, they just "consume" more leisure. You could, of course, just seize all their assets, but don't expect any more geese to be laying golden eggs where you live anytime soon.

I know you hate the rich and all, I'm just talking about the practical consequences of trying to milk more revenues out of them.

Plus, the premises of the argument behind the Laffer curve really are true. Again, you might not be past a Laffer point, but make no mistake there is a Laffer point. Denying this just makes wise people revise their estimation of the merit of your statements downward.

Re:As I was walking to St. Ives...

[Keebler71]

depends on the definition of "with"

Re:Lightbulb problem

[mogwai7]

One of my solutions takes into consideration LEDs or bulbs that you can't measure the heat. You are right though, it is not a math/logic problem, it's an engineering problem. Thats why "...people...ordinarily good at logic have so much trouble with it."

Re:The King and the Chalice (only for Experts!)

[Negative Response]

This puzzle makes no sense. Either you didn't word it correctly, or it's just plainly wrong. Imagine the case where k is larger than the number n, the times each prisoner needs to be called eventually. All the king needs to do is pick a random prisoner, say "Jack", call him in n times, and undo the cup whenever Jack flips it. After n times, just forget about Jack and call others any way he wants. As far as Jack is concerned, he will never have a chance to answer questions again; for others, Jack never left any information at all, so there's no way any of them can be certain whether Jack has been called at any given point of time. Other prisoners may answer "yes" out of boredom eventually, and that's about the best they could do, always with a chance to lose their collective heads.

Re:Lightbulb problem

[renoX]

Nice one, it took me about 1min to solve (without reading the hint).
So nice but not too hard either.

Re:The King and the Chalice (only for Experts!)

[psst]

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? =)

Re:Lightbulb problem

[kisielk]

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..

Re:Math and science are obsolete

[Impy the Impiuos Imp]

Never let logic and reality get in the way of a good, liberal hate-on for Republicans.

Re:The King and the Chalice (only for Experts!)

[pgpckt]

No, he can't.

Sure he can. Read your own damn problem.

That means the king may turn an upright cup upside down or vice versa up to k times

Up to K times means K or less. Therefore, K is any number. Therefore, the king can do whatever the hell he wants, and the calice provides no information.

Or let's suppose it has to be EXACTLY k times. Either K or zero. Fine. I declare K to be 1.

In this case, if the challice is upside down, the king chooses to flip it K times. If it is rightside up, then the king chooses to flip it zero times. Either way, I can guarantee that the challice is rightside up everytime.

Therefore the challice provides no information, etc, etc, etc.

Re:Math and science are obsolete

[Impy the Impiuos Imp]

While it is true people are greedy and will continue to work hard, even as more and more gets filched by the government, at some point revenue will decrease because people will stop working so hard for diminishing returns.

It's very cynical to tout as good a government that lays like a 2000 pound pig on top of the population, and then shouting joy about it as the population barely moves it around, said movement, if nothing else, caused by the economic activity necessity to stay alive.

But see, if we take taxes, i.e. confiscate money that is not ours, to use for projects that we approve of then it doesn't feel like stealing to us.

Which I find as a disgusting attitude, and why I have little long-term hope for humanity. They preform all the age-old tricks of a dictator, but laundered because it's at the behest of power hungry, charismatic individuals who launder it via "see, the voteres elected me and want it!"

Re:Soduku

[Transcendent]

They're all right, but after you figure out how to actually solve it logically (very simple), there not to much fun anymore... just tedious.

Re:Ok, here's mine

[radtea]

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.

Re:Ok, here's mine

[Schroedinger]

All very true, but if the question were phrased: "What's the simplest generating rule for this sequence?" There would be a lot fewer answers and quite likely one unique answer. The emphisis should be on compressing the available information and not on predicting future information.

Re:Light Bulb

[orainsear]

Prior to entering the room (I am assuming it's a room where you can somehow touch the light bulb, the light works and is connected to one of the switches etc), flip one of the switches e.g. switch number 1 (we'll call them 1,2 and 3) and leave it on for 30 seconds. Flip that switch back to off and flip switch number 2 to on. Now enter the room. If the bulb is lit it is switch number 2 that controls the light. If the bulb is not lit but warm (feel by touching it) it is switch number 1 that controls the light. If the bulb is unlit and cold it is switch number 3 that controls the light.

Re:Similar 'proof'

[Anonymous Coward]

Square root is a multi-valued function. sqrt(-1) = +/- i, sqrt(1) = +/- 1. You can't equate two multi-valued functions in the traditional sense except under specific limiting circumstances, one of them being square roots of non-negative numbers when we only take the positive root.
 
The "rules" of breaking up square roots that you are familiar with only work in this circumstance, and trying to extend them to square roots of negative numbers is a logical fallacy. You're making the assumption that sqrt(x/y) = sqrt(x)/sqrt(y) for all x,y in the real numbers, which is unproven and untrue.
 
As a similar example, let's use the non-negative numbers and only take the negative root. We get that -1 = sqrt(1) = sqrt(1*1) = sqrt(1)*sqrt(1) = -1 * -1 = 1. Again, because our square root techniques only work with roots of non-negative numbers, this is not a valid proof.

Re:Coloured stamps

[rravenn]

Hmm. I am not quite sure it is the solution, but I figured out that you would immediately know you have two cards of color1 on your forehead if others had 2 & 2 cards of color2 (e.g. no more color2 left for you).

If the 1st and the 3rd say they don't know and the 2nd sees that both have equal pairs of different colors (both red and both green), it means he can't have an equal pair of either color (or the 1st or the 3rd wouldve answered) and thus he has one red and one green.

Re:Soduku

[LordoftheWoods]

Why do people get kicks out of solving NP-complete problems? It does take some problem solving skill but its still mostly just tedious trial & error.

Re:The best riddle site on the net

[Anonymous Coward]

Got it in a few minutes.

One prisoner acts as the 'accountant'. He is the only one who will make the assertion. When a prisoner enters the room, if he has not entered before AND the light is off, he turns it on. When the accountant enters the room, if the light is on he turns it off and increases his tally. Once his tally hits 99 (+1 for himself) he can make the assertion.

Re:MOD PARENT UP

[Myopic]

if that's the answer to your riddle, you are an idiot. it's not within the constraints of the problem.

MOD PARENT DOWN

[CoughDropAddict]

So what you're saying is that you wrote the problem ambiguously, and to resolve ambiguities we ought to choose the interpretation that yields a solution?

Your description of the problem does not say when k is fixed. A perfectly valid reading of the problem is to suppose that the prisoners are told that the king will decide k when the game begins.

You ought to admit that the problem was unclear, instead of insulting everyone who interprets your ambiguity the wrong way.

Re:The King and the Chalice (only for Experts!)

[gerardrj]

Here again, you are demonstrating that you can't articulate your thoughts. What does "...at least a day longer than after the prisoners solve the puzzle..." mean?

  In your original posting the language leaves much open to speculation because you spend several sentences clarifying one point and casually make another point. Ex: You dwell on the point that the cells are sound proof but make no mention of other senses such as sight. Is there a window from the cells to the central room? You dwell on the manner in which prisoners are called, but leave the "...or twenty times, or any number you choose," statement completely up in the air. What do you mean "you choose"?

I'd suggest you consider re-writing the mess so that it is not open to debate or question.