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

Soduku

[beacher]

They drive me nuts. Array and vecor logic. Fun

-B

Keeping my skills fresh

[Paladine97]

I wouldn't say I have a favorite problem but often when I'm bored I'll pen down the Pythagorean theorem and solve it manually. 0 = ax*x + bx + c. I'll work it out until I get the solution that (I hope) everybody knows and loves! It helps to keep my math skills alive during boring meetings.

Sequence

[blystovski]

What is the next line in the following sequence? 1 11 21 1211 111221 312211

Fork in the road

[Anonymous Coward]

You are stranded on an island, on a path which splits in two directions. One direction takes you to "The Village of Death", the other path takes you to "The Village of Life." There are two tribes of people living on the island, one which ALWAYS TELLS THE TRUTH and one which ALWAYS LIES. A person is standing at the fork in the road. What is the ONE QUESTION (micro-variants don't count) you can ask this person which will ALWAYS get you to the Village of Life. Remember that you don't know which tribe the person is from.

Petals of the Rose

[Alien54]

I personally like the petals of the rose [google.com]

Bill Gates is said to have solved the problem by memorizing the combinations first [borrett.id.au], the brute force approach.

It ones of those that requires a knack for seeing the simple things

Re:Infinity

[Frequency Domain]

Then you may like this one: X to the X to the X to the... = 2. What is X if the left hand side is an infinite sequence of powers?

Re:easy one

[calvin1981]

That one's really easy. Set a=42, b=0 and c=42, for any n :)

What do you get if you multiply 6 by 9?

[Doc Ruby]

42

Solution

[Frequency Domain]

Since it's an infinite sequence, you can separate the left-most X and rest still equals 2. Thus X^2 = 2, so X = sqrt(2).

Jugs

[Noksagt]

If you have a 5 gallon jug and a 3 gallon jug of water, and a hose so u can refill any as u please. What are the steps to get exactly 4 gallons of water?

Fill the 5G jug. Pour it into the 3G jug, so you have 2G in the 5G jug. Empty the 3G jug & pour the 2G from the 5G jug into the 3G jug. Refill the 5G jug & finish filling the 3G jug. It will only take 1G, so you will have 4G in the 5G jug.

An original brain teaser

[bratwiz]

Here is the little brain teaser I thought up-- see if you can solve
it...

In the following sequence:

1, 4, 8, 13, 21, 30, 36, 44...

What is the next number and why:

A. 48

B. 50

C. 53

D. 57

E. 61

F. There is no pattern

Re:thrice-plus-one-or-half

[dcclark]

The problem, as stated, is incomplete. If it is being defined recursively, we need some starting conditions, like x(1) = 1. However, as the OP didn't actually ask a question, I'll state what I think he was trying for here:

This is called the "Collatz Conjecture [wikipedia.org]": given a positive integer a_1 = n, let a_i = a_{i-1}/2 if a_i is even, and a_i = 3a_{i-1}+1 if n is odd. Repeat. In other words, take a number, divide by two if it's even and take three times it plus one if it's odd, and repeat ad nauseum. Try a few integers, and you'll find that they eventually end up cycling: 1, 2, 4, 1, ... Does this always happen? The answer is, alas, unknown.

This problem fascinated me through high school, and I eventually ended up going into mathematics partly because of the fun I had exploring its ins and outs.

Re:Oldie but goodie...

[toddbu]

Alternatively:

How many cans can a canner can, if a canner can can cans?

Another online version

[Enti]

http://www.websudoku.com/ [websudoku.com] is my sudoku fix of choice

A True/False Oldie but Goodie

[Quirk]

Since I tend to muck about in philosophy, history and epistemology I'll go with perhaps the most ancient riddle.

Epimenides was a Cretan who made one immortal statement: "All Cretans are liars."

"The Epimenides paradox [wikipedia.org] is a problem in logic. This problem is named after the Cretan philosopher Epimenides of Knossos (flourished circa 600 BC), who stated , "Cretans, always liars". There is no single statement of the problem; a typical variation is given in the book Gödel, Escher, Bach (page 17), by Douglas R. Hofstadter.

Lightbulb problem

[Ellen Spertus]

Given:

• One room has three switches, labeled A, B, and C.
• Another room has three light bulbs, labeled 1, 2, and 3.
• Each switch is connected to one bulb, but you do not know which is connected to which.
• When inside either room, you cannot see the other room.
• You begin in the room with the switches and may turn the switches on and off in any way you choose.
• Once you leave the room with the switches, you may not reenter it. You may, however, go to the room with the light bulbs.

How can you determine which switch is connected to which light? Here is a hint [nicemice.net] and solution [nicemice.net].

I like this problem because people are ordinarily good at logic have so much trouble with it. I once had the pleasure of meeting Donald Knuth and stumped him with this puzzle.

Re:Petals of the Rose

[Alien54]

though i can see how frustrating it would be if you didn't pick up on this quickly :)

Unfotunately, one rumor says that the smarter you are, the longer it takes to figure out.

Because smart people often fall for complex solutions.

Algebraic proof: 2=1

[mithran8]

This is one of my favorites - it has stumped many self-professed math geeks, yet high school freshmen have spotted the solution immediately.

x=y
x^2=xy
x^2-y^2=xy-y^2
(x+y)(x-y)=y(x-y)
x+y=y
2y=y
2=1

Every step uses perfectly valid algebra, yet something is obviously very wrong somewhere.

Enjoy...

Re:Divisible by 3 or 6?

[dcclark]

Generalized problem: find a similar method (to the division by 3 or 6 rules) for any integer. Not all are fast ways, but there is a relatively simple solution for any integer. A fun one to try is 11. Hint: write the number in base 11 and use modular arithmetic.

Any ABCABC number is divisible by 13...

[aendeuryu]

Not really hard to prove, but it's cute.

Take any six-digit number that's of the form ABCABC where A,B,C are any integers (yes, they can be the same, yes they can be zero, although that might make it less than six-digits if A, or A and B, are zero), and that number is guaranteed to be divisible by 13.

Violation of angular momentum

[GarbanzoBean]

1) No object can violate conservation of angular momentum.
2) To rotate an object one needs to give it angular velocity, hence angular momentum.
3) To have finite angular momentum, an object needs torque applied to it (or a force applied away from the center of moment).
4) Gravity acts on the center of moment and does not result in torque on any free falling object.
5) Cats dropped feet up manage to land on their feet.
6) Does this mean cats violate conservation of angular momentum; no wonder Egyptians worshiped them.
What is wrong with this discussion; no math involved from my Classical dynamics class.

