Math Puzzles!

Math Puzzles

Logic Puzzles

Resources

Math Puzzles

Fake Coin

There are 12 coins. One of them is false; it weights differently. It is not known, if the false coin is heavier or lighter than the right coins. How to find the false coin by three weighs on a simple scale?

What’s My Card?

A student is given five random cards from a standard deck of 52 cards. He must choose four cards to reveal to his professor and the order in which to reveal them; his goal is to reveal four cards in such a way that the professor knows what the fifth hidden card is. How does he do this?

What's My Card? II

What if there are 124 cards instead of the standard deck of 52?

Hexagons

Divide an hexagon in equilateral triangles, like in the figure. Now fill all the hexagon with the three kinds of diamonds made from two triangles, also shown in the figure. Prove that the number of each kind of diamond is the same.

Hats Off

Three mathematicians are applying for a job. There are five hats, three white, two black. They’re lined up, and a hat is placed on each. The first person in line cannot see any hat; the second in line sees only the hat of the person in front of him; the third person sees only the hats of the two people in front of her. The first person to correctly figure out what color hat he has gets the job; you guess wrong and you are killed. Assume these are INTELLIGENT mathematicians, and that they will do the logically correct thing at each stage — if something can be deduced, they will figure it out. After a long pause, the first person, who cannot see any hats, says he knows the color of his hat. What is the color, and how does he know?

Zen problem

A Buddhist monk got an errand from his teacher: to meditate for exactly 45 minutes. He has no watch; instead he is given two inscent sticks, and he is told that each of those sticks would completely burn in 1 hour. The sticks are not identical, and they burn with variant yet unknown rates (they are hand-made). So he has these two inscent and some matches: can he arrange for exactly 45 minutes of meditation?

100 Prisoners and The Light Bulb

100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?

Mad as a Hatter

100 mathematicians are standing in a line, wearing a black or white hat. Each mathematician can ONLY see the color of the hats of the people in front of them. So the first person sees no hats, the last sees 99. The mathematicians are allowed to talk to each other and decide upon a strategy, for a government rep is coming to cut off funding. Each person can only say “black” or “white.” If you correctly say what color hat you’re wearing, your funding is continued and you live. If you’re wrong, you lose your funding, and you may as well be dead. How many mathematicians can you guarantee will keep their funding? You are not allowed you use “tricks,” say a person delays one second before answering means A, two seconds means B, … You have to answer IMMEDIATELY what color hat you’re wearing.

Three Hats and a Strange Probability

Three players enter a room and a red or blue hat is placed on each person’s head. The color of each hat is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each person can see the other players’ hats but not his own. No communication of any sort is allowed, except for an initial strategy session before the game begins. Once they have had a chance to look at the other hats, the players must simultaneously guess the color of their own hats or pass. The group shares a hypothetical $3 million prize if at least one player guesses correctly and no players guess incorrectly. The same game can be played with any number of players. The general problem is to find a strategy for the group that maximizes its chances of winning the prize.

Prisoner's Hats

Fifteen prisoners sit in a line, and hats are placed on their heads. Each hat can be one of two colors: white or black. They can see the colors of the people in front of them but not behind them, and they can’t see their own hat colors. Starting from the back of the line (with the person who can see every hat except his own), each prisoner must try to guess the color of his own hat. If he guesses correctly, he escapes. Otherwise, he is fed to cannibals (because that’s the canonical punishment for failing at hat problems). Each prisoner can hear the guess of each person behind him. By listening for painful screaming and the cheering of cannibals, he can also deduce if each of those guesses was accurate. Of course, this takes place in some magical mathematical universe where people don’t cheat. Assuming that they do not want to be eaten, find the optimal guessing strategy for the prisoners. (The cannibals should eat no more than one prisoner.)

Infinite Prisoners and Hats!

