ZZZzzz...

I think I read this in a history book from the future, but I only remember vaguely, so it could as well be that I just made this up:

"In the beginning of the 21st century society began to change in a way that human history had never seen before. Polyphasic sleep was widely adopted. The usual day-night life cycle as mankind knew it was virtually over. The words day and night were abandoned and people began to talk about phases instead. Even earth's orbit and rotation were altered in a staggering space mission in 2031. Certain people that could not adapt to this new form of life decided to go into winter sleep. But this was only a temporary solution. Many of them finally signed up for cryonic stasis, most of them with explicit demand to never wake them up again. Those people were also called monos (from monophasic sleep) or sloths."

About Puzzles

When solving puzzles I often think the most frustrating thing is that there is very little theory about how to approach and efficiently solve them. Yet this is maybe why they are so interesting and allow one to be really creative. But sometimes I wish there had been more reasoning about the methodology of solving puzzles in my learning career than the sole perpetual advice that skill comes with practice.

Understand the question, see the challenge

I remember having spent a lot of time just figuring out what the heck this puzzle is asking for, in what direction the questions want me to go. This can of course be part of the puzzle itself, and maybe it is not that important after all to find the exact solution as fast as possible but rather just start thinking and go where you want to go. Only that degrees, school and partially also university are not always the right place for that.

The image in the mirror

A simple question I once heard and already asked some people is: "Why is left and right flipped in the mirror?" I then sometimes get a lesson in optics, how the light is reflected, a schematic drawing and the final answer that this is why of course left and right is mirrored, "You see?!". To be fair the question is not that obviously asking for a puzzle, but to make it more clear I could ask "Why of all things is it left and right? Why not top and bottom?" Then the puzzling question may become more obvious. I started to think about what two images are actually compared, that it is easier to not take myself as the subject to think with but somebody else I am looking at, once directly standing in front and once in the mirror. Then I thought about how I come from one image to the other and what needs to be changed to make top and bottom flip instead.

I found this example particularly interesting because at first it seems to ask for a simple technical explanation, but then when you see the actual implied challenge it gets much more puzzling.

No need to solve what is not asked for

Maybe not an advice I would give for trying to be creative, but unarguably efficiency is sometimes what is asked for.

One glass of water and one glass of orange juice

Assume both glasses a filled with the same amount. If you take one spoonful of the water glass, put it into the orange juice, mix it, take a spoonful of the mix and put it back into the water, will there be more orange juice in the water or more water in the orange juice or the same amount of each one in the other (disregarding density of the different fluids)? When I first started to solve this I made the mistake to actually starting to compute the fractions of each fluid in the other. While you may be able to solve it that way, remember that this is more than is asked for. The question is only if the parts are equal or in case not, which one is bigger.

There is actually a high level thought to easily solve this. If you take one spoonful from one glass to the other and then a spoonful of the same size again back, there must be the same total amount in each glass as before. Knowing that, if amount x is missing in the water glass because it is in the orange juice, the same amount of juice must be in the water glass, otherwise they would not have the same equal amount as they had before. Of course it can also be interesting to compute the actual fractions but it is a less efficient way to solve the original question.

Ask the neighbors

Sometimes a seeming detour can be a shortcut. It may be easier to compute something else, perhaps similar, and go on from there.

Power set

What is the sum of 2^0 + 2^1 + 2^2 + ... + 2^k? Not trivial to convert but in another representation it looks much simpler. This is of course the representation of a binary number with k digits each being 1. E.g. for k=4 it is 1111. To bring it into a simpler form the lots of 1 are bothering. Can this number be represented as a sum that has much less 1, maybe a fixed amount of 1, not depending on k? Well, 1111 is the same as 10000-1. And this form always has only two 1. So sum[i=0, k, 2^i] = 2^(k+1)-1.

The mathematical conversion for the interesting part would go something like this: 2^(k+1) = 2 * 2^k = 2^k + 2^k = 2^k + 2 * 2^(k-1) = 2^k + 2^(k-1) + 2^(k-1) = 2^k + 2^(k-1) + 2 * 2^(k-2) = ....

Of King Cakes and Dices

Last epiphany a friend asked me the following puzzle: "You have k king cakes and p persons eating. Each person gets exactly one equal sized piece of each cake, and of course each cake has exactly one king in one piece. What is the probability that each person has picked at least one king?"

Some facts

• Since we are asking for each person to have at least one king, k must be equal or bigger than p.
• Each cake is divided into p equal sized pieces, because each person gets one piece of each cake.
• The question "picking at least one king" is what makes the puzzle so difficult.

Abstraction

The problem is equal to repeatedly throwing a dice. Each king has the same chance to be picked by any person. So you could throw a dice with p surfaces for each king. You get a sequence of k numbers, say n(1)...n(k), each with value 1..p. The interpretation of this is that person n(i) has picked the king from the i-th cake. So now we deal with possible combinations of k digits, each having a value from 1..p.

Since all persons and cakes are the same, each combination has the same probability.

The question

... is now how many combinations are there, where each p is present at least once, meaning each person gets at least one king. The final probability is given by this value divided by the total number of combinations, which is p^k. E.g. when p=2, k=4, we have 4 bits and can represent 2^4 = 16 different numbers.

An example

Choose k=2, p=2. The combinations are:

1 1
1 2
2 1
2 2

The first and the last are not valid, both kings go to the same person and the other one gets none. So we have a probability of 2/4 = 50% that each person gets at least one king.

Choose k=4, p=3. Then the list of combinations is:

1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 1
1 1 2 2
...
3 3 2 3
3 3 3 1
3 3 3 2
3 3 3 3

A total of 3^4 = 81 combinations. As you can see it gets more complicated to write down all possibilities, so we are looking for a more abstract approach.

You could either try to find a formula for all valid combinations directly by finding all that have each p=1..3 occurring at least once, or you compute the inverse, the invalid ones, which are all combinations that have at least one p missing, and subtract it from the total count. An invalid combination would be 1 2 1 1 since 3 is not present which means person 3 gets no king. 1 2 3 x is valid for each x since every p is present.

I chose the second way. I found it easier to think with, but maybe the first works as well. The invalid combinations are those that either lack a 1, 2 or 3, let us call them m1, m2, m3. Each m has (3-1)^4 = 16 combinations. We could sum them up if they were disjoint. For example, 3 3 3 3 is counted twice, once in m1 and a second time in m2. So we have to subtract again all combinations that we counted twice. That is, combinations which are in two of m1, m2, m3. Let us call these possible sets m12, m23, m13. E.g. m12 is missing 1 and 2. There is actually only one combination for that: 3 3 3 3. m12, m23, m13 are disjoint, so we did not again count too much and are almost finished. The total amount of invalid combinations is then m1 + m2 + m3 - m12 - m23 - m13 = 3*(3-1)^4-3*(3-2)^4 = 45. And the final probability is (81-45)/81 = 36/81 = 4/9 ~ 44%.

Generic solution

The tricky part is to count m1, m2, ... mX. Since they are not disjoint, you can not simple sum them up, but have to compute the union. For that you need to know all the possible intersections between the sets. But luckily mankind has solved this before , and I could not explain it better. In short, to compute the union between a number of sets, you add all possible intersections between an odd number of the sets, and subtract all possible intersections between an even number of the sets. You also make use of combinatorics and the binomial coefficient. In our case A1 ∩ ... ∩ An means all combinations that are missing all of the digits 1..i. There are (p low n) such intersections and each counts (p-n)^k elements. So our final formula is:

sum((-1)^(n+1) * (p low n) * (p-n)^k), n=1..p

And this would be the nice graph for it if Mathematica did plot it:

plot sum[power[-1,n+1]*binomial[p,n]*power[p-n,k],{n,1,p}], p=1..10 and k=1..10

The final result is:

(p^k - sum((-1)^(n+1) * (p low n) * (p-n)^k)) / p^k, n=1..p

A question for you

Is it possible to construct a fair dice for all n?

The Microwave Trap

"Sometimes you have to shock your audience with something brilliantly primitive, only to be able to hit them really hard when you make your next creative punch."

– From Voices in your head by A. Strauss on February 3, 2011 –

Maybe, but I think most people still just do it for gaining attention.