Sticky Triangles

[Doc Ruby]

Let's say I have a stack of sticks: all identical, inflexible, unbreakable. Sticks can touch only at their ends, not in between.

If I give you 3 sticks, you can make one triangle. If I give you 2 more sticks (5), you can make 2 triangles. If I give you another stick (6), how can you make 4 triangles?

The King and the Chalice (only for Experts!)

[brian0918]

There is a king and there are his n prisoners. The king has a dungeon in his castle that is shaped like a circle, and has n cell doors around the perimeter, each leading to a separate, utterly sound proof room. When within the cells, the prisoners have absolutely no means of communicating with each other.

The king sits in his central room and the n prisoners are all locked in their sound proof cells. In the king's central chamber is a table with a single chalice sitting atop it. Now, the king opens up a door to one of the prisoners' rooms and lets him into the room, but always only one prisoner at a time! So he lets in just one of the prisoners, any one he chooses, and then asks him a question, "Since I first locked you and the other prisoners into your rooms, have all of you been in this room yet?" The prisoner only has two possible answers. "Yes," or, "I'm not sure." If any prisoner answers "yes" but is wrong, they all will be beheaded. If a prisoner answers "yes," however, and is correct, all prisoners are granted full pardons and freed. After being asked that question and answering, the prisoner is then given an opportunity to turn the chalice upside down or right side up. If when he enters the room it is right side up, he can choose to leave it right side up or to turn it upside down, it's his choice. The same thing goes for if it is upside down when he enters the room. He can either choose to turn it upright or to leave it upside down. After the prisoner manipulates the chalice (or not, by his choice), he is sent back to his own cell and securely locked in.

The king will call the prisoners in any order he pleases, and he can call and recall each prisoner as many times as he wants, as many times in a row as he wants. The only rule the king has to obey is that eventually he has to call every prisoner in an arbitrary number of times. So maybe he will call the first prisoner in a million times before ever calling in the second prisoner twice, we just don't know. But eventually we may be certain that each prisoner will be called in ten times, or twenty times, or any number you choose.

Here's one last monkey wrench to toss in the gears, though. The king is allowed to manipulate the cup himself, k times, out of the view of any of the prisoners. That means the king may turn an upright cup upside down or vice versa up to k times, as he chooses, without the prisoners knowing about it. This does not mean the king must manipulate the cup any number of times at all, only that he may.

Assume that both the king and the prisoners have a complete understanding of the game as I have just explained it to you, and that the prisoners were given time beforehand to come up with a strategy. The king was able to hear the prisoners discuss, however, so also assume that if there is a way to foil a strategy, the king will know it and exploit the weakness. The prisoners must utilize a strategy that works in absolutely every single possible case.

