Archive for April 2011

The Cookie Monster Problem

by Olivier Bernardi and Tanya Khovanova

The Cookie Monster is a peculiar creature that appeared in The Inquisitive Problem Solver (Vaderlind, Guy & Larson, MAA, P34). Presented with a set of cookie jars, the Cookie Monster will try to empty all the jars with the least number of moves, where a move is to select any subset of the jars and eat the same number of cookies from each jar in the subset.

Even an untalented Cookie Monster would be able to empty n jars in n moves: to fulfill this strategy the Monster can devour all the cookies of one jar at a time. If the Monster is lucky and some jars have the same number of cookies, the Monster can apply the same eating process to all these identical jars. For example, if all the jars have the same number of cookies, the Monster can gulp down all of them in one swoop.

Now, let us limit our discussion to only cases of n non-empty jars that contain distinct numbers of cookies. If indeed all the numbers are distinct, can the Monster finish eating faster than in n moves?

The answer depends on the actual number of cookies in each jar. For example, if the number of cookies in jars are different powers of 2, then even the most talented Monsters can’t finish faster than in n steps. Indeed, suppose the largest jar contains 2N cookies. That would be more than the total number of cookies in all the other jars together. Therefore, any strategy has to include a step in which the Monster only takes cookies from the largest jar. The Monster will not jeopardize the strategy if it takes all the cookies from the largest jar in the first move. Applying the induction process, we see that we need at least n steps.

On the other hand, sometimes the Monster can finish the jars faster. If 2k−1 jars contain respectively 1, 2, 3, …, 2k−1 cookies, the Cookie Monster can empty them all in k steps. Here is how. For its first move, the Monster eats 2k-1 cookies from each of the jars containing 2k-1 cookies or more. What remains are 2k-1−1 pairs of identical non-empty jars containing respectively 1, 2, 3, …, 2k-1−1 cookies. The Monster can then continue eating cookies in a similar fashion, finishing in k steps. For instance, for k=3 the sequences of non-empty jars are: 1,2,3,4,5,6,7 → 1,1,2,2,3,3 → 1,1,1,1 → all empty.

Now we would like to prove a theorem that shows that the example above is the lowest limit of moves even for the most gifted Cookie Monsters.

Theorem. If n non-empty jars contain distinct numbers of cookies, the Cookie Monster will need at least ⌈log2(n+1)⌉ steps to empty them all.

Proof. Suppose that n jars contain distinct numbers of cookies and let f(n) be the number of distinct non-empty jars after the first move of the Cookie Monster. We claim that n ≤ 2f(n)+1. Indeed, after the first move, there will be at least n − 1 non-empty jars, but there cannot be three identical non-empty jars. That means, the number of jars plus 1 can’t decrease faster than twice each time.

Now here is something our readers can play with. Suppose a sequence of numbers represents the number of cookies in the jars. Which sequences are interesting, that is, which can provide interesting solutions for the Cookie Monster problem?

Share:Facebooktwitterredditpinterestlinkedinmail

Fractional Voting Power

I read an interesting article on the paradoxes involved in allocating seats for the Congress. The problem arises because of two rules: one congressperson has one vote, and the number of congresspeople per state should be proportional to the population of said state.

These two rules contradict each other, because it is unrealistic to expect to be able to equally divide the populations of different states. Therefore, two different congresspeople from two different states may represent different sizes of population.

Let me explain how seats are divided by using as an example a country with three states: New Nevada (NN), Massecticut (MC) and Califivenia (C5). Suppose the total number of congresspeople is ten. Also suppose the population distribution is such that the states should have the following number of congresspeople: NN — 3.33, MC — 3.34 and C5 — 3.33. As you know states generally do not send a third of a congressperson, so the situation is resolved using the Hamilton method. First, each state gets an integer portion of the seats. In my example, each state gets three seats. Next, if there are seats left they are allocated to states with the largest remainders. In my example, the remainders are 0.33, 0.34 and 0.33. As Massecticut has the largest reminder it gets the last seat.

This is not fair, because now each NN seat represents a larger population portion than each MC seat. Not only is this not fair, but it can also create some strange situations. Suppose there have been population changes for the next redistricting: NN — 3.0, MC — 3.4 and C5 — 3.6. In this case, NN and MC each get 3 seats, while C5 gets the extra seat for a total of 4. Even though MC tried very hard and succeeded in raising their portion of the population, they still lost a seat.

Is there any fair way to allocate seats? George Szpiro in his article suggests adding fractional congresspersons to the House of Representatives. So one state might have three representatives, but one of those has only a quarter of a vote. Thus, the state’s voting power becomes 2 1/4.

We can take this idea further. We can use the Hamilton method to decide the number of representatives per state, but give each congressperson a fractional voting power, so the voting power of each state exactly matches the population. This way we lose one of the rules that each congressperson has the same vote. But representation will be exact. In my first example, NN got three seats, when they really needed 3.33. So each congressperson from New Nevada will have 1.11 votes. On the other hand MC got four seats, when they needed 3.34. So each MC representative gets 0.835 votes.

Continuing with this idea, we do not need congresspeople from the same state to have the same power. We can give proportional voting power to a congressperson depending on the population in his/her district.

Or we can go all the way with this idea and lose the districts altogether, so that every congressperson’s voting power will be exactly proportionate to the number of citizens who voted for him/her. This way the voting power will reflect the popularity — rather than the size of the district — of each congressperson.

Share:Facebooktwitterredditpinterestlinkedinmail

How Many Hats Can Fit on Your Head?

Lionel Levine invented a new hat puzzle.

The sultan decides to torture his hundred wise men again. He has an unlimited supply of red and blue hats. Tomorrow he will pile an infinite, randomly-colored sequence of hats on each wise man’s head. Each wise man will be able to see the colors of everyone else’s hats, but will not be able to see the colors of his own hats. The wise men are not allowed to pass any information to each other.
At the sultan’s signal each has to write a natural number. The sultan will then check the color of the hat that corresponds to that number in the pile of hats. For example, if the wise man writes down “four,” the sultan will check the color of the fourth hat in that man’s pile. If any of the numbers correspond to a red hat, all the wise men will have their heads chopped off along with their hats. The numbers must correspond to blue hats. What should be their strategy to maximize their chance of survival?

Suppose each wise man writes “one.” The first hat in each pile is blue with a probability of one-half. Hence, they will survive as a group with a probability of 1 over 2100. Wise men are so wise that they can do much better than that. Can you figure it out?

Inspired by Lionel, I decided to suggest the following variation:

This time the sultan puts two hats randomly on each wise man’s head. Each wise man will see the colors of other people’s hats, but not the colors of his own. The men are not allowed to pass any info to each other. At the sultan’s signal each has to write the number of blue hats on his head. If they are all correct, all of them survive. If at least one of them is wrong, all of them die. What should be their strategy to maximize their chance of survival?

Suppose there is only one wise man. It is clear that he should write that he has exactly one blue hat. He survives with the probability of one-half. Suppose now that there are two wise men. Each of them can write “one.” With this strategy, they will survive with a probability of 1/4. Can they do better than that? What can you suggest if, instead of two, there is any number of wise men?

Share:Facebooktwitterredditpinterestlinkedinmail

Computer Jokes

* * *

Today I saw an ad — “A printer for sale” — handwritten. Hmm.

* * *

What do you call a motherboard on your spouse’s computer?
The motherboard-in-law.

Share:Facebooktwitterredditpinterestlinkedinmail