Brainteasers

Brainteasers become more and more popular in these days. You hear them from friends, in bars, read them on blogs and they are even used in job interviews to puzzle the candidates. Some of them are easy and some of them are tricky and some of them are really hard.

A common teaser for example is:

"A melon weights 1200gr and contains 99% water. Suppose that after one week the amount of water has reduced to 98%. What is the new weight of the melon?"

[Spoiler Start: White-on-White / Mark with the mouse]
It is 600gr! Just observe that the $1200$gr is made up of  $99\%$ water and $1\%$ melon-meat. That are $1188$gr water $12$gr melon-meat. After one week the weight of the melon reduces the $x$gr, whereof $y$gr are water and still $12$gr melon-meat. And it is known that the $y$gr water are now $98\%$, hence the $12$gr melon-meat must be $2\%$. But if $2\%$ are $12$gr, then $100\%$ are $600$gr.
[Spoiler End] 



Another one is for example the following:

 "A car completes the first round on a speedway with an average speed of x mph. How fast must it be on the second round in order to double its overall average speed?"

[Spoiler Start: White-on-White / Mark with the mouse]
It is impossible. Assume that the round on the speedway has length $n$ miles. W.l.o.g., i assume that i use one hour for the first round, which leads to an average speed of $n/1 = n = x$ mph. If i double my speed on the second round, then i only need $1+1/2$ hours for two rounds, hence i get an average speed of $2n/(1+1/2) = x'$ mph. If i drive four times the speed on the second round, then i only need $1+1/4$ hours for two rounds, hence i get an average speed of $2n/(1+1/4) = x'$ mph. In general, if i drive $d$ times the speed from the first round, i have an overall average speed of $2n/(1+1/d) = x'$. In order to double my average speed from the first round to $2x = 2n$ in our example, it must hold $2n/(1+1/d) = 2n$, hence $1/d = 0$, which is impossible.
[Spoiler End]

In job interviews normally Brainteaser are used that could be solved with a short answer, so that the candidate is not forced to do some time consuming calculations. For example:

"Why are manhole covers are typically round?"

[Spoiler Start: White-on-White / Mark with the mouse]
There is more than one good answer, but the most common one is, that if it is round it can not fall through its circular opening.
[Spoiler End]

Or more funny stuff:

"Before Mt. Everest was discovered, what was the highest mountain in the world?"

[Spoiler Start: White-on-White / Mark with the mouse]
Mt. Everest. It just wasn’t discovered yet.
[Spoiler End]

However, there are some really hard brainteaser. One of my favorite is the Lucifer's Puzzle. It probably can not be solved in a short time, but if you like brainteaser, this is worth to give it a try:

"Both Euler and Gauss sitting in hell, when Lucifer promises freedom to them, if they can find out the two integer numbers between 1 and 100 which Lucifer has imagined. He tells Gauss the product and Euler the sum of the two numbers. Then a dialog rises:

Gauß: „I don't know the numbers.“
Euler: „That was clear to me.“
Gauß: „Now I know them.“
Euler: „Then I know them too.“

 "
It seems surprising that this four sentences are indeed enough to uniquely determine the two numbers. However, you must always keep in mind, that Euler and Gauss behave logically.

The rest of the post shows a solution to Lucifer's Puzzle, so if you want to give it a try, stop reading here.

#### Spoiler - Alert ######

The german Wikipedia [1] article offers also a good explanation. We denote the two numbers in question by $a$ and $b$, with $1 < a,b < 100$. The goal is to get the two numbers, it does not matter which is $a$ and which $b$. Gauss gets $P = a\cdot b$ and Euler gets $S = a+b$.
We view that challenge through Euler's eyes and can only find the integers $a$ and $b$ after Euler last sentence. Note that we have even less information than Gauss and Euler, since we do not know $P$ and $S$.

The first sentence: Gauß: „I don't know the numbers.