Now you must figure out not only how to keep the prisoners alive, but how to also ensure their eventual freedom. When can any one of them be certain they've all been in the central chamber of the dungeon at least once? And how? Don't try to imagine any trickery like scratching messages in the soft gold of the chalice. The problem is as simple as it sounds. The prisoners have absolutely no way of communicating with each other except through the two orientations of the chalice. If any of them attempts any trickery at all they will all be beheaded. All the prisoners can do is turn the chalice upside down or right side up, as they choose, whenever they are called into the chamber.



(written by a former roomate)

hats

[blackcoot]

let's see... the problem goes roughly like this:

you have five hats (two red, three black) and three people. you queue the people up in order of height and have them face the same way (this way the tallest person can see the two people in front of him/her, the middle person can see the shortest person, and the shortest person can't see anyone). you put a hat on each person's head and instruct them that they are not allowed to take the hat off or turn around. you then ask them to tell you what color their hat is. after a while, the person at the front of the line correctly announces the color of his/her hat. how did the person at the front of the line know and what were the other hat colors?

Light Bulb

[lababidi]

here's an oldy MSFT asks on job interviews:

next to a door are 3 light switches. one of the switches are connected to an incandescant light bulb in the windowless room on the other side of the door. you may not open the door and flip the switches. you may only enter the room once. which switch lights up the room?
Solution [mooder.org]

Monty Hall

[nfarrell]

This is a classic, demonstrating how humans can't cope with conditional logic. Ripped straight from Wikipedia:

The Monty Hall problem is a puzzle in game theory involving probability that is loosely based on the American game show Let's Make a Deal. The name comes from the show's host, Monty Hall. In this puzzle a player is shown three closed doors; behind one is a car, and behind each of the other two is a goat. The player is allowed to open one door, and will win whatever is behind the door. However, after the player selects a door but before opening it, the game host (who knows what's behind the doors) must open another door, revealing a goat. The host then must offer the player an option to switch to the other closed door. Does switching improve the player's chance of winning the car?

For a dicussion go here, but be warned, they tell you the solution: http://en.wikipedia.org/wiki/Monty_Hall_problem [wikipedia.org]

Knight's reward

[Anonymous Coward]

This is a non trivial problem. ...

Once upon a time, in a land far far away, there lived a knight who had
just rescued his first damsel in distress. The knight was called before
the king to receive a reward. The king told the knight that he had
written an amount of gold on a piece of paper and twice the amount of
gold on another piece of paper. He placed the two pieces of paper face
down in front of the knight, and told him he could chose either one.
The king would give the knight the amount of gold on the paper as a
reward. Or, the knight could opt to get the amount of gold on the other
paper instead.

This was the knight's first reward, so he had no idea what he was likely
to get. But the knight reasoned that no matter what amount he saw on the
paper he chose, he would take the other one because he had more to gain
than lose. For example, if the paper he chose had 16. He might win
another 16, and at worst he only loses 8!

The damsel points out that if the knight is going to end up with the amount
on the other piece of paper anyway, why not just choose it first and not
switch. His reward will be the same. ...

Is the damsel correct? Or is the knight's plan sound?

Refute the argument you disagree with. (Refuting the incorrect argument
is the challenge.)

you're given a globe

[rmm4pi8]

Assuming the earth is a perfect sphere, describe the solution set of points where you can go 1 mi south, 1 mile east, and 1 mile north and return to your starting point. Hint: the cardinality of the set is R cross Z + 1 (and yes, I know that's equal to R, but expanding it makes it a more effective hint). Feel free to email me for more hints.

One I like

[andrewagill]

You are a tourist, visiting a desert island just off the coast of South America. There's only one reason that you would be visiting this one-acre island, and that is that there is a tiny plateau reaching up a mile into the air, with the ruins of an Aztec temple on it.

As you walk along a path, you come to a fork. In the fork are two men, of which you know little, except that they must have come from one of the villages on the other islands nearby.

There are three villages--the Marqetteres always lie, the panguons always tell the truth, and the Shie'ep always do what everybody else is doing.

You may ask one question to one of the men. What do you do?

Answer(ROT-13):
Fvzcyr. Lbh vtaber obgu zra, naq jnyx fgenvtug gb gur zvyr uvtu cyngrnh, juvpu jbhyq or ivfvoyr sebz nal cbvag ba n bar-nper qrfreg vfynaq.

Spacial geometry one

[nfarrell]

Ok, here is a progression of questions which require no special training. Make sure you only ROT13 one answer at a time if you're trying these yourself:

Assume Earth is a perfect sphere.

Q1) Where can you stand such that if you go 1km North, then 1km East, then 1km South, you're back where you started?

A1 rot13'ed) gur fbhgu cbyr. pregnvayl abg gur abegu cbyr, nf lbh pna'g tb abegu sebz gurer. naq vs lbh fnvq 1xz fbhgu bs gur abegu cbyr v'q fnl ab gbb, nf lbh pna'g tb rnfg sebz gur abegu cbyr, bayl fbhgu.

Q2) OK smarty. Where ELSE can you do it from, on the Earth's surface? No tricks are involved either, just a bit of thinking.

A2) n ovg bire bar xz fbhgu bs gur abegu cbyr: nsgre jnyxvat gur 1xz abegu, n 1xz jnyx rnfg pbzcyrgryl pvepyrf gur abegu cbyr, zrnavat lbh'ir qbar n ebhaq gevc. 1xz fbhgu gura ergheaf lbh gb gur vavgvny cbfvgvba. n srj crbcyr pbzcynva nobhg guvf bar, nf lbh nera'g jnyxvat va n fgenvtug yvar, rira gubhtu lbh'er nyjnlf urnqvat rnfg. lbh pna erzvaq gurz gung gurl jrera'g tbvat va n fgenvtug yvar va n1 rvgure. naq nfx gurz gb qrsvar 'rnfg' vs gurl fgvyy nera'g unccl.

