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?
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 if there are 124 cards instead of the standard deck of 52?
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?
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 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?
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 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.
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.)
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?
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.
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.
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.
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?
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).