Manfred Börgens Mathematische Probleme # 13 |
Liste aller Probleme mit Lösungen voriges Problem nächstes Problem |
zur Leitseite |
Problem des Monats November 2001 |
English version |
Alle lügen.
Unsere Zahlen sind ein einziges Chaos.
Unsere Statistiken sind weniger zuverlässig als die Horoskope in der Boulevardpresse.
Authentisches Zitat aus dem Brief, den der Direktor der obersten italienischen Statistik-Behörde schrieb, bevor er im Amtszimmer seinem Leben ein Ende setzte.
Einen wichtigen Teil des folgenden Monatsproblems verdanke ich einer Anregung von Herrn Dipl.-Math. Georg Arends, der sein Mathematik-Studium 1988 - 1992 an der Fachhochschule Gießen-Friedberg absolviert hat.
Auch das Wahrheitsministerium des Staates Veritanien hat Schwierigkeiten mit den Untertanen. Insbesondere ein bestimmtes Wohnviertel in der Hauptstadt fällt immer wieder auf: Von hier kommen besonders viele falsche Steuererklärungen, betrügerische Versicherungsmeldungen, erlogene Angaben bei Volkszählungen usw. Der Minister will ein Exempel an den 210 Bewohnern des Viertels statuieren und weist seine Beamten an, dort N Häuser und in jedem dieser Häuser N Stockwerke auszuwählen, und aus jedem Stockwerk N Personen zum Verhör vorzuführen.
Die Festnahme findet statt, aber die Befragung lässt etwas auf sich warten. Die Häftlinge kennen sich alle gut und sprechen über das bevorstehende Verhör. Es bilden sich zwei Gruppen: Die eine Gruppe will klein beigeben und im Verhör die Wahrheit sagen, die andere Gruppe verabredet, den Beamten des Wahrheitsministeriums Widerstand zu leisten und nur falsche Angaben zu machen.
Beim Verhör wird diese Gruppenbildung von den Beamten schnell erkannt. Man beschließt, jeden einzeln zu fragen, wie viele "Widerständler" unter ihnen sind. Hier sind die ersten Antworten:
"Mindestens vier."
"Mehr als sieben."
"Nicht nur einer."
"Mindestens sechs."
"Alle."
...
...
Nach dieser Befragung stellen die Beamten entnervt fest, dass alle Aussagen verschieden waren; keine zwei unter ihnen bedeuteten dasselbe. Nach Sortierung ergibt sich, dass sie sich (salopp) in folgender Gestalt schreiben lassen ( L sei die Anzahl der Widerständler):
L ≥ 1
L ≥ 2
L ≥ 3
...
...
L = "alle"
Wieviele Personen wurden verhört? Wieviele davon haben gelogen?
Die Gruppengröße M ist eine Kubikzahl, also M = N3, aber das Problem lässt sich zunächst ganz unabhängig von dieser Anzahl behandeln.
Zu Beginn ein einfaches konkretes Beispiel: Sei M = 100. Dann gibt es 100 Aussagen:
An : "Es gibt mindestens n Lügner."
Z. B. kann dann An = A37 nicht von einem Lügner sein. Denn wäre A37 falsch, so gäbe es mindestens 64 Ehrliche, also auch mehrere Ehrliche, die (wahrheitsgemäß) Ak mit k ≥ 51 behaupten, im Widerspruch dazu, dass es höchstens 36 Lügner geben kann.
Diese Argumentation funktioniert für alle n ≤ 50.
Andererseits kann beispielsweise An = A53 nicht von einem Ehrlichen stammen. Denn wäre A53 wahr, so gäbe es mindestens drei gelogene Aussagen Ak mit k ≤ 50, was eben widerlegt wurde.
Diese Argumentation funktioniert für alle n ≥ 51.
An dieser Stelle ist Vorsicht geboten! Unser Nachweis, dass z.B. A37 nicht von einem Lügner sein kann, bedeutet nicht automatisch, dass diese Aussage von einem Ehrlichen stammt. Denn es könnte doch sein, dass auch dies auf einen logischen Widerspruch führt. In der Tat werden wir weiter unten sehen, dass in manchen Fällen unter den gegebenen Randbedingungen die Aussagen A1 bis AM logisch inkonsistent sind, also nicht alle entweder wahr oder falsch sind.
Im Beispiel mit M = 100 läuft man allerdings nicht in diese Falle: A1 bis A50 wahr und A51 bis A100 gelogen ergibt - leicht nachprüfbar - keine logischen Widersprüche, ist also eine richtige Lösung; dann muss sie nach der obigen Argumentation aber auch die einzige Lösung sein.
Dieses Beispiel lässt sich ohne Schwierigkeiten verallgemeinern auf alle geraden Gruppengrößen M :
Die Aussagen An für n ≤ M/2 werden von Ehrlichen und für n > M/2 von Lügnern geäußert, d.h. es gibt gleich viele Lügner wie Ehrliche.
Ist M ungerade, so gibt es diese gleichmäßige Teilung nicht. Es liegt also nahe, sich die "mittlere" Position n = M + 1/2 genauer anzuschauen (kann man z.B. mit M = 101, n = 51 ausprobieren). Wäre für dieses n An wahr, so wären natürlich auch für alle k < n die Aussagen Ak wahr. Somit gäbe es mindestens n Ehrliche. Wegen An wahr gäbe es aber auch mindestens n Lügner, was wegen 2n = M + 1 nicht stimmen kann. - Nehmen wir umgekehrt an, dass An gelogen ist, so muss Ak erst recht für alle k > n gelogen sein. Also gibt es mindestens n Lügner. Da An gelogen ist, gibt es aber auch mindestens n Ehrliche, was wieder wegen 2n = M + 1 auf einen Widerspruch führt.
Also kann im Monatsproblem die Gruppengröße M nicht ungerade sein.
Wegen M = N3 ≤ 210 kommen also nur M = 8 und M = 64 in Frage.
M = 8 scheidet aus, da alle Aussagen verschiedene Bedeutungen haben sollten, aber für M = 8 die Aussagen "Mehr als sieben" und "Alle" inhaltlich identisch wären.
Es wurden je 4 Stockwerke in 4 Häusern ausgewählt, aus jedem Stockwerk wurden 4 Personen verhört. Von diesen 64 Personen haben genau 32 gelogen.