Q3) You really think you're good don't you? OK, I want to know where ELSE!

(read this when you think you have it, before you read the real answer: gur nafjre vf abg nabgure cbfvgvba ba gur rnegu'f fhesnpr qhr rnfg (be jrfg) bs gur nafjre gb d2. jryy vg vf, ohg vg'f abg tbbq rabhtu, gurer'f fbzrjurer ryfr.)

A3) guvf nafjre vf nyzbfg gur fnzr nf gur ynfg, ohg vafgrnq bs cynpvat lbhefrys fb gung gur bar xz rnfgreyl jnyx vf n pbzcyrgr ybbc, lbh'er rira pybfre gb gur abegu cbyr, naq znantr gjb ybbcf! be, sbe gung znggre, lbh pna zbir rira pybfre, naq nf lbh nccebnpu gur '1xz fbhgu' cbvag sebz gur abegu cbyr lbh jvyy svaq zber naq zber fbyhgvbaf.

Enjoy.

The Dilema

[Cash202]

If you do the population curve (takes a couple minutes, and somewhat tedious) it teaches an interesting lesson. The more money we donate to starving countries, like we do to various countries in Africe (both government and public donations), the more they reproduce. Thus they require more money, eventually dying out anyway. If we don't donate money, they drop to incredibly low numbers, and stabilize, but not as low as the other alternative. Thus the dilema. Either you donate and save some lives, causing more death in the end. Or you sit idle by, letting people die.

Re:hats

[drawfour]

If the tallest person saw two red hats in front of him, he would immediately know his had was black and say "My hat is black!" He didn't, therefore he either sees two black hats or one black hat and one red hat.

Knowing this, the second person looks at the hat in front of him. If he sees a red hat, he knows his is black. Since he does not see a red hat, his is either red or black, he doesn't know. But knowing this, the first guy can deduce that his hat is black.

I don't think you can know what the other colors were from this, but the first person can correctly deduce his hat color. Interesting puzzle. I've heard it before, but never took the time to analyze it.

Re:Soduku

[LnxAddct]

This is a fun little python script I wrote to solve sudoku puzzles. I'm pretty sure its bug free, and there may be more pythonic ways of doing some of the things I did in it, but whatever:) It works. (iff the puzzle has one solution, which I believe is a requirement for true sudoku puzzles, but I've encountered a few with several solutions). Just run the the script in the same directory as a file called "sudoku.txt", or modify the script to accept an arg, its easy enough. the format of the txt file is 9 characters per line, 9 lines. A space is where there is no known digit, and the other characters are the known digits.
Regards,
Steve

To get past the lameness filter I had to encode the file. To decode it, copy the text into a file like "sudoku.endcoded", remove the spaces that slashdot inserts at character 51, run "uudecode sudoku.encoded", and then run "uncompress main.py". Ugh thats a lot of work for a damn file, but hey it works :)

begin 664 main.py.Z
M'YV0(T*\J#-'S@LQ:=R\@).'#IHW;A282<.F#(@>(-[`*>,&A 8@Y=<B\6?/&
M!1T\=$2D4-`F#!TY:?!<!+&EBP(Y;^[,K*E`P0@04LJ$(0,B( 0B0(M?4*>K&
MS!LY+>FD@0@BC!NB<\K089I&:A@V(*+"Q"/Q*0@V"2T:G5C1A 1RA9-"Z*3,'
M10H="A(XE0-B#)HP<L*,H5.&KU&Y9?`F2)#&3-^_@0<7OHA1! `@1BA?CO.,B
M#)R-5U%LB<%"!HL9+&BPJ,'"!HL;+'"PR-%EY>(R:!W[!2R8L &$WEV/(F$&C
MAHT;.')@SJLY9^?/',F(3D@'Q>[(OE/4SBLVYG/0TC?;WKS3Y D\F6N<<?</&
MCD6'%KN3W0M"#!NK:YB"P!/8S9DR*.1P%P@C4(%&&NJI0=!67 17F$ET@Y`""
M5&W0Q4)]][F1'X(@U.$&0660D1=]Y!G%GU7_!7@7<_2-P5X=; 0!G8G\I"I@9
M8XY5U)%\6VS6Q18NL@&C&[51!D(,(-R8P!AUR/&6&W1\8<=7= 5B$$8\^`OEB
MC#_"8--BB]&7AGXG^@>@C<R!^=,0%0$V(1H6;9;F8HT5!4((& )%G%5%,.LE1
ME%,*J19P/*;Q8Y!#=I'DG(L5>NB61+I51AMON&==DT\"2F49M H&9P)IM\@5?
M7Y`R6N>8>)(J9(Q57=47IG]*N:E^6.;THZ&+>MJH2V/U:.L6A DI*J:5]9BJK
MH)TN!JI0HL)YUAMC?(4AM/FA,&J9_ZD'F$5AG-45'16%]091+ Z4Q1GYTO`'"
M?UN-:A^UR>IEEHMDT@A@"]9!6L(,*5R(+Z(Q[IO""OPJ*2]?. -6+XKTH;":P
MOPWG)##!*^J*(P@@1'PG1C!DQ!>]J<*00JM\P@KEL572RFM,O NJT`@@X/;HJ
M<"^[J*C!NY:+1\L@O)RPS$/V3&H7PE8*8+&Q!EKE2B3FI++.B K4(J7Z;94;?
FAVV(,9E1`+MQ(QPP00D"UEK+P0)S8%-W&1<I@7!V`FF++8((" @``
`
end

Re:What do you get if you multiply 6 by 9?

[jag164]

#define SIX 1+5
#define NINE 8+1

printf("TATLTUAE = %d, SIX * NINE);

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

[pgpckt]

It seems that the Chalice is a red-herring.

Obviously, the most devious thing that the king can do is to always make sure the chalice is rightside up. Therefore, it will always be rightside up. Therefore, the chalice can provide no information. Therefore, it is a red-herring.

With all other avenues of gathering information forbidden, there seems no information left to base an answer on.

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

[Anonymous Coward]

It feels like the "flipping the chalice" bit is deliberate misdirection. Where were the prisoners able to communicate to come up with a strategy? It's explicitly stated that they can't hear each other from their own cells -- they had to have either 1) all moved out into the central room (or through it to some other location) to talk to each other, or 2) all moved into one cell. If 1) is correct, then the first person to walk out can say "Yes" and they will all be freed. If 2) is correct, then when the person whose cell was used as a meeting room is called upon, he says "Yes" -- everyone else simply states "I don't know."

Am I close? :)

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:Truth vs. Lies

[eonlabs]

My bad, he mis-told the riddle. I'm familiar with the correctly told one, so I overlooked the goof up. The original is There are two indistinguishable doors, each has a guard, one leads to salvation, one to a gruesome death, and one of the guards always lies while one always tells the truth. What yes/no question could you ask a guard to guarentee you would pick the door to salvation. You may only ask one question. The reasoning behind the solution is very simple, but it usually takes a while to pick up on it for most people.

Three Salesmen

[Anonymous Coward]

Three salesmen are late to town for a conference. Eventually late that night they find a hotel with one room left. (It's a room for three). The bell boy says "The room is $30, please". The salsemen are delighted with such a reasonable rate and each fork over $10.

When the bell boy gives the cash to the night manager, the manager says "No, no, no no. This is not right - The room is only $25 dollars - not $30. Here are five $1 notes. Please give them back to the guests".

On the way back back, the bell boy thinks, "I have five dollars and three guests. I can't divide this evenly. So I'll just keep two dollars for myself."

The salesmen take their cash and turn in for the night.

So.......
Each Saleman has effectively paid nine dollars (ten dollars minus one returned).
The bell boy has two dollars in his back pocket.
$9 + $9 + $9 + $2 = $29.

Where has the last dollar gone???

Suck on that, my fellow brains-on-stilts.
Heh heh heh.

Re:Math and science are obsolete

[LeonGeeste]

One wonders if it is in fact you who is dismissive of the poor, your attitude toward them in your posts here certainly is.

*sigh*

I'm trying to explain to you the practical consequences of what you're proposing. I was just describing aspects of reality. You'll notice I never said anything was good or bad, just what will or won't happen. If you can find the place where I was dismissive of the poor, I'd really like to know where it is.

Now, I already explained enough so you could understand the difference between cracking down on the rich vs. the poor. The rich can easily scurry away and/or stop producing. The poor can neither easily scurry away nor stop producing. Again, this is not to say anything is "good" or "bad", just that it "will" or "won't" raise tax revenues. Contrary to your staunch refusal to dispassionately analyze the topic, there really are relevant practical considerations in raising taxes.

In fact, I'd like nothing more than to test out your ideas. Check out the link in my sig. I submitted an idea to a policy site. The idea is that basically, in one state, we do what you propose: high taxes on the rich, high minimum wage, good workers protections and workplace safety requirements, etc. In the other state, do the oppose: no min. wage, low taxes on the rich, no safety requirements, etc. If you're really serious about your views, you'd leap at the chance to do this and see who's right based upon which state people flock to.

You do think you're right, right? ...RIGHT?

The BART Ticket Puzzle

[saccade.com]

The BART is the SF Bay area's excuse for a subway / mass transit. To ride, you buy a ticket at a kiosk full of $x worth of "BARTness". When you get board the train, you stick your ticket into a turnstile, and it hands it back to you. When you reach your desgination and get off the train, you again stick your ticket into a turnstile. It deducts the cost of your trip (based on how far you traveled) and gives your ticket back. You keep using the ticket until $x is used up. BUT: Suppose you walk toward the train, put your ticket in the entrance turnstile. You pick up your ticket, then you change your mind and leave, putting your ticket in the exit turnstile to get out. The cosmic BART megamachine will charge you the maximum possible fare, even though you haven't gone anywhere. For a good reason. What's the reason?

Re:Solution

[wildsurf]

Since it's an infinite sequence, you can separate the left-most X and rest still equals 2. Thus X^2 = 2, so X = sqrt(2).

Disprufe(TM) by contradiction:

1. Suppose sqrt(2) ^ sqrt(2) ^ sqrt(2) ^ ... = n.
2. Then, sqrt(2) ^ (sqrt(2) ^ sqrt(2) ^ ...) = n.
3. Hence, sqrt(2) ^ n = n.
4. Therefore, n obviously equals 4, because sqrt(2) ^ 4 = 4.
5. Hence, sqrt(2) ^ sqrt(2) ^ sqrt(2) ^ ... equals 4, not 2, so it can't be the solution to the original problem.

What's wrong with this logic? ;-)

That's a dumb response

[Anonymous Coward]

He just showed you how all five of the possible answers are correct given only the information you supplied.

How is it that you have any solution more "real" than the solutions he just provided? Could it be that you haven't really thought through your riddle so well?

Re:Riddle

[Wavicle]

Since that's basically a probability question, I thought I'd follow up with my own favorite probability mind bender:

Your married-with-two-kids co-worker invites you over to dinner. When you arrive a son of the coworker answers the door. What is the probability that the other child is a girl?

Followup:

The co-workers oldest child, a son, answers the door. What is the probability that the other child is a girl?

Most who have gone through a formal stats class have seen this one before, but it is always fun to try and wrap your head around it the first time.

Re:Ok, here's mine

[matt4077]

again, with breaks in it:
1
12
1112
3112
132112
1113122112
311311222112

what's the next line?

Re:One possible solution:

[radtea]

Turn a light on.

I was once a judge at a "Phyics Olympics" where there was one puzzle in which students had to figure out the wiring if a circuit consisting of a couple of light bulbs and a couple of switches. They were "supposed" to solve the puzzle by flipping the switches, noting what lights were on and off, and inferring the circuit.

One team took the apparatus apart and inspected the wiring.

I gave 'em full marks.

The head judge went spare.

Science is not a game, and there aren't any rules according to which you are "supposed" to solve the problem. Alexander the Great was demonstrating the practice of experimental science when he unravelled the Gordian knot, and Feyrabend was onto something when he said, "Anything goes."

Puzzles set by humans have more to do with communication between the puzzle-setter and the puzzle-solver than anything else. Some people even decry computer-generated puzzles because of this--they say that the pleasure they get from solving puzzles comes from the feeling of interaction with another mind.

Re:Algebraic proof: 2=1

[Anonymous Coward]

I am reminded of a short bit in the Journal of Irreproducible Results, where they had proof of -1 being the largest integer. Rough rephrasal:

The defining property of the largest integer is that there is no larger integer. But if you take any integer and add one, you get a larger integer. So the largest integer must fulfill x = x + 1, and taking it one step farther for good measure, x = x + 2.

x = x + 2

Square both sides.
x^2 = x^2 + 4x + 4

Subtract x^2.
0 = 4x + 4

Subtract 4x.
-4x = 4

Divide by -4.
x = -1

Checking this result, -1 is indeed an integer and nothing is one more than -1. QED.

My all-time favorite logic puzzle

[Council]

Oh, woe is me. I have a perfect logic puzzle, but was unlucky enough to be otherwise engaged when this story was posted. (By the way: a soft couch, a carefully selected DVD, half a bottle of rum, and a girl. Guess which element to this excellent scenario was fucking ruined by copy protection? I'll give you a hint: I may have just switched sides in this movie piracy debate. Fuck the RIAA. It was a perfectly legal store-bought DVD. Fuck them all.)

But anyway, logic puzzles. This logic puzzle is excellent. I've had it up on my site (http://www.xkcd.com/blue_eyes.html [xkcd.com]), and after I got boingboing'ed I got a lot of email about it, so I've been able to tweak the wording to get rid of most of the confusing stuff, leaving only the logic. It's extremely subtle; I've never seen anything like it.

Here's the puzzle:

A group of people live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. If anyone has figured out the color of their own eyes, they [must] leave the island that midnight.

On this island live 100 blue-eyed people, 100 brown-eyed people, and the Guru. The Guru has green eyes, and does not know her own eye color either. Everyone on the island knows the rules and is constantly aware of everyone else's eye color, and keeps a constant count of the total number of each (excluding themselves). However, they cannot otherwise communicate. So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes, but that does not tell them their own eye color; it could be 101 brown and 99 blue. Or 100 brown, 99 blue, and the one could have red eyes.

The Guru speaks only once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:

"I can see someone with blue eyes."

Who leaves the island, and on what night?

There are no mirrors or reflecting surfaces, nothing dumb, It is not a trick question, and the answer is logical. It doesn't depend on tricky wording, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me."

And lastly, the answer is not "no one leaves."

Re:Math and science are obsolete

[Anonymous Coward]

Hmmm, let me guess.

Low taxes, no expensive workers protection, no minimum wage will move business to the 2nd coutry.

Business in the first country will not be able to compete with business from the 2nd country. Since workers protection
is good they will be afraid to hire people since it will be costly to fire them.

This will lead to much higher unemployment in the first country.

Now the answer depends on the unemployment benefits. If they are low - people will flock to the 2nd country faster.

If they are high - it will create another drain on the 1st country resources. In 100 years it will be significantly poorer than
2nd country and people will flock to the 2nd country then.

It is already happenning: Europeans moving to the US, I even know a few Europeans who moved to China.
Just compare France and the US.

My fav math puzzle is:

[Anonymous Coward]

My fav math puzzle is:
There are two mathematicians in a room. The product of two integers >=2 is given to the first mathematician, and the sum of the same two integers is given to the second one. Hence, the first mathematician only knows the product and the second only knows the sum of the two integers. However, both are aware that the first knows the product and the second knows the sum of the two integers.

The first mathematician is asked whether he can determine the two numbers, and he answers no.
The second mathematician is then asked whether he can determine the two numbers, and he too answers no.
The first mathematician is then asked once again whether he can determine the two numbers and this time the answer is yes!
What are these two numbers?

Re:Petals of the Rose

[raap]

My math teacher posed this problem as the so called "bear guardian test". It went like this: You are to become an ice bear guardian at the north pole. You know the following facts:

1. Bears appear only in pairs.
2. Bears live in holes. No holes - no bear.

That's all the information given. After the dice are rolled, you have to tell the number of holes and the number of bears. To make it harder, he did not always roll five dice, but varied from 2 to 5 dice. We tried like crazy for 45 minutes without getting a solution. Note that in this variation of the puzzle, the name does not give away the solution.
It impressed me so much, that I haven't forgotten this lesson even after being out of school for more than 20 years.

Take a Break - 8 Ways to 15

[BoRegardless]

If you really get one of 'those' meetings or classes, you can try this. It is so boring, you have already made another Tic Tac Toe crossed set of lines. Take all 10 numeral digits and put them in the Tic Tac Toe so that all horizontal, all vertical and all diagonal sums each add up to ... 15 I give no hints.

He wasn't really using brute force.

[pavon]

Ah I got it. Took 16 rolls (written down) and almost hour. The fact that I am ignorant about roses didn't help :)

Anyway I read that story and it didn't appear to me that he was trying to solve it by memorization, but rather that after an hour, seeing hundreds of rolls, he remembered many of them, which isn't all that surprising. What I got out of the story, is that he persistently kept at the problem trying many different ideas until he finally got it, even after everyone else in the group had solved it or quit.

I don't think that how quickly someone solves any one particular problem is much of an indicator of how smart they are. We were doing brain teasers on an ACM trip my freshman year of college, and I was one of the first to get most of them. Then there was this one that everyone got right away and I couldn't get it. When I finally did a day later I was kicking myself because it was so obvious - I just wasn't looking at it the right way.

This story showed my that Bill Gates is a very persistent and determined person which is probably a big reason that he was so successful. That and he needed to get a girlfriend at that point, as do I apparently :)

All horses are the same color (by induction)

[Anonymous Coward]

http://www.math.hmc.edu/funfacts/ffiles/30002.8.sh tml [hmc.edu]

An excellent collection of puzzles

[Anonymous Coward]

An excellent site with puzzles: Thirty Puzzles for Mathematicians and Computer Scientists [stanford.edu]

For example:

Bigger or Smaller: Alice chooses two distinct real numbers between 0 and 1, writes them onto two chits of papers and places the chits in a jar. Bob gets to select one of the chits randomly and open it. He then has to declare whether the number he sees is the bigger or smaller of the two. Is there any way he can be correct more than half the times Alice plays this game with him?

f(f(x)) == -x? Is it possible to write a function int f(int x) in C that satisfies f(f(x)) == -x? Without globals and static variables? Is it possible to construct a function f mapping rationals to rationals such that f(f(x)) = 1/x?

30 Coins: 30 coins of arbitrary denominations are laid out in a row. Ram and Maya alternately pick one of the two coins at the ends of the row. Could Maya ever collect more money than Ram?

Excellent book of CS/Math puzzles by Peter Winkler

[Anonymous Coward]

Mathematical Puzzles: A connoisseur's Collection by Peter Winkler: at Amazon [amazon.com]. The first chapter is readable at Amazon! With wonderful puzzles.

Re:My all-time favorite logic puzzle

[efflux]

*spoiler warning*

I think this stipulation is also necessary:

1) That everyone with blue eyes (at least) is wholly involved in figuring out if they have blue eyes and should comply (bear with me, this is different than you think)

Without this specification, there can be no implicit communication as to the understanding of others.

But to be fair, this is hardly the end of the specifications, and is why I so detest logic puzzles. An earlier poster had it right when they said that a logic puzzle is hardly about logic, but about communication between the puzzle maker and tester.

I think there is an issue with your stipulation about the islanders not "otherwise" communicating with each other because I think communication other than the exact count of islanders is exactly what happens.

To rectify this I could, for instance, instead demand there be such stipulations as:
2) The islanders don't tell each other what their eye colors are
3) Or otherwise sign
and because we're tired and want to stop this progression from escaping us we'll try a catch all...
4) or intentionally let each others know
Perhaps you might say someone demanding that there could be such a "outside mode of communication" isn't "playing along", but this is precisely what I mean. There must be a communication of what the solution might be for a guesser to play along with what might get him there. I would like to especially point out that one can get into the same trouble with rule 4 as you did with your stipulation (and for the same reason, and that this is unavoidable). I would say that an islander following stipulation 1 is implicitly breaking this or any such rule.

But we're hardly done yet... I want to examine rule 1 a little closer and to do that I need to outline the "solution".

1 blue eyed islander:
In the case of the 1 blue eyed islander, he sees that everyone else has brown eyes (and the guru green) so knows he must have blue eyes. He leaves. The others do not leave because they see him leave.

2 blue eyed islanders:
The two blue eyed islanders see that there is another blue eyed islander and so don't leave on the first day. They then both leave on the second day, knowing that the other must have not left because they expected themselves to leave the first day*. No one else leaves, because they knew there were at least two others, and so waited for the third night**.

And so on for n blue eyed islanders.

So, first onto the problem with condition 1), and then onto those little stars.

Condition 1) at first seems as if it is a simple restatement of the condition that islanders know the count of other's people eye color at all times. It is not. In addition, it also signifies that every islander (or at least ever islander with blue eyes) must be *carrying out* the logical processes and understand its implications.

But then, for any islander to have any certainty of what the other islanders know, he must also have the guarantee that every other islander is carrying out these processes. This leads us to:
5) Every islander knows that every (blue eyed) islander is wholly involved in deciding if they have blue eyes.
It's actually a bit more involved and also involves knowing all other stipulations are also in effect, but I would like to keep this somewhat comprehensible.
And now that we realize this is a stipulation for the valid reasoning of an islander, an islander also needs to be assured of 5). Thus:
6) Every islander knows that every (blue eyed) islander knows that every (blue eyed) islander is wholly involved in deciding if they have blue eyes.

And so on. It is only important that every blue eyed islander has correctly proceeded for one to decide how to proceed.

Those stars:
*Conveniently, this directly extends from the previous statement, so it should flow nicely. For an islander with blue eyes to know that the others know he has blue eyes, he must assume that the islanders "correctly proceeded". Thi