puzzles

Puzzles

(expand all | collapse all)

all marbles are the same color

download

State precisely what is wrong with the following proof:

claim: For all positive integers n, it is the case that, in any set S consisting of n marbles, all marbles in S are the same color.

proof: By induction on n.

Base case (n=1): in any set S consisting of a single marble, it is trivially true that all marbles in S are the same color, because only one marble is in S.

Induction step (n>1): Assume inductively that the claim is true for all sets of n-1 marbles. Under this assumption, we will prove the claim for all sets of n marbles.

Let S be any set of n marbles. Denote the marbles in S as M(1), M(2), ..., M(n). That is, M(1) is the first marble, and so on. Form two size-(n-1) subsets of S as follows:

S1 = {M(1), M(2), ..., M(n-1)}
S2 = {M(2), M(3), ..., M(n)}.

Since S1 has n-1 marbles, by the inductive assumption all marbles in S1 are the same color. Thus, M(1), M(2), ..., M(n-1) are the same color.

Likewise, all marbles in S2 are the same color. Thus, M(n-1) and M(n) are the same color.

Thus, M(1), M(2), ..., M(n) are all the same color.
choose the max of two numbers

download

I write two different numbers, one on each hand.

You choose one of my hands at random, I show you the number on that hand.

You now guess whether the number you've seen is larger than the number you haven't seen.

Find a strategy for guessing such that, no matter what two numbers I write, you have GREATER THAN a 50% chance of being correct.
cover a checkerboard with three pieces

download

You are to cut out some pieces of paper.

You must be able to place your pieces of paper on an 8x8 checkerboard so that they exactly cover the checkerboard, minus _any_ one square.

That is, once your pieces are cut, if I identify to you _any_ of the squares on the checkerboard, you must be able to arrange all your pieces of paper (flat, not folded) on the checkerboard so that:

a) the pieces of paper don't overlap
b) the pieces of paper don't cover any area outside the checkerboard
c) the pieces of paper cover all of the checkerboard except the square I chose

The problem: figure out how to do this with three pieces of paper.

For example, it is easy to see how to do this with 63 pieces of paper -- use 63 1x1 squares of paper. Or, 32 pieces --- use a 4x8 piece and 31 1x1 pieces...
dumb soldiers simultaneously firing

download

2^N (that's two raised to the power of N, where N can be arbitrarily large) soldiers are arranged shoulder to shoulder facing outwards in a circle. Each soldier has limited memory - s/he can only remember O(1) bits of information, and can give or receive information only to the soldier to his or her left and the soldier to his or her right. Time proceeds in discrete rounds: time 0, time 1, time 2, .... In each round, each soldier can communicate only O(1) bits of information with the two soldiers to the right and left. No soldier knows how many soldiers there are.

At time 0, a general taps one of the soldiers on the shoulder and says "go". After that, soldiers communicate (as the time steps pass) according to some agreed upon protocol. At some later time, all soldiers simultaneously raise their guns and fire. (No soldier fires before this time.)

The challenge problem is to determine a protocol that the soldiers can use to accomplish this, subject to the constraints outlined in the first paragraph.

An example that doesn't quite work would be:

(1) the first soldier (the one that the general taps at time 0), at time 1 taps the soldier to his or her right. At time 2, that soldier in turn taps the soldier to his or her right, and so on. In this phase, each soldier follows the protocol "when I am tapped on my left shoulder, I will, next round, tap the soldier to my right on his or her left shoulder."

(2) while this is happening, the first soldier counts the time steps as they pass. when, eventually, he is tapped on his left shoulder by the soldier to his left, he knows that the number of soldiers is equal to the number of time steps passed. let this number be 2^N. In the next round, he turns to the soldier to his or her right and says "fire after 2^N-1 time steps." That soldier waits a round and then says to the soldier to his or her right "fire after 2^N-2 time steps. In general, each soldier, once s/he is told "fire after X time steps", waits a time step and turns to his or her right and tells the next soldier "fire after X-1 time steps". each soldier, after being told "fire after X time steps" also does the following: s/he counts down X time steps, then fires.

That's an example protocol, but it doesn't fit the criteria outlined for two reasons. First, it requires each solder to communicate more than O(1) bits of information in a round. (To communicate a number as large as 2^N requires N bits, and N can be arbitrarily large.) Second, it requires each soldier (when counting down) to remember up to N bits of information.

The protocol you design must require each soldier to remember, and to communicate, only O(1) bits of information at any given time.
five pirates divide the booty

download

5 pirates discover 100 gold coins.

Their protocol for dividing the loot is as follows.

The most senior pirate proposes an allocation (how much each pirate should get). All the pirates vote. If at least half agree to the allocation, then that is the allocation.

Otherwise, the senior pirate is executed and the process is repeated with the remaining 4 pirates (the second-most-senior pirate proposes an allocation, etc.), then, if necessary, with the remaining 3 pirates, and so on. If it gets down to the least senior pirate, she gets it all.

Assuming that each pirate has the following priorities, what will the most senior pirate propose?

priorities, in order of importance:
1) stay alive
2) get as much gold as possible
3) kill as many other pirates as possible
flipping discs