Gauss has the product which he can factor into its prime factors. Note that $P$ can not be a prime number since $a$ and $b$ are larger than $1$. If the factorization of $P$ has

1. exactly two prime factors
2. one prime factor $> 50$

then Gauss could immediately reveal the integers $a$ and $b$. In case 1. $a$ and $b$ would be simply the two obtained prime factors and in case 2., the large prime factor $p_i > 50$ must be equal to $a$ or $b$, since otherwise any divisor that contains $p_i$ is larger than $100$, which is not possible for $a$ or $b$. So Gauss can not have a product of type 1. or 2. So $P$ must have at least $3$ factors and they are all less than $53$. Gauss is already very close to the solution, but he can not decide how to form the two factors.

The second sentence: Euler: „That was clear to me.“

From this sentence we learn, that Euler already knew that Case 1. and Case 2. (i.e., exactly two primes factors or one factor $> 53$) are not possible. I.e., that means, that Euler must be able to deduce from his sum $S$, that $P$ can not have two prime factors or one prime factor $> 50$. This excludes already many possibilities, as explained next.

1. If $S = 198$, then the only possible combination would be $a = 99$ and $b = 99$. Since $ab = 99\cdot 99 = 9801 = 3^4\cdot 11^2$. But this product could be uniquely decomposed by Gauss into a solution $ab$ with $a,b < 100$ and that is $a = b = 99$. Since Euler reveals, that he can conclude that Gauss has no chance to find a potential valid factorization, it is $S \neq 198$.

2. If $S = 197$, then the only possible combination would be $99+98$. Since $ab = 99\cdot 98 = 9702 = 2\cdot 3^2\cdot 7^2\cdot 11$. But this could be uniquely decomposed by Gauss into a solution $ab$ with $a,b < 100$ and that is $98$ and $99$. Since Euler reveal, that he can conclude that Gauss has no chance to find a potential valid factorization, it is $S \neq 197$.

3. If $99 < S < 197$. Starting from $S = 196$, the sum could be created by $196 = 97 + 99$, hence $P=99\cdot 97$. Since $97$ is a prime number and $> 50$, i already explained that this can not happen, since Gauss could use this to reveal $a$ and $b$. This argument can be applied for any $98 < S < 197$, since $195 = 97 + 98$, $194 = 97 + 97$, ..., $99 = 97 + 2$. So it is $S < 98$.

4. If $54 < S < 98$. In this case one integer could be $53$ which is prime, hence $S = 55,...,97$ could be created by $53+2,53+3,53+4,....,53+44$, which could bring Gauss into the situation to deduce the prime factors. Hence $S < 55$.

5. If $S < 55$ and even. The Goldbach Conjecture says, that all even number could be written as the sum of the primes. It is unproven but verified up to a large bound (especially larger then 55), hence $S$ can not be an even integer less than $55$. So $S < 55$ and odd.

6. The Goldbach Conjecture is about the sum of two odd primes. But if we allow also $2$, then all odd integer of the form $p + 2$ for a prime $p$, could not be equal to $S$.

7. $S = 51 = 17+34$ and hence $P$ could be $17\cdot 34 = 2\cdot 17^2$, which could only uniquely decomposed into $17$ and $34$ hence is not possible.

Hence, we know that $S$ is

1. $ < 55$
2. odd
3. not equal to $p+2$
4. $\neq 51$

This leaves the set
\begin{equation}
S \in \{11,17,23,27,29,35,37,41,47,53\} = T
\end{equation}
Note that since $S$ is odd, either $a$ is odd and $b$ is even or vice versa.

The third sentence: Gauß: „Now I know them.“

Gauss also reconstructed the set $T =\{11,17,23,27,29,35,37,41,47,53\}$ from Euler's sentence. And he only could be able to know $a$ and $b$ at this point, if from all the possible factorization of $P$ in two factors, there is only one which yields a sum in $T$. And this fact he reveals with the third sentence.

The fourth sentence: Euler: „Then I know them too.“