In the year 3141, Earth’s population has exploded. A countably infinite number of prisoners sit in a line (there exists a back of the line, but the other end extends forever). As in the previous problem, white and black hats are placed on their heads. Due to modern technology, each person can see the hat colors of all infinitely many people in front of them. However, they cannot hear what the people behind them say, and they do not know if those people survive. Assuming that they do not want to be eaten, find the optimal guessing strategy for the prisoners. Assume that there are enough cannibals to eat everyone who fails. (The cannibals should eat no more than finitely many prisoners.)

Seven Prisoners and Hats!

There are seven prisoners, and colored hats will be placed on their heads. The hats have seven possible colors (red, orange, yellow, green, blue, indigo, violet), and may be placed in any arrangement: all the same color, all different colors, or some other arrangement. Each person can see everyone else’s hat color but cannot see his own hat color. They may not communicate after getting their hats, and as in the previous problems, they remain in a magical universe where no one cheats. They must guess their hat colors all at the same time. If at least one person guesses correctly, they are all released. If no one guesses correctly, however, the entire group is fed to cannibals. Assuming that they don’t want to be eaten, find the optimal guessing strategy for the prisoners. (By this point, the cannibals have probably eaten far too much. It would be cruel to force them to eat any more, so spare the cannibals and find a way to guarantee that the seven prisoners survive.)

23 Prisoners and 2 Switches

A warden meets with 23 prisoners. He tells them the following: Each prisoner will be placed into a room numbered 1-23. Each will be alone in the room, which will be soundproof, lightproof, etc. In other words, they will NOT be able to communicate with each other. They will be allowed one planning session before they are taken to their rooms. There is a special room, room 0. In this room are 2 switches, which can each be either UP or DOWN. They cannot be left in between, they are not linked in any way (so there are 4 possible states), and they are numbered 1 and 2. Their current positions are unknown. One at a time, a prisoner will be brought into room 0. The prisoner MUST change one and only one switch. The prisoner is then returned to his cell. At any time t, given some N>0, there exists a finite t_0 by which time every prisoner will have visited room 0 at least N times. (In other words, there is no fixed pattern to the order or frequency with which prisoners visit room 0, but at any given time, every prisoner is guaranteed to visit room 0 again. If you’re still confused by this statement, ignore it, and you should be ok). At any time, any prisoner may declare that all 23 of them have been in room 0. If right, the prisoners go free. If wrong, they are all executed. What initial strategy is 100% guaranteed to let all go free?

Ace of Spades or the Two of Hearts

Take a shuffled deck of cards. Deal off the cards one by one until you reach any Ace. Turn over the next card, and note what it is. Which card has a higher probability of being turned over, the Ace of Spades or the Two of Hearts?

Coins in a Row

On a table is a row of fifty coins, of various denominations. Alice picks a coin from one of the ends and puts it in her pocket; then Bob chooses a coin from one of the (remaining) ends, and the altemation continues until Bob pockets the last coin. Prove that Alice can play so as to guarantee at least as much money as Bob.

Gasoline Crisis

There's a gasoline crisis, and the fuel stations located on a long circular route together contain just enough gas to make one trip around. Prove that if you start at the right station with an empty tank, you can make it all the way around.

Integer Rectangles

A large rectangle in the plane is partitioned into smaller rectangles, each of which has either integer height or integer width (or both). Prove that the large rectangle also has this property.

Lockers and Numbers

Lockers numbered 1 to 100 stand in a row at the school gym. When the first student arrives, she opens all the lockers. The second student then goes through and recloses all the even-numbered lockers; the third student changes the state of every locker whose number is a multiple of 3. This continues until 100 students have passed through. Which lockers are now open?

Signs in an Array

Suppose that you are given an $m \times n$ array of real numbers and permitted, at any time, to reverse the signs of all the numbers in any row or column. Prove that you can arrange matters so that all the row sums and column sums are non-negative.

Sum to 15

Alice and Bob alternately choose numbers from among $1,2, \ldots, 9$, without replacement. The first to obtain 3 numbers which sum to 15 wins. Does Alice (the first to play) have a winning strategy?

Logic Puzzles

Blue-Eyed Islander

There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).

Resources

The Art of Mathematics, Coffee Time in Memphis, Bela Bollobas

@suryatejagavva