Two weeks ago, I formulated a Logelei I very much like. I also considered it extremely hard to solve. Well, one email I received had the correct answer.
Here is the solution to the problem I gave you on April, 2rd, 2017. I copied the formal part of the solution from the winner: Jörg.
The question was:
How can the criminals make sure that they all survive?
And the solution is surprisingly simple!
As soon as a gangster will see the nine images of all the other nine gangster, he will do the sum of all the numbers on these images and then add “his” number to the sum.
Then he applies the operation modulo 10 to the result and calls the resulting number. Every gangster does this during her or his interview.
This is how you can make sure that exactly one of the gangsters will give the number on his/her picture. The others will, of necessity, say a wrong number – but that is irrelevant, since it will suffice if one of them gives his correct number. That means they all will survive.
Well, as you see, you must never give up hope – once in a while, even mathematics can help.
Here is the formal description of the solution (after Dr. Rothermel).
• Let the number of gangsters be: N
• Let zi be the number assigned to the gangster I (not known to him). It is not necessarily unique and it is part of the set {0, 1, …, N-1} of which a minimum of one needs to be told in the end..
• Let S be the sum of all pre-defined numerals S = Σ zi
The gangsters agree upon the following procedure:
1. Initially, each of them gets a personal, unique number i (known to him/her) assigned to her/his picture from the set {0, 1, …, N-1}.
2. During the interview, every gangster builds the sum of all the numbers he/she can see – that is the (definite) total sum S minus his own (not known to him) numeral zi , i.e. S – zi . That is the only information at his disposal.
3. Since the gangsters are only interested in the numbers in the range {0, 1, …, N-1}, they will modulo N or the congruency relation ≡ N. Now each gangster will calculate an integer x such that:
x ≡ N i – (S – zi ) or
x = ( i – (S – zi )) mod N (I)
With this procedure, exactly one gangster will get his correct zi!
Proof:
S is congruent with a number s from the set {0, 1, …, N-1} or S ≡ N s, consequently, you can also write (I) as:
x ≡ N i – (s – zi )
Since no two N i’s are identical, one of them equal s, consequently, we have for one gangster:
x ≡ N zi.
both x and zi belong to the set {0, 1, …, N-1} which means they are not only congruent, but identical:
y = zi,
and that means this gangster will have the correct number for himself.
(Solution and proof by Dr. Jörg Rothermel)
Now I would recommend that you read the problem again and ponder it a little bit.
RMD
(Translated by Evelyn)
Loading ...