download

You have n discs labeled 1,2,3,...,n (not necessarily in that order),
stacked one on top of each other (sort of like towers of hanoi).

The basic operation you can do on the stack is the following:
take some disc, and all the discs above it, and flip over that
part of the stack. For example, you can take the following
stack:

3
1
4
5
6
2
-

and, by applying the basic operation starting at disc 5, you can get

5
4
1
3
6
2
-

The problem has two parts:

(a) Show that, no matter how a stack of n discs starts out, by applying
the basic operation repeatedly, you can get the discs stacked in order
(1 on top, 2 next, ..., n on the bottom) using at most 2*n basic operations.

(b) Show that, for any n, there is some way to order a stack of n discs
so that no matter how you apply the basic operations, at least n
basic operations are required to get the discs ordered. (In this part,
you have to specify a particular order that requires at least n basic
operations, AND you have to prove that there is no sequence of less
than n operations that orders the stack.)
gas to market

download

You have a truck and 300 gallons of gas. You have to transport the gas, using the truck, to sell at the market 100 miles away. Your truck can carry at most 100 gallons of gas at any time, and it consumes 1 gallon of gas for every mile it travels. What's the maximum amount of gas you can get to the market? You have spare containers so you can leave gas along the way and come back and pick it up if you like.

For example, you could load up your truck with 100 gallons of gas and drive to the market. But then when you got to the market, you'd have no gas to sell, and worse, you would be stranded and could not get back to the rest of your gas.
guess the fifth card

download

The audience chooses 5 arbitrary cards from a regular 52-card deck, and hands those 5 cards to a magician.

The magician chooses 4 cards, then reveals those 4 cards one at a time to his assistant.

The assistant promptly tells the magician what the 5th card is.

QUESTION 1: Figure out how to do this. That is, figure out how to choose, for any size-5 subset of cards, an ordering of 4 of those cards so that the assistant can tell just from the 4 cards and the ordering of those 4 cards what the 5th is.

QUESTION 2: What's the largest deck (more than 52 cards) that this trick can be done with, assuming that the magician will be given 5 cards and he must choose 4 to reveal?
handshakes after the party

download

N+1 couples attend a dinner. At the end of the dinner, one person (Alice) asks each other person to write down the number of distinct people with whom he or she shook hands at the dinner. Surprisingly, all numbers 0,1,2,...,2N are written down. Assuming that no person shook hands with their partner, how many people did Alice shake hands with at the dinner?
save the pirates

download

N pirates stand in a line, facing forward, so that
pirate #1 sees pirates 2-N,
pirate #2 sees pirates 3-N,
pirate #3 sees pirates 4-N,
etc.

Each pirate wears a hat, each hat is either red or blue, but no pirate knows the color of his own hat. More specifically, each pirate knows only the colors of the hats on the pirates that he sees.

An executioner asks each pirate, in order (pirate #1, then #2, etc), what the color of the pirate's hat is. Everyone can hear the pirate's answer. If the pirate answers correctly, the executioner spares the pirate. Otherwise, executioner executes the pirate.

The pirates have anticipated that they might face this situation, and have agreed on a protocol for answering in advance. Their goal is to have as few pirates killed as possible. The puzzle is to figure out what is the best they can do. That is, describe a protocol that minimizes the worst-case number of pirates killed. (Here worst-case is over all possible ways of coloring the hats red or blue.)

For example, one protocol would be that pirate #1, when asked the color of her hat, answers with the color of pirate #2's hat. Pirate #2 hears what pirate #1 says, thus learning her own hat color, and then when she is asked, she simply gives the correct answer. Continuing in this way, half of the pirates lives are saved (in the worst case). Assume that the pirates cannot tell if a pirate is executed or not.
sit down if your hat is black

download

There are 30 students arranged in a circle, with their eyes closed. The instructor places a hat on each student's head. 20 of the hats are black, 10 are white. The students then open their eyes. They can see each other student's hat, but not their own hat.

The instructor says "At least one of you is wearing a black hat."

He then gives the following instruction:

"Any student who has determined that his or her hat is black, please sit down."

Of course, no one sits down, because nobody can see his or her own hat. (There are no mirrors in the room, and the students are not allowed to discuss what they see.)

A minute later, the instructor repeats the previous instruction:

"Any student who has determined that his or her hat is black, please sit down."

No-one moves.

The instructor repeats this same instruction every minute for the next thirty minutes.

QUESTION 1: what happens, and when?

QUESTION 2: State exactly what new piece of information the instructor provided when he said "At least one student's hat is black." After all, this fact was already known by every student.
stop before red card

download

I randomly shuffle a deck of cards, then start turning over the cards one at a time. At some point, you can stop me. If the next card (the one on top of the remaining deck) is red (hearts or diamonds), then you win, otherwise you lose. If you never stop me, you lose.

Prove or disprove: there is a strategy that you can follow so that you will win with probability GREATER THAN 50% (assuming the deck is randomly ordered at the start).

puzzles

Puzzles

See also