Vor zwei Wochen habe ich eine Logelei formuliert, die mir besonders gut gefällt und die ich als sehr schwierig empfand. Mich erreichte tatsächlich eine richtige Lösung.
Hier ist die Lösung zu dieser Aufgabe vom 3. April 2017. Den formalen Teil habe ich aus der Formulierung von Jörg – dem Gewinner – übernommen.
Die Frage war:
Wie können die Ganoven ihr Überleben sicher stellen?
Und die Lösung ist
🙂 Verblüffend einfach!
Die 10 Ganoven ordnen jedem von sich z.B. durch Abzählen eine eindeutige Zahl zwischen 0 und 9 zu!
Wenn ein Ganove dann die jeweils neun Bilder der anderen neun Ganoven sieht, addiert er die Zahlen auf diesen Bildern zusammen und addiert „die ihm gegebene“ Zahl auf die Summe der 9 sichtbaren Zahlen.
Dann wendet er auf das Ergebnis die Operation modulo 10 an und nennt die sich ergebende Zahl (Ziffer). Das macht jeder Ganove bei seinem Interview so.
So wird sicher gestellt, dass genau einer der Ganoven die Zahl nennt, die bei ihm auf dem Bild steht. Der Rest sagt zwar zwangsläufig die falsche Zahl – das stört aber nicht, denn es genügt ja wenn einer die Zahl „errät“, damit alle überleben.
🙂 Man soll also die Hoffnung nie aufgeben – ab und zu hilft sogar die Mathematik.
Die formale Beschreibung der Lösung (nach Dr. Rothermel).
• Gegeben sei die Anzahl der Ganoven: N
• Sei zi die dem Ganoven i gegebene (für ihn) geheime und nicht notwendigerweise eindeutige Ziffer aus der Menge {0, 1, …, N-1} von denen mindestens eine zu erraten ist.
• Sei S die Summe aller vergebenen Ziffern S = Σ zi
Die Ganoven verabreden jetzt folgendes Verfahren:
1. Jeder erhält im Vorfeld eine persönliche (und ihm bekannte) eindeutige Zahl i aus der Menge {0, 1, …, N-1} zugeteilt.
2. Bei der Befragung bildet jeder Ganove jetzt die Summe der Ziffern die er sehen kann – das ist die (eindeutige) Gesamtsumme S minus seiner (ihm unbekannten) Ziffer zi also S – zi . Das ist die einzige Information die er zur Verfügung hat.
3. Da die Ganoven nur an Zahlen im Bereich {0, 1, …, N-1} interessiert sind, verwenden sie modulo N oder die Kongruenzrelation ≡ N. Jeder Ganove ermittelt jetzt eine ganze Zahl x, derart dass folgendes gilt:
x ≡ N i – (S – zi ) oder
x = ( i – (S – zi )) mod N (I)
Mit diesem Verfahren bestimmt genau ein Ganove sein zi richtig !
Beweis:
S ist kongruent mit einer Zahl s aus der Menge {0, 1, …, N-1} oder S ≡ N s also schreibe ich (I) um:
x ≡ N i – (s – zi )
Da sich alle N i’s voneinander unterscheiden, muss eines gleich s sein, damit gilt für einen Gauner:
x ≡ N zi.
Jetzt sind sowohl x als auch zi aus der Menge {0, 1, …, N-1} damit sind sie nicht nur kongruent sondern auch gleich:
y = zi,
und das bedeutet, dieser Ganove bestimme seine Ziffer korrekt.
(Lösung und Beweis sind formuliert von Dr. Jörg Rothermel)
Jetzt empfehle ich, noch mal die Aufgabe zu lesen und ein wenig darüber nachzudenken.
RMD
Wird geladen ...
15 Antworten
Before seeing this solution, but after wasting some time, I found a more elegant solution, (with no maths).
For n from 1 to 9 each bandit who sees n different card numbers tries number n.
I have explained this to Roland per email,
but here I leave the proof to you readers.
Sorry, I should not have published so fast. I made a mistake. I think I can correct it without much loss of elegance. But now I need to sleep.
In bed, I thought I found a mistake, but this elegant solution is OK.
Note that the bandits‘ tries can come in any sequence.
Roland, do I get a share of the victory?
Let us say:
Five bandits have 8
Five bandits have 9
So everybody sees 2 different numbers.
But nobody hast the 2.
And all have to die.
By the way: We spoke from 10 bandits and numbers from 0, 1 … until 9. But this seems to be a formal mistake.
What’s about evéy bandit has the 5? So every nines of them always see nine times the 5. Should he say 0 or 1?
May be I don’t understand the „solution“?
Roland, stimmt die Lösung? Meine Ganoven (0…9) haben (2,8,3,1,5,0,3,8,2,5). Die Summe ist 37, sie raten also (5,0,6,9,6,2,0,6,3,1). Wo ist der Denkfehler?
Lieber Michael,
es ist ganz einfach. Zwar ist die Summe aller 10 vergebenen Zahlen immer dieselbe (dies ist auch der Ausgangspunkt beim Beweis). Sie ist aber nicht die Basis für das vereinbarte Vorgehen. Die Basis für den Algorithmus ist jedoch immer die Summe von 9 aus 10 Zahlen. Jeder Ganove sieht doch immer nur die 9 Zahlen der 9 Komplizen und addiert diese. Und wendet darauf den Algorithmus an. Und so gibt es immer genau einen, der seine eigene Zahl erwischen muss.
Klar geworden?
In Deinem Beispiel sehen die beiden mit der 2 eine Summe von 35, die beiden mit der 8 eine Summe mit der 29 usw. Das vereinbarte Vorgehen wenden sie auf die Summe der Zahlen der 9 Komplizen an, die sie sehen. Darauf addieren sie die
Hallo Roland,
Genau, der 1. Ganoven sieht als Summe 37-2 (seine Zahl)=35, addiert dazu 0 (seine vereinbarte Nummer) und erhält damit Module 10 die 5 usw.
Ich glaube, ich habe das Problem gefunden, die Ganoven dürfen nicht ihre Zahl auf die Summe addieren, sondern müssen die Summe von ihrer Zahl abziehen (so ist es auch im Beweis unten), dann klappts auch mit meinem Beispiel.
🙂 Stimmt! Die Summe wissen sie ja auch gar nicht, sie sehen ja nur die anderen 9 Zahlen, können also nur die Summe der anderen 9 berechnen, dies ohne ihrer eigenen und ihnen ja unbekannten Zahl. So gibt es auch in jeder Kombination nach diesem Verfahren auch zwingend immer nur einen (!) Ganoven, der seine eigene Zahl richtig angibt, alle anderen haben sie zwingend falsch. Aber einer genügt ja, um alle zu retten. Bei mir vorstellbar anderen Methoden ist es immer gut möglich, dass mehr als einer seine Zahl richtig errät, aber eben auch dass keiner seine Zahl richtig angibt. Das bedeutet dann ja den Tod für alle.
Yes, Roland, my attempted solution was irreparable rubbish. 52 years ago, I switched from maths to programming. This seems to have influenced how I approach such problems, (stepwise, looking for patterns, rather than holistically). Now, I must try to rehabilitate myself. This problem is still interesting after publication of the elegant mathematical solution.
I name the elegant solution “M”, for “Maths”, “Modulo”, or “Mengen”.
M only gets one card number right. If that bandit forgets his bandit number, or miscalculates, all die. If any one bandit gets it wrong, all die with probability 10%. If the card numbers are allocated randomly, this 10% can hardly be improved. Can anybody prove that 10% is optimal? Each bandit knows about his card number only that it is 0 to 9. So, the ten bandits together are needed to try all possibilities. But random allocation is difficult. Dice rarely have ten sides. All 10 bandits just guessing would fail with probability about 35%.
If the numbers are allocated by humans, one can look for patterns. For instance, lazy allocation may give every card the same number, or instead all ten numbers may be used. No bandit can be sure that such a pattern reveals his card number, but it might be worth a try. Dr Rothermel stated that, after adding the visible numbers together, they give no further information. Regarding each bandit’s own card number, that is true provided they are randomly allocated, (which was not exactly what the problem said). Even if they are randomly allocated, they still reveal information about what the other bandits see, (but the information cannot be passed on). For instance, if a bandit sees nine different numbers, then nine or ten different numbers are used, and each other bandit can see eight or nine of them. For instance, if a bandit sees one number nine times, then one or two different numbers are used, and each other bandit can see both or one. In neither of these cases is the extra information useful. With random allocation, both these cases are rare, and the cases where ten numbers or only one are used, are even rarer.
For every attempt to detect a pattern, there seems to be a similar pattern that defeats the attempt. This reminds me of the wonderful Gödel/Turing incompleteness theorem, as explained by Douglas Hofstadter in Gödel, Escher, Bach: An Eternal Golden Braid, ( Gödel, Escher, Bach: ein Endloses Geflochtenes Band). Any series of algorithms has a problem it cannot solve; any series of problems has an algorithm that can solve them. (I hope my short version of the theorem is acceptable)?
A probabilistic algorithm can be better than a certain one. Consider testing whether a huge number is prime. The fastest certain algorithm, (polynomial time), is slower than a probabilistic algorithm. And the probability of failure is less than the probability of the slower calculation being stopped by an asteroid crash! (See “Quantum computing since Democritus” by Scott Aaronson).
Roland, I find this problem strangely confusing. I presume you produced the simplified version of M, published next to the picture of Rothermel. I explain later why I think it is wrong. M involves subtracting each bandit number from the sum of card numbers seen by him. But your simpler version involves adding these two together.
Next, I have some sort of an explanation, for non-mathematicians, of the good solution, M.
“x modulo n” means the remainder when x is divided by n.
So, “x modulo 10” means “the last digit of x”, (or, “the first digit” for Arabs and others who read right to left).
With 9 bandits and 9 cards, one would calculate with “modulo 9”.
Working with “modulo”, the usual rules hold for adding and subtracting some numbers, in that the result is independent of the sequence. Also, modulo 10, the tens can be thrown away at every stage, but should also be thrown away at the end. Note that 6 = -4. And -3 = 7. Etc. The problem is written with ten bandits, rather than 9 or 11, to make it simpler for people used to working with the decimal system. Numbers 0 to 9 simplify the solution. But essentially the same solution could be made to work with 1 to 10, or even with ten letters, rather than numbers.
Consider the sum of all the card numbers used.
If any bandit knew this he could calculate his correct card number.
He only needs to know the last digit, since his card number is 0 to 9.
So, each bandit gets a unique digit, (0 to 9), and adds it to the sum of the card numbers he can see.
This lets each bandit make a different guess at the last digit, s, of the sum of all card numbers. He then uses this guess to calculate the corresponding card number. This last digit, s, is a fixed target for guesses, it does not change from one bandit to another.
(I show later how this can still work if each bandit subtracts his number, rather than adding it)!
I hope that is a help in understanding the method and proof of Dr Rothermel?
But there is the further difficulty. Where does the method come from that is described next to the picture?
Did Roland construct it? It is (significantly?) different from Rothermel’s.
It adds the bandit numbers to Si, rather than subtracting. This seems more natural, since we are looking for S, which is bigger than Si. Anyway, we all learn addition before subtraction. But with such a difference, can both methods be right?
Yes, they can! The secret is that “modulo 10” has the effect that subtracting 0 to 9 is the same as adding 0 to 9, but in a different order, (since -1 = 9 , -2 = 8 , etc.). A different bandit will succeed, (except for cases 0 and 5). But that does not matter; bandits are equal except for the bandit numbers. Each bandit then must predict his card number according to whether he has added or subtracted. (Any other permutation of bandit numbers could also be used instead).
A Roland(?) bandit predicts x = ( i + Si ) mod 10 This is wrong.
A Rothermel bandit predicts x = ( i – Si ) mod 10 This is OK.
Either would still work as well with “-i” instead of “i”, as explained above, but -Si must be used to predict the card number.
The first method misses a trick at the end. x = – ( i + Si ) mod 10 would be OK.
It is tricky to find an example where it goes wrong.
Suppose the successful bandit has number 0 or 5. Then plus or minus makes no difference. This includes all cases where all ten card numbers are used. It also includes cases where all bandits have the same number. Both methods try a variety of card numbers, so with the first method, about 65% will succeed purely by chance. But I calculate that it fails with card numbers five times 7, then 5 times 4.
I shall try to find another solution without addition or subtraction. For instance, write the card numbers in binary, and use the computer instruction “XOR” to combine them. This works well with 4 or 8 bandits. But it seems messy with 10.
My previous comment, and this and the next were written before I saw the last couple of other comments.
I am interested in a solution using (XOR, exclusive OR), instead of addition and subtraction.
XOR is well explained in https://en.wikipedia.org/wiki/Exclusive_or
and in the shorter German version. (Beware of the underline in “Exclusive_or”).
(An XOR gate acts on two bits, it delivers a 1 if the bits are different, otherwise it delivers a 0.
Here I work in binary, which is the way most numbers are handled these days.
Organise bandit numbers as in the solutions already seen.
Now each bandit does XOR on his bandit number and all the card numbers seen.
(To do this, he writes all ten numbers, properly aligned, in a column, 4 bits wide.
Then, for each of the four columns of single bits, he generates a single bit, which is 0 for an even number of 1 bits in the column, and is 1 for an odd number).
The resulting 4 bit number, modulo 10, is the card number for him to try.
People are used to decimal calculations, but for computers, binary is simpler.
With 2, 4, 8, 16, … bandits this method needs no modulo stuff.
With 10 bandits, modulo 10 is needed, for instance because 9 XOR 6 = 15.
This works the same way as the other solutions. All ten card numbers XORed together give a fixed number to aim at. XOR is simpler than add and subtract, since it is its own converse.
XOR (m, n, m) = n
What about using unary instead of binary? Here a number is represented by the given number of ones.
I put the ones in double quotes to avoid confusion.
For instance, 6 becomes “111111”. This is simple for people who dislike binary.
Write the bandit number and all the card numbers seen, in a column, under each other.
Then perform XOR on each column of units, giving a “1” for an odd number of ones.
The unary result is then the card number to try.
There is no need for modulo. The result for n bandits is from 0 to n-1 anyway.
It does not to matter whether the numbers are aligned on the left or right,
but all bandits must do this the same way.
Does this work? Take a simple example with 4 bandits, using numbers 0 to 3,
where card numbers 2, 3, 1, 1 are used.
Bandit 0 calculates
“111”
“1”
“1”
“ “
giving result “111”, that is 3, so he fails.
Bandit 1 calculates
“11”
“1”
“1”
“1”
giving result “ 1”, that is 1, so he fails.
Bandit 2 calculates
“11”
“111”
“1”
“11”
giving result “ 11”, that is 2, so he fails.
Bandit 3 calculates
“11”
“111”
“1”
“111”
giving result “ 1”, that is 1, so he succeeds.
As intended, one bandit succeeds and 3 fail.
Somebody should check this, but I know it is right.
No binary, no modulo, no addition or subtraction, just counting and recognising odd and even.
An unbiased intelligent computer would recognise this as wonderfully simple!
But, with thousands of bandits, he would be sad about using unary.
To tidy up, here is the same case with XOR and binary, (see above).
Modulo 4 is automatic with 4 bandits, (a power of 2).
Write the bandit number and all the card numbers seen, in a column, under each other.
Then perform XOR on each column of bits, giving a “1” for an odd number of ones.
The binary result is then the card number to try.
Take the same simple example with 4 bandits, using numbers 0 to 3,
where card numbers 2, 3, 1, 1 are used.
Bandit 0 calculates
11
01
01
00
giving result 11, that is three, so he fails.
Bandit 1 calculates
10
01
01
01
giving result 11, that is three, so he succeeds.
Bandit 2 calculates
10
11
01
10
giving result 10, that is two, so he fails.
Bandit 3 calculates
10
11
01
11
giving result 11, that is three, so he fails.
As intended, one bandit succeeds and 3 fail.
No addition or subtraction, just counting and recognising odd and even.
Note that the three correct solutions may give three different successful bandits.
I return to a question I set earlier, but I generalise a bit.
If not every bandit of the 10 can try to guess his card number, what should they do?
For instance, can 9 active bandits succeed with more than 90% probability?
I assume each card number, 0 to 9, is given randomly and that the bandits know which of them will be asked.
One of the three above correct solutions should be used as a basis. It would not help, to risk having two bandits aiming for the same total of ten card numbers!
For instance, with only two “active” bandits, they can agree that one will use an even bandit number, and the other will use an odd bandit number.
With the Rothermel solution, I think a bandit should try with bandit number 5. The distribution of the sum of 10 card numbers is symmetrical with 45 in the middle. And 45 is the most likely sum. (Of course, 44 or 46 is only slightly less probable). For instance, if all ten different card numbers are used, the sum is 45.
So, if one bandit alone guesses, perhaps he can win with slightly more than 10% probability.
But there is a snag! If one follows the distribution curve, away from 45 in both directions, one comes to 40 and 50. So perhaps our lone bandit should try bandit number 0, getting both chances?
And if two bandits can try, perhaps one should try 5, and one should try 0?
I have a feeling that this “both chances” idea does not work. I must think about that.
I find this too difficult to decide. It reminds me of 1965 when I failed to calculate the geometric average of coefficients in continued fractions, (Kinchin’s constant), one of the most interesting numbers of all.
See https://en.wikipedia.org/wiki/Khinchin%27s_constant.
I shall come back to this when I have time. What do you think, Dr Rothermel?
Another idea, is to use more of what the bandit sees.
For instance, if a lot of small numbers are seen, try a small bandit number.
But I do not believe that this can help.
The binary and unary solutions with XOR change things a bit.
The successful bandit number will often be different. With unary, even left or right aligning can change it.
(With unary, if all card numbers are used, the target digit is again 5, regardless of aligning).
With unary, if card number 9 is not used, or is used twice, it cannot be the target digit.
Any card number that is used an even number of times does not affect the target digit.
So, the XOR target number “X”, (instead of the sum “s”), probably has a much less even probability distribution of 0 to 9. This then greatly improves the chances when few bandits are active.
When I have time, I shall experiment with six bandits. I have dice to generate the random card numbers.
I may even try to calculate the chances of success.
I may even prove that the binary and unary XOR solutions are correct.
Dear Roland, this problem is fascinating!
My “solutions” with XOR were also rubbish! I now realise that they are like trying random card numbers.
Guessing random card numbers has good chances of one success, (or more).
75% with two bandits, 65% with 10 bandits, 63% with 1000, etc.
I feel that there must be good solutions other than that of Dr Rothermel.
The problem has little connection with addition or subtraction.
The details of its statement kindly steered readers towards this solution.
The problem could have been stated using numbers 1 to 10, instead of 0 to 9.
It could have been written using ten letters, A to J, instead of numbers 0 to 9.
Another number of bandits would have made the solution harder to understand.
I can follow the logic of the Rothermel solution, but I need a deeper understanding,to help me find another solution.
The digit s is 5 with probability very slightly more than 10%. If another method can tilt probabilities more, that would be good where not all bandits can guess.