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

Comments

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.

Petals of the Rose

[Alien54]

I personally like the petals of the rose

Bill Gates is said to have solved the problem by memorizing the combinations first, 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 :)

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

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

Another online version

[Enti]

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

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

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.

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)

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.

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), 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."

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.