Gauss already finished his challenge, but Euler made the same consideration as we did until know. So with Gauss last sentence, he now knows that $P$ can only be factored in one way such that the sum of the factors is in $T$. This is the final information he needed. Note that Euler also reconstructed $T$ despite knowing  $S$.
The last sentence reveals, that now also Euler knows $a$ and $b$. So the sum $S$ must have the unique property that

1. for the correct $a$ and $b$ with $a+b=S$ and $ab=P$, all other factorizations of $P$, i.e., $a'b'=P$ it must hold $a'+b' \notin T$.
2. for the wrong $a$ and $b$ with $a+b=S$ and $ab=P$, at least for one other factorization of $P$, i.e., $a'b'=P$ it must holds that $a'+b' \in T$ (that means also, that there MUST be another representation of $P$)

This two rules are posing a huge restriction and the only thing that is left for us, is to check this two rules for all integers in $T$. Whenever an integer from $T$ has two partitions $a+b=S=a'+b'$ whereof $ab$ and $a'b'$ have both no different factorization such that the sum of the other factors yields an integer in $T$, this integer can not be the correct $S$.

$S = 11 = 2 + 9 = 4 + 7$. But neither $8\cdot 3=24$ and $4\cdot 7=28$ have another valid factorization in $ab$ (note either $a$ even and $b$ odd). So $S=11$ is excluded.

$S = 23= 4 + 19 = 16 + 7$. But neither $4\cdot 19=76$ and $16\cdot 7=102$ have another valid factorization in $ab$ (note either $a$ even and $b$ odd). So $S=23$ is excluded.

$S = 27= 4 + 23 = 8 + 19$. But neither $4\cdot 23=92$ and $8\cdot 19=152$ have another valid factorization in $ab$ (note either $a$ even and $b$ odd). So $S=27$ is excluded.

$S = 29 = 13+16 = 12+17$. Both $12\cdot 16$ and $12\cdot 17$ have no other valid factorization, hence $S=29$ is excluded.

What is left are the integers $17,35,37,41,47,53$. For the last $5$, i.,e., $T'=\{35,37,41,47,53\}$ it holds the following: Since all this integer are $> 31$, all this integers can be written as $29 + x$ and $31+x'$. Note that $P$ has at least $3$ prime factors. Hence for $29+x=S$, one has $29\cdot x$. And this is already the only way to factor $P$. Because if one factor of $x$ is multiplied to $29$, this would be $> 58$
and the sum could not be in $T'$, because the largest possible sum is $53$. The same argument holds for the $31+x'$. So every integer from $T'$ has at least two ways to write them as $a+b$ and $a'+b'$, whereof the products $ab$ and $a'b'$ have no other factorization.

What is left is $S = 17$. For this we have:

1. $17 = 2 + 15 = 2\cdot 15 = 30 = 6\cdot 5$ and $6+4 =11\in T$
2. $17 = 4 + 13 = 4\cdot 13 = 52 $ No other representation.
3. $17 = 6 + 11 = 6\cdot 11 = 66 = 2\cdot 33$ and $2+33=35\in T$
4. $17 = 8 + 9 = 8\cdot 9 = 72 = 3\cdot 24$ and $3+24=27\in T$
5. $17 = 10 + 7 = 10\cdot 7 = 70 = 2\cdot 35$ and $2+35=37\in T$
6. $17 = 12 + 5 = 12\cdot 5 = 60 = 3\cdot 20$ and $3+20=23\in T$
7. $17 = 14 + 3 = 14\cdot 3 = 42 = 2\cdot 21$ and $2+21=23\in T$

So $17$ fulfils all requirements. It only has one way to write $17 = 4+13$ and all other summands $a'$ and $b'$ with $a'b'=P'$ have at least one different way to factorize $P'$ such that the sum of this other factors is also in $T$.

So the integers Lucifer imagined are $4$ and $13$.

[1] http://de.wikipedia.org/wiki/Luzifer-R%C3%A4tsel