"Welche Mathelehrerin kann es schaffen, dass jemand aus ihrer Klasse
sicher einen Preis gewinnt?"

kann ich aus dem Stehgreif leider nicht beantworten :-))

Interessant an der Aufgabe finde ich, dass hier zwei Bernoulli-Prozesse
quasi "verschränkt" sind.

Grüße
Brigitta

> Gruß,
> Rainer Rosenthal
> r.ros...@web.de

Rainer Rosenthal

unread,

Sep 23, 2021, 1:03:05 PM9/23/21

to

Am 23.09.2021 um 13:54 schrieb Gus Gassmann:
> On Thursday, 23 September 2021 at 05:28:03 UTC-3, Rainer Rosenthal wrote:

# Ich habe hier eine Liste mit elf Fragen, die mit ja oder nein zu
# beantworten sind, DIE ICH ABER NIEMANDEM ZEIGE. Wer wenigstens acht
# davon richtig beantwortet, bekommt einen Preis.
#
# Welche Mathelehrerin kann es schaffen, dass jemand aus ihrer Klasse
# sicher einen Preis gewinnt? Wie groß muss die Klasse mindestens sein,
# und welche Lösungsvorschläge führen zum Ziel?
#

>
> Müssen alle Lösungsvorschläge gleichzeitig abgegeben werden, oder darf die Mathelehrerin Informationen sammeln?
>

#
# Zusatzfrage:
# Ist es hilfreich, wenn die Lösungsvorschläge
# nacheinander abgegeben werden dürfen?
#

Fritz Feldhase

unread,

Sep 23, 2021, 2:06:10 PM9/23/21

to

On Thursday, September 23, 2021 at 6:32:33 PM UTC+2, Brigitta Jennen wrote:
> Rainer Rosenthal schrieb am Donnerstag, 23. September 2021 um 10:28:03 UTC+2:
>
> Deine Forderung, dass mindestens 1 Schüler den Preis "sicher gewinnen" soll,
> interpretiere ich jetzt mal so, dass die
> Wahrscheinlichkeit für "sicher" mehr als 0.999 betragen soll.

Also dafür würde ich eher die Bezeichnung "mit an Sicherheit grenzender Wahrscheinlichkeit" verwenden. :-P

Konkretes Beispiel: Wenn eine Bremse nur in 999 von 1000 Fällen (der Betätigung) funktioniert, würde ich das auch nicht als "(funktioniert) sicher" ansehen wollen. :-P

Von dem her würde ich dann doch eher einen "kombinatorischen" Ansatz bevorzugen (der -von Fällen der höheren Gewalt abgesehen- eine "absolute Sicherheit" gewährleistet).

Rainer Rosenthal

unread,

Sep 23, 2021, 2:07:34 PM9/23/21

to

Am 23.09.2021 um 18:32 schrieb Brigitta Jennen:

> Zusammen ergibt sich als kumulative Wahrscheinlichkeit bei zufälligem Raten
> höchstens drei Fragen falsch zu beantworten als Summe
> p_0123 = 0.1132812
> und damit als Gegenwahrscheinlichkeit, zufällig 8 Fragen aus 11 zufällig richtig
> zu erraten mit
> p = 1 - p_0123 = 0.8867188
>

"höchstens drei falsch" ist das selbe wie "mindestens acht richtig".

Die Gegenwahrscheinlichkeit von über 88 % gilt für das Ereignis "mehr
als drei Fragen falsch beantwortet".

Lieben Gruß,
Rainer

Martin Vaeth

unread,

Sep 23, 2021, 2:34:25 PM9/23/21

to

Rainer Rosenthal <r.ros...@web.de> schrieb:

> Ich habe hier eine Liste mit elf Fragen, die mit ja oder nein zu
> beantworten sind, DIE ICH ABER NIEMANDEM ZEIGE. Wer wenigstens acht
> davon richtig beantwortet, bekommt einen Preis.
>
> Welche Mathelehrerin kann es schaffen, dass jemand aus ihrer Klasse
> sicher einen Preis gewinnt? Wie groß muss die Klasse mindestens sein,
> und welche Lösungsvorschläge führen zum Ziel?

Ich denke Du willst eher darauf hinaus: Die Schüler dürfen sich
absprechen, und ihr Ziel ist es, dass mindestens einer den Preis
bekommt. Wie groß muss die Klasse mindestens sein, dass ihnen
das *mit Sicherheit* gelingt, und welche Antworten müssen die
Schüler dabei geben?

Rainer Rosenthal

unread,

Sep 23, 2021, 2:57:03 PM9/23/21

to

Ich will darauf hinaus, dass die Mathelehrerin ihre Schüler und
Schülerinnen dazu anregt, einen Plan zu machen.
Ich hätte also besser geschrieben:
"Wie schafft es die Mathelehrerin, dass jemand aus ihrer Klasse sicher
einen Preis gewinnt." Dabei ist "sicher" genau so zu verstehen, dass das
*mit Sicherheit* gelingt. Auch Wahrscheinlichkeits-Ansätze sind als
Diskussionsbeiträge willkommen, aber wie an anderer Stelle schon öfter
betont wurde: 0.999... < 1. Und für endlich viele 9-en stimme ich dem zu.

Ich möchte nochmal die Formalisierung zitieren:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Formalisierung:
Lösungsvorschläge sind Listen mit Einträgen 0 oder 1 (für nein/ja).

Beispiele:
A = [0,1,0,0,0,0,1,0,1,0,0]
B = [0,1,0,1,0,0,1,0,1,0,0]

Sollte meine geheime Liste die Lösung L = [1,0,1,0,0,0,1,0,1,0,0]
erfordern, dann bekäme A einen Preis, weil nur die ersten drei Fragen
falsch beantwortet sind, also immerhin acht Antworten korrekt sind.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Für eine richtige Lösung erwarte ich
1. Die Angabe einer Klassengröße K
2. K elfstellige Listen mit Einträgen 0 oder 1 (für nein/ja).

Eine Klasse mit K = 2^11 Schülern schafft es bestimmt, aber wie klein
darf K werden?

Gruß,
Rainer

Gus Gassmann

unread,

Sep 23, 2021, 3:20:02 PM9/23/21

to

Ohne Lernmöglichkeit sicher nicht allzuviel kleiner.

(spoiler)

Nur ein Listeneintrag trifft alle 11, 11 treffen zehn richtige, 55 treffen 9 und 165 treffen 8. Die übrigen 1816 treffen nie mehr als sieben richtige. Also brauchst du schon eine Aula, um die ganze Klasse von 1817 Schülern zu versammeln.

Rainer Rosenthal

unread,

Sep 23, 2021, 3:32:15 PM9/23/21

to

Am 23.09.2021 um 21:20 schrieb Gus Gassmann:
> Also brauchst du schon eine Aula, um die ganze Klasse von 1817 Schülern zu versammeln.
>

Ich notiere K = 1817 und brauche nun nur noch die 1817
Lösungsvorschläge, um sie mit meiner Geheim-Lösung zu vergleichen(*).

Ich danke für den ersten Ansatz, aber es geht mit K << 50.

Gruß,
Rainer

(*) Ich behalte mir natürlich Schummeln vor, d.h. wenn es eine
Geheim-Lösung geben könnte, die von allen 1817 Lösungsvorschlägen an
mehr als drei Stellen abweicht, dann werde ich behaupten, das sei die zu
Erratende gewesen.

Rainer Rosenthal

unread,

Sep 23, 2021, 3:33:26 PM9/23/21

to

Am 23.09.2021 um 16:51 schrieb Jens Kallup:

> Am 23.09.2021 um 10:28 schrieb Rainer Rosenthal:
>> Lösungsvorschläge sind Listen mit Einträgen 0 oder 1 (für nein/ja).
>>
>> Beispiele:
>> A = [0,1,0,0,0,0,1,0,1,0,0]
>> B = [0,1,0,1,0,0,1,0,1,0,0]>
>>

> A hat genau die gleiche Changen wie B, also:
>

Hallo Jens,

nach den "Chancen" von A oder B ist nicht gefragt.
A und B sind lediglich Beispiele für zwei Lösungsvorschläge, die
vielleicht von der Klasse mitgeteilt werden.
Dabei hat A hat 3 falsche Antworten und B hat 4 falsche Antworten, wenn
die Liste der korrekten Antworten so aussieht: [1,0,1,0,0,0,1,0,1,0,0].

Gruß,
Rainer

Brigitta Jennen

unread,

Sep 23, 2021, 3:38:07 PM9/23/21

to

Stimmt!
Deshalb neuer Ansatz, bei gleicher Binomial-Denkweise:

Den Preis gewinnt, wer 8, 9, 10 oder 11 Fragen richtig beantwortet.

Die Wahrscheinlichkeit hiefür beträgt
p = 0.1132812
[In R: sum(dbinom(8:11, 11, 1/2)) = 0.1132812]

Ein einzelner Schüler, der einfach nur rät, hat eine Erfolgswahrscheinlichkeit von
11.3%

Wenn die Klasse aus nur einem einzigen Schüler besteht, liegt die Wahrscheinlichkeit,
dass er den Preis für 8 Richtige gewinnt, also bei rund 11.3%.

Bestünde die Klasse aus zwei Schülern, würde die Wahrscheinlichkeit dafür, dass

mindestens einer den Preis gewinnt auf p = 0.2137298 ansteigen.
[In R: sum(dbinom(1:2, 2, 0.1132812))]

Die Frage, die jetzt zu beantworten ist, lautet:
Wie groß muss die Schülerzahl n sein, dass bei einer Bernoulli-Kette der Länge n
die Wahrscheinlichkeit für "mindestens 1 Schüler hat acht Richtige"
auf über 0.999 steigt?

Die Antwort ist: n = 58

Mit R:
sum(dbinom(1:58, 58, 0.1132812)) = 0.9990633

Wenn die Klasse aus 58 Schülern besteht, liegt die Wahrscheinlichkeit für das
Ereignis "mindestens einer hat 8 Richtige" bei 99.9%

>
> Lieben Gruß,
> Rainer

Martin Vaeth

unread,

Sep 23, 2021, 3:38:37 PM9/23/21

to

Gus Gassmann <horand....@gmail.com> schrieb:

> On Thursday, 23 September 2021 at 15:57:03 UTC-3, Rainer Rosenthal wrote:
>>
>> Ich möchte nochmal die Formalisierung zitieren:
>> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>> Formalisierung:
>> Lösungsvorschläge sind Listen mit Einträgen 0 oder 1 (für nein/ja).
>>
>> Beispiele:
>> A = [0,1,0,0,0,0,1,0,1,0,0]
>> B = [0,1,0,1,0,0,1,0,1,0,0]
>>
>> Sollte meine geheime Liste die Lösung L = [1,0,1,0,0,0,1,0,1,0,0]
>> erfordern, dann bekäme A einen Preis, weil nur die ersten drei Fragen
>> falsch beantwortet sind, also immerhin acht Antworten korrekt sind

>> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>
>> Für eine richtige Lösung erwarte ich
>> 1. Die Angabe einer Klassengröße K
>> 2. K elfstellige Listen mit Einträgen 0 oder 1 (für nein/ja).
>>
>> Eine Klasse mit K = 2^11 Schülern schafft es bestimmt, aber wie klein
>> darf K werden?
>
> Ohne Lernmöglichkeit sicher nicht allzuviel kleiner.
>
>
>
>
>
>
>
>
>
>
>
>
> (spoiler)
>
>
>
>
>
>
>
>
>
>
>
>

(spoiler)

Du liegst falsch.

(spoiler)

Lies Dir einmal einen anderen kürzlichen Thread von Rainer durch.

Rainer Rosenthal

unread,

unread,

Sep 23, 2021, 10:27:58 PM9/23/21

to

On Thursday, September 23, 2021 at 8:57:03 PM UTC+2, Rainer Rosenthal wrote:

> aber wie an anderer Stelle schon öfter betont wurde: 0.999... < 1.
> Und für endlich viele 9-en stimme ich dem zu.

Daher das besser so hinschreiben: 0,9...9 < 1
Denn: 0,999... = 1.

Siehe: https://de.wikipedia.org/wiki/0,999%E2%80%A6

> Eine Klasse mit K = 2^11 Schülern schafft es bestimmt, aber wie klein
> darf K werden?

K = 32 genügt jedenfalls schon.

Message has been deleted

Fritz Feldhase

unread,

Sep 24, 2021, 12:23:37 AM9/24/21

to

On Thursday, September 23, 2021 at 9:38:07 PM UTC+2, Brigitta Jennen wrote:

> Wenn die Klasse aus 58 Schülern besteht, liegt die Wahrscheinlichkeit für das
> Ereignis "mindestens einer hat 8 Richtige" bei 99.9%

Wenn die Klasse aus 32 Schülern besteht, die sich abgesprochen und auf eine gewisse Strategie geeinigt haben bzw. von der Klassenlehrerin oder dem Klassenlehrer entsprechend instruiert wurden (und die Fragen auch entsprechend der Strategie beantworten), dann liegt die Wahrscheinlichkeit für das Ereignis "mindestens einer hat 8 Fragen richtig beantwortet" (Fälle höherer Gewalt einmal außen vor gelassen) bei 100%.

Interessant würde Dein auf Wahrscheinlichkeit basierender Ansatz wohl werden/sein, wenn damit die Anzahl der Schüler, die man benötigt, um auf die 99,9% zu kommen, (deutlich) unter 32 gedrückt werden könnte.

Vgl. https://de.wikipedia.org/wiki/Quicksort

Alfred Flaßhaar

unread,

Sep 24, 2021, 3:41:19 AM9/24/21

to

Am 23.09.2021 um 20:57 schrieb Rainer Rosenthal:
> Am 23.09.2021 um 20:34 schrieb Martin Vaeth:
>> Rainer Rosenthal <r.ros...@web.de> schrieb:

(...)

>>
> Ich will darauf hinaus, dass die Mathelehrerin ihre Schüler und
> Schülerinnen dazu anregt, einen Plan zu machen.
> Ich hätte also besser geschrieben:
> "Wie schafft es die Mathelehrerin, dass jemand aus ihrer Klasse sicher
> einen Preis gewinnt." Dabei ist "sicher" genau so zu verstehen, dass das
> *mit Sicherheit* gelingt.

(...)

Spoiler

Darf der vom führenden Schülerstrategen beabsichtigte Planungserfolg
etappenweise vom Lehrer beurteilt werden? Wenn ja, dann wäre ein
Abstiegsverfahren zielführend.

Also:

Die Hälfte der Klasse tippt irgendwie auf genau acht Richtige. Wenn dann
der Lehrer sich freut, ist das Spiel zuende. Wenn kein Treffer dabei
ist, dann tippt die Hälfte der Restschüler auf genau neun Richtige usw.
Das bricht dann nach vier Schritten ab und erinnert an die
Reiskornaufgabe auf dem Schachbrett.

jvr

unread,

Sep 24, 2021, 4:29:52 AM9/24/21

to

On Thursday, September 23, 2021 at 10:28:03 AM UTC+2, Rainer Rosenthal wrote:
> Ich habe hier eine Liste mit elf Fragen, die mit ja oder nein zu
> beantworten sind, DIE ICH ABER NIEMANDEM ZEIGE. Wer wenigstens acht
> davon richtig beantwortet, bekommt einen Preis.
>

> Welche Mathelehrerin kann es schaffen, dass jemand aus ihrer Klasse
> sicher einen Preis gewinnt? Wie groß muss die Klasse mindestens sein,

> und welche Lösungsvorschläge führen zum Ziel?
>

> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Formalisierung:
> Lösungsvorschläge sind Listen mit Einträgen 0 oder 1 (für nein/ja).
>
> Beispiele:
> A = [0,1,0,0,0,0,1,0,1,0,0]
> B = [0,1,0,1,0,0,1,0,1,0,0]
>
> Sollte meine geheime Liste die Lösung L = [1,0,1,0,0,0,1,0,1,0,0]
> erfordern, dann bekäme A einen Preis, weil nur die ersten drei Fragen

> falsch beantwortet sind, also immerhin acht Antworten korrekt sind.
>
> Gruß,
> Rainer Rosenthal
> r.ros...@web.de

Hamming bound, Hamming codes, perfect codes nachlesen.
Das Thema ist nicht völlig trivial; die Raterei ziemlich sinnlos.

Rainer Rosenthal

unread,

Sep 24, 2021, 6:35:51 AM9/24/21

to

Am 24.09.2021 um 09:41 schrieb Alfred Flaßhaar:
>
> ... dann wäre ein Abstiegsverfahren zielführend.
>
> ... Wenn dann der Lehrer sich freut, ...

Der Lehrer oder die Lehrerin kennen doch meine Geheim-Lösung nicht.
Sie sollen lediglich ihren K Kindern in der Klasse helfen, einen Plan zu
schmieden, so dass die Lösungsvorschläge V_1, V_2, ..., V_K mit
Sicherheit einen Vorschlag enthalten, der mindestens 8 richtige
Antworten hat.

Ich bedanke mich für die rege Diskussionsbeteiligung, insbesondere für
die erste Einreichung (von Fritz Feldhase) zum Beweis, dass K <= 32 ist:
[0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,1,1,1,1,1,1,1],
[0,0,0,1,0,0,0,0,0,0,0],
[0,0,0,1,1,1,1,1,1,1,1],
[0,0,1,0,0,0,0,0,0,0,0],
[0,0,1,0,1,1,1,1,1,1,1],
[0,0,1,1,0,0,0,0,0,0,0],
[0,0,1,1,1,1,1,1,1,1,1],
[0,1,0,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,1,1,1,1,1],
[0,1,0,1,0,0,0,0,0,0,0],
[0,1,0,1,1,1,1,1,1,1,1],
[0,1,1,0,0,0,0,0,0,0,0],
[0,1,1,0,1,1,1,1,1,1,1],
[0,1,1,1,0,0,0,0,0,0,0],
[0,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,0,0],
[1,0,0,0,1,1,1,1,1,1,1],
[1,0,0,1,0,0,0,0,0,0,0],
[1,0,0,1,1,1,1,1,1,1,1],
[1,0,1,0,0,0,0,0,0,0,0],
[1,0,1,0,1,1,1,1,1,1,1],
[1,0,1,1,0,0,0,0,0,0,0],
[1,0,1,1,1,1,1,1,1,1,1],
[1,1,0,0,0,0,0,0,0,0,0],
[1,1,0,0,1,1,1,1,1,1,1],
[1,1,0,1,0,0,0,0,0,0,0],
[1,1,0,1,1,1,1,1,1,1,1],
[1,1,1,0,0,0,0,0,0,0,0],
[1,1,1,0,1,1,1,1,1,1,1],
[1,1,1,1,0,0,0,0,0,0,0],
[1,1,1,1,1,1,1,1,1,1,1]

Gruß,
Rainer

Rainer Rosenthal

unread,

Sep 24, 2021, 6:49:39 AM9/24/21

to

Am 24.09.2021 um 04:22 schrieb Fritz Feldhase:
> On Thursday, September 23, 2021 at 10:28:03 AM UTC+2, Rainer Rosenthal wrote:
>>
>> Ich habe hier eine Liste mit elf Fragen, die mit ja oder nein zu
>> beantworten sind, DIE ICH ABER NIEMANDEM ZEIGE. Wer wenigstens acht
>> davon richtig beantwortet, bekommt einen Preis.
>>
>> Welche Mathelehrerin kann es schaffen, dass jemand aus ihrer Klasse
>> sicher einen Preis gewinnt?
>

>

> Mein Lösung funktioniert wie folgt:
>
> Die Klasse umfasst 32 Schüler. Je zwei Schüler beantworten die ersten 4 Fragen gleich. Und zwar nach dem "binären Schema":
>
> Also:
>
> nein, nein, nein, nein
> nein, nein, nein, ja
> nein, nein, ja, nein
> nein, nein, ja, ja
> usw.
>
> Da damit alle Antwortmöglichkeiten für die ersten 4 Fragen ausgeschöpft werden, beantworten genau 2 Schüler die erste 4 Fragen korrekt. Bei den weiteren Fragen, folgen die Schüler einem simplen Schema, das -wie eine einfache Überlegung zeigt- garantiert, dass einer der beiden, die die ersten 4 Fragen gleich beantwortet haben, mindestens 4 der verbleibenden 7 Fragen korrekt beantwortet: Jeweils einer der beiden beantwortet die restlichen Fragen allesamt mit ja, und der andere mit nein.
>

Ausgeschrieben sehen die 32 Lösungsvorschläge so aus:

Das ist eine sehr schön strukturierte Einreichung, die für Klassen mit
mindestens 32 Schülern funktioniert. Die Lehrerin wird sich über den
Tipp freuen und ihren Schülern und Schülerinnen helfen, ihn vielleicht
sogar selbst zu entwickeln durch geeignete Tipps.

Ich bin sogar ein bisschen neidisch auf den klaren Ansatz. Auf meiner
Suche nach möglichst kleinen Klassen bin ich zwar erfolgreich gewesen,
aber da ich mich dem blinden Zufall überlassen habe, habe ich diesen
einfachen ersten Zugang nicht gesehen.
Ich denke, dass er geeignet ist, das Thema noch verständlicher zu
machen. Wenn es Dir egal ist, nach kleineren Klassengrößen zu forschen,
dann wirst Du sicher Deinen Grund haben. Es gibt ja noch viele wichtige
Dinge zu erledigen :-)

Gruß,
Rainer

Fritz Feldhase

unread,

Sep 24, 2021, 6:54:08 AM9/24/21

to

On Friday, September 24, 2021 at 10:29:52 AM UTC+2, jvr wrote:

> Hamming bound, Hamming codes, perfect codes nachlesen.
> Das Thema ist nicht völlig trivial; die Raterei ziemlich sinnlos.

Na dann sag doch einfach, wie klein das minimale K ist und gib eine konkrete Menge von Schüler-Lösungen V_1, V_2, ..., V_K an, die zum Ziel führen an.

Rainer Rosenthal

unread,

Sep 24, 2021, 6:59:52 AM9/24/21

to

Am 24.09.2021 um 10:29 schrieb jvr:
>
> Hamming bound, Hamming codes, perfect codes nachlesen.
> Das Thema ist nicht völlig trivial; die Raterei ziemlich sinnlos.
>

Im Chor zu singen, ist zum Beispiel auch ziemlich sinnlos.
Aber es macht Spaß.

Für die Raterei spricht auch, dass sich bei der Beschäftigung mit dem
Thema das Verständnis für dies "nicht völlig triviale" Thema bildet und
erweitert, so dass Nachlesen eine sinnvolle Option wird.

Ich fühle mich jedenfalls gerade ein wenig "im Zaubergarten der
Mathematik", weil heute Nacht bei parallelen Suchläufen zwei neue 24-er
erblüht sind. Die werde ich mir natürlich noch genauer anschauen und
analog zu http://rwro.de/Demonstrationen/Code24A_dsm.jpg analysieren.
(s. "benachbart"-Relation: eine Quasi-Äquivalenz, 18.09.2021, 23:56)

Gruß,
Rainer Rosenthal
r.ros...@web.de

Fritz Feldhase

unread,

Sep 24, 2021, 7:07:00 AM9/24/21

to

On Friday, September 24, 2021 at 12:49:39 PM UTC+2, Rainer Rosenthal wrote:
> Am 24.09.2021 um 04:22 schrieb Fritz Feldhase:
> >
> > Mein Lösung funktioniert wie folgt:
> >

> > Die Klasse umfasst 32 Schüler. [usw.]

> >
> Das ist eine sehr schön strukturierte Einreichung, die für Klassen mit
> mindestens 32 Schülern funktioniert. Die Lehrerin wird sich über den
> Tipp freuen und ihren Schülern und Schülerinnen helfen, ihn vielleicht
> sogar selbst zu entwickeln durch geeignete Tipps.
>
> Ich bin sogar ein bisschen neidisch auf den klaren Ansatz. Auf meiner
> Suche nach möglichst kleinen Klassen bin ich zwar erfolgreich gewesen,
> aber da ich mich dem blinden Zufall überlassen habe, habe ich diesen
> einfachen ersten Zugang nicht gesehen.

Naja, mein "erster Zugang" hat ja zu eine Lösung für "6 Richtige aus 11 Aufgaben" geführt. Dafür genügen 2 Schüler. :-P

Um zumindest zu einer halbwegs brauchbaren Lösung zu kommen, bin ich dann (nach etwas Überlegung) auf diese "gemischte" Strategie verfallen. Wo die ersten 4 Fragen "systematisch" "abgefrühstückt" werden und der Rest dann mit der "schlauen Strategie" angegangen wird - aber reduziert auf "4 Richtige aus 7 Aufgaben" (wofür ebenfalls 2 Schüler ausreichen).

Dass das nicht "optimal" ist, habe ich mir schon gedacht.

> Ich denke, dass er geeignet ist, das Thema noch verständlicher zu
> machen. Wenn es Dir egal ist, nach kleineren Klassengrößen zu forschen,
> dann wirst Du sicher Deinen Grund haben. Es gibt ja noch viele wichtige
> Dinge zu erledigen :-)

Ja, besonders um 4 Uhr morgens. :-)

Rainer Rosenthal

unread,

Sep 24, 2021, 3:14:50 PM9/24/21

to

Am 24.09.2021 um 12:59 schrieb Rainer Rosenthal:
>
> Ich fühle mich jedenfalls gerade ein wenig "im Zaubergarten der
> Mathematik", weil heute Nacht bei parallelen Suchläufen zwei neue 24-er
> erblüht sind.
>

Jetzt habe ich weiter gegärtnert und züchte aus den ziemlich vielen
inzwischen gefundenen Paketen mit 25 Lösungsvorschlägen neue 24-er!

Der Trick lautet: zwei zurück, eins vor.
Das bedeutet, ich nehme aus einem Paket mit 25 Lösungsvorschlägen zwei
weg und schaue dann, ob ein weiterer Lösungsvorschlag das aus nunmehr 24
0-1-Folgen bestehende Paket vollständig macht.

Und wenn ich dann genügend 24 beisammen habe, will ich schauen, ob der
Trick vielleicht sogar ein 23-er-Paket liefert. Denn die Minimalgröße K
muss keineswegs 24 sein. Durch dummes Suchen habe ich halt nur noch
nichts Besseres finden können. (Direkte dumme Suche hat mir in den
letzten drei Tagen gerade mal 3 Pakete mit K = 24 beschert.)

Aber soeben habe ich bereits aus dem ersten 25-er-Paket neun(!) neue
24-er gezüchtet!

Das könnte einen ergiebigen Nachtlauf geben, denn ich habe elf
25-er-Pakete, d.h. noch 10 weitere, um sie aufzuhübschen.

Gruß,
RR

P.S. Formeln werden gerne entgegengenommen, für Pakete mit K < 24
gibt es noch immer das bereits versprochene Bier, siehe
"benachbart"-Relation: eine Quasi-Äquivalenz, 16.09.2021, 17:11.
Zitat:
(*) Ich spendiere ein Bier für ein Repräsentantensystem mit *weniger*
als 24 Elementen. Und ich spende Beifall für jedes System mit 24
Elementen. Für 26 Elemente gibt es ein anerkennendes Kopfnicken.

Für 32 Elemente gab es Sonderapplaus wegen der schönen Systematik.

Fritz Feldhase

unread,

Sep 24, 2021, 4:28:54 PM9/24/21

to

On Friday, September 24, 2021 at 9:14:50 PM UTC+2, Rainer Rosenthal wrote:

> Für 32 Elemente gab es Sonderapplaus wegen der schönen Systematik.

Naja, schön vielleicht, aber nicht gut genug. :-P

Jens Kallup

unread,

Sep 24, 2021, 6:33:05 PM9/24/21

to

Hallo,

Versuch durch Irrtum?
hehe.

Probiere doch mal Pumation:

(n) n!
( ) = -------------
(k) k! (n - k)!

Also 11 aus 4:

(11) 11!
( ) = --------------
( 4) 4! (11 - 4)!

Voila:

n = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11
= 39.916.800

k = 1 * 2 * 3 * 4 * (1 * 2 * 3 * 4 * 6 * 7)
= 24

(11) 39.916.800
( ) = ------------ = 24 <--- Ergebnis
( 4) 120.960

Gruß, Jens

Jens Kallup

unread,

Sep 24, 2021, 6:35:42 PM9/24/21

to

Am 25.09.2021 um 00:33 schrieb Jens Kallup:
> k = 1 * 2 * 3 * 4 * (1 * 2 * 3 * 4 * 6 * 7)
> = 24
>

das natürlich Quatsch.
richtigerweise:

k = 1 * 2 * 3 * 4 * (1 * 2 * 3 * 4 * 6 * 7)

= 120.960

Jens

Rainer Rosenthal

unread,

Sep 25, 2021, 7:17:35 AM9/25/21

to

Was hat das mit dem Thema "Elf unbekannte Aufgaben" zu tun?

Gruß,
RR

Fritz Feldhase

unread,

Sep 25, 2021, 7:32:59 PM9/25/21

to

On Saturday, September 25, 2021 at 12:33:05 AM UTC+2, kallu...@web.de wrote:

> k = 1 * 2 * 3 * 4 * (1 * 2 * 3 * 4 * 6 * 7)

... * 4 * 6 * ... --- fehlt da nicht was?

Jens Kallup

unread,

Sep 25, 2021, 11:01:44 PM9/25/21

to

Am 26.09.2021 um 01:32 schrieb Fritz Feldhase:
>> k = 1 * 2 * 3 * 4 * (1 * 2 * 3 * 4 * 6 * 7)
> ... * 4 * 6 * ... --- fehlt da nicht was?

was sollte da fehlen?
die Formula ist:

(n) n!

= -------------
(k) k! (n - k)!

das ist Faktorisierung - also dieses n! und k!

n := 11 mögliche ja
k := x richtige ja's

wenn x := 8 ist, also 8 Fragen = ja, dann:

n := 11!
n := 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11
n := 39.916.800

k := 8!
k := 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8
k := 40.320

(n - k)! := n! - k!
:= 39.916.800 - 40.320
:= 39.876.480

k! * (n - k)! := 40.320 * 39.876.480
:= 1.607.819.673.600

39.916.800 / 1.607.819.673.600 := 0,24826 (8 richtige)

tabelarisch:
Aufgaben dividiert durch Schüler mit resultierende Wahrsch-
einlichkeit:

(bei einer Aufgabe und einen Schüler, besteht eine
50 zu 50 (1:2) also fifty fifty Wahrscheinlichkeit,
bedingt durch die -1 (da -1 bei den gestellten Bediningen
(also 0 - nein, 1 - ja) ein Unterlauf ergibt, resultiert
hier die 2).

1 / 2 := 0,5000000000000000000000000
2 / 79.833.596 := 0,0000000250521096406580507
3 / 239.500.764 := 0,0000000125260560755455460
4 / 958.002.624 := 0,0000000041753539080076674
5 / 4.790.001.600 := 0,0000000010438409874435115
6 / 28.739.577.600 := 0,0000000002087713355954125
7 / 201.155.270.400 := 0,0000000000347989887914962
8 / 1.607.819.673.600 := 0,0000000000049756823674682
9 / 14.354.052.249.600 := 0,0000000000006270006436858
10 / 131.681.894.400.000 := 0,0000000000000759405842812
11 / 1.593.350.922.240.000 := 0,0000000000000069036894801

Fazit:
Je größer die Aufgaben werden, desto größer muss die Klassen-
stärke werden, wobei der Erfolg (also *eine* richtige Aufgabe
zu erfüllen, die Warscheinlichkeit unter Null (0) sinkt).
Das heißt: je mehr Aufgaben, und je mehr Schüler, desto geringer
wird die Warscheinlichkeit *ALLE* Aufgaben zu lösen.

in Prozent gerechnet:

11 := 1.593.350.922.240.000 := 100,000 %
10 := 131.681.894.400.000 := 8,264 %
9 := 14.354.052.249.600 := 0,901 %
8 := 1.607.819.673.600 := 0,101 %
7 := 201.155.270.400 := 0,013 %
6 := 28.739.577.600 := ...

Fazit:
wie oben schon beschrieben;
je weniger Aufgaben, desto weniger wird die Wahrscheinlichkeit
bzw. die Preis-Ausschüttung.

Hoffe gedient zu Haben
Euer Schreiberling, Jens

Rainer Rosenthal

unread,

Sep 26, 2021, 2:19:08 AM9/26/21

to

Die sinnlose Raterei zusammen mit dem sinnvollen Turbo "2 rück, 1 vor"
ergibt K <= 23. Ich kann dazu momentan 58 Lösungen bieten, und die Zahl
kann in den nächsten Stunden noch anwachsen. Dass bei den 58 Lösungen
viele isomorphe sind, ist sehr wahrscheinlich.

Der "Turbo" hat aus elf Rohlingen mit K = 25 zweiunddreißig mit K = 24
gemacht, und die letzten sieben davon werden noch ein Weilchen
bearbeitet, um noch mehr mit K = 23 zu finden.

Natürlich kann mich danach nur ein plötzlicher Stromausfall oder
Herzinfarkt stoppen, auch auf Suche nach K = 22 zu gehen :-)

Schönen Sonntag,
Gruß,
RR

Dieter Heidorn

unread,

Sep 26, 2021, 7:36:45 AM9/26/21

to

Jens Kallup schrieb:

> Am 26.09.2021 um 01:32 schrieb Fritz Feldhase:
>>> k = 1 * 2 * 3 * 4 * (1 * 2 * 3 * 4 * 6 * 7)
>> ... * 4 * 6 * ... --- fehlt da nicht was?
>

> die Formula ist:
>
> (n) n!

> ( ) = -------------

> (k) k! (n - k)!
>
> das ist Faktorisierung - also dieses n! und k!
>

Das "n!" bzw. "k!" nennt sich "Fakultät":

n! = 1*2*3*...*n

k! = 1*2*3*...*k

Der Term

(n) n!
( ) = -----------

(k) k! (n - k)!

heißt "Binomialkoeffizient".

> n := 11 mögliche ja
> k := x richtige ja's
>
> wenn x := 8 ist, also 8 Fragen = ja, dann:
>
> n := 11!

Nein, sondern

n! = 11!

> n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11
-
(mit "=" statt ":=" - das bedeutet etwas anderes)

> n! := 39.916.800
-
>
> k := 8!

Nein, sondern

k! = 8!

> k! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8
> k! = 40.320

>
> (n - k)! := n! - k!

Unsinn.

(n - k)! = 1*2*3*...*(n-k)

Hier:

(n-k)! = (11 - 8)!

= 3!

= 6

Also:

(11) 11!
( ) = -------------- = 165
(8 ) 8! * (11 - 8)!

> Hoffe gedient zu Haben

Wobei?

Dieter Heidorn

Rainer Rosenthal

unread,

Sep 26, 2021, 11:06:32 AM9/26/21

to

Am 26.09.2021 um 08:19 schrieb Rainer Rosenthal:
>
> Der "Turbo" hat aus elf Rohlingen mit K = 25 zweiunddreißig mit K = 24
> gemacht, und die letzten sieben davon werden noch ein Weilchen
> bearbeitet, um noch mehr mit K = 23 zu finden.
>
> Natürlich kann mich danach nur ein plötzlicher Stromausfall oder
> Herzinfarkt stoppen, auch auf Suche nach K = 22 zu gehen :-)
>
> Schönen Sonntag,

Und was für ein schöner Sonntag! Kein Stromausfall, kein Herzinfarkt,
aber ...

Eine Klasse mit K = 22 Schülern bekommt sicher einen Preis, wenn sie das
hier einreicht:

Schüler 1: [0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0]
Schüler 2: [0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1]
Schüler 3: [0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1]
Schüler 4: [0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1]
Schüler 5: [0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0]
Schüler 6: [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1]
Schüler 7: [0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0]
Schüler 8: [0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1]
Schüler 9: [0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0]
Schüler 10: [0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0]
Schüler 11: [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
Schüler 12: [1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]
Schüler 13: [1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0]
Schüler 14: [1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0]
Schüler 15: [1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1]
Schüler 16: [1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1]
Schüler 17: [1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0]
Schüler 18: [1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1]
Schüler 19: [1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1]
Schüler 20: [1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0]
Schüler 21: [1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1]
Schüler 22: [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0]

Fragt mich nicht, warum, aber es ist einfach so, dass jede 0-1-Folge der
Länge 11 an mindestens 8 Positionen mit einer der obigen Schüler-Folgen
übereinstimmt. Wer's nicht glaubt, zahlt 'nen (Rosen-)Taler.
Somit kann meine "geheime Liste" aussehen, wie sie will: einer kriegt
den Preis.

Als Beispiel nehme ich die "geheime Liste" aus meinem ersten Posting:

"Sollte meine geheime Liste die Lösung L = [1,0,1,0,0,0,1,0,1,0,0]

erfordern, ..."
In dem Fall würde Schüler 3 einen Preis bekommen (und nur er):

[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0] // geheime Lösung
[0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1] // Schüler 3
----------------------------------------------------
= = = = = = = = // 8 Übereinstimmungen

Gruß,
Rainer Rosenthal
r.ros...@web.de

Nachtrag:

Ich habe bereits 4 weitere Lösungspakete für K = 22, und dabei habe ich
erst die ersten 11 der 62 heute gefundenen 23-er destilliert.

Da kommt vielleicht noch einiges Schöne zutage. An K = 21 kann ich nicht
mehr so recht glauben, aber wer weiß ...

Martin Vaeth

unread,

Sep 26, 2021, 12:58:59 PM9/26/21

to

^ ^

Die markierten Spalten fallen mir auf: Während alle anderen Spalten 10 oder 11
Nullen haben (falls ich mich nicht verzählt habe), haben diese Spalten 12 bzw.
9 Nullen was deutlich von der Hälfte von 22 abweicht. Intuitiv hätte ich
erwartet, dass in einer "optimalen" Lösung alle Spalten 11 Nullen haben.
Diese aufsummierte Asymmetrie scheint mir deshalb Potential für Verbesserungen
zu bieten.
Ob das natürlich ausreicht, einen ganzen weiteren Eintrag einzusparen, ist
schwer abzuschätzen: Schließlich hat das Problem von vornherein eine gewisse
Asymmetrie, denn 3 ist kein Teiler von 11.
Trotzdem würde ich bei einer systematischen Suche (mit Deiner 2-Zurück-1-vor
Taktik), zuerst mal versuchen, die Lösung zu "optimieren", indem ich schauen
würde, ob man das nicht symmetrischer hinbekommt.

Rainer Rosenthal

unread,

Sep 26, 2021, 1:40:58 PM9/26/21

to

Am 26.09.2021 um 18:58 schrieb Martin Vaeth:
>
> Die markierten Spalten fallen mir auf: Während alle anderen Spalten 10 oder 11
> Nullen haben (falls ich mich nicht verzählt habe), haben diese Spalten 12 bzw.
> 9 Nullen was deutlich von der Hälfte von 22 abweicht. Intuitiv hätte ich
> erwartet, dass in einer "optimalen" Lösung alle Spalten 11 Nullen haben.
> Diese aufsummierte Asymmetrie scheint mir deshalb Potential für Verbesserungen
> zu bieten.
> Ob das natürlich ausreicht, einen ganzen weiteren Eintrag einzusparen, ist
> schwer abzuschätzen: Schließlich hat das Problem von vornherein eine gewisse
> Asymmetrie, denn 3 ist kein Teiler von 11.
> Trotzdem würde ich bei einer systematischen Suche (mit Deiner 2-Zurück-1-vor
> Taktik), zuerst mal versuchen, die Lösung zu "optimieren", indem ich schauen
> würde, ob man das nicht symmetrischer hinbekommt.
>

Hallo Martin,

es freut mich natürlich sehr, wenn meine Ergebnisse auch von anderen
angeschaut und analysiert werden, danke!

Ich habe im Moment bereits neun(!) 22-er-Lösungen und dabei wurde erst
ein Drittel der zweiundsechzig 23-er-Lösungen systematisch abgeklopft
mit der 2z1v-Methode.

Noch setze ich auf die brutalo-blöd-Suche, weil sie einen Reichtum an
Mustern produziert. Sobald der Ergebnis-Strom versiegt, muss ich mir
natürlich was Schlaueres einfallen lassen. Dafür sind solche Hinweise
zur Symmetrie sicher hilfreich (inklusive der Vorbehalte, dass 3 kein
Teiler von 11 ist, d.h. Asymmetrie vorprogrammiert ist.)

Ich weiß es zu schätzen, dass Du neulich (*) schriebst:
"Ich wundere mich schon, wie Du überhaupt eine so kleine Zahl gefunden
hast." Das ist jetzt eine Woche her, und es macht immer noch viel Spaß.

Gruß,
Rainer

(*)
Thema / "benachbart"-Relation: eine Quasi-Äquivalenz
Datum / 19.09.2021, 08:36

unread,

Sep 26, 2021, 4:20:53 PM9/26/21

to

Rainer Rosenthal schrieb am 23.09.21 um 10:28:

> Ich habe hier eine Liste mit elf Fragen, die mit ja oder nein zu
> beantworten sind, DIE ICH ABER NIEMANDEM ZEIGE. Wer wenigstens acht
> davon richtig beantwortet, bekommt einen Preis.
>
> Welche Mathelehrerin kann es schaffen, dass jemand aus ihrer Klasse

> sicher einen Preis gewinnt? Wie groß muss die Klasse mindestens sein,
> und welche Lösungsvorschläge führen zum Ziel?

Zur Klassen-Mindestgröße: M=\ceil{(2^L)/(\binom{L}{d})}
dürfte eine untere Schranke sein, wobei L die Länge
der Wörter (hier L=11) und d der Hamming-Abstand
(hier d=3) sind. Hier wäre M=13; bei weniger als
M bleiben immer mögliche Klausurergebnisse übrig,
die niemand mit 8 Richtigen beantwortet.

Die Frage ist natürlich, ob M ausreicht; das ist eher
unwahrscheinlich, gegeben die Differenz zwischen 13
und deinem bisherigen Minimum 22 im Beispiel. Ein
schrittweises Verfahren bietet sich naiv an:

Im 1. Schritt starte mit einem Wort v_1 in {0,1}^L
und nenne dies Schüler 1. Der deckt schon mal sich
selbst und alle Wörter ab, die Hamming-Abstand <=d
zu ihm haben. (Das sind genau \binom{L}{d}-1 viele.)

In Schritt i>=2 wählt man "geschickt" ein Wort v_i,
das bisher noch nicht abgedeckt ist, das wäre dann
Schüler i. Der deckt alle Wörter ab, die <=d von
ihm entfernt sind. Irgendwann bricht das Verfahren
ab, und wir haben die Klasse beieinander. Fragt
sich nur, was "geschickt" heißt. In erster Näherung
sollte der Hamming-Abstand zwischen v_i und allen
bislang schon abgedeckten Wörtern maximal sein. Es
ist mir jedoch nicht gelungen, daraus eine obere
Schranke abzuleiten, und um das Verfahren bei L=11
und d=3 anzuwenden, würde ich programmieren wollen.

Carlo XYZ

unread,

Sep 26, 2021, 4:55:31 PM9/26/21

to

Carlo XYZ schrieb am 26.09.21 um 22:20:

unread,

Sep 27, 2021, 5:39:19 PM9/27/21

to

Rainer Rosenthal <r.ros...@web.de> schrieb:

>
> Im verwandten Thread //"benachbart"-Relation: eine Quasi-Äquivalenz//
> steht: "Ausblick: ich steuere auf Folgen mit L = unendlich hin".
> Das entspricht dann der genannten Aufgaben-Variante
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Aufgaben 1,2,..., Kinder 1,2,..., Fehlertoleranz < oo
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Und die ist mittels Auswahlaxion lösbar.

Nein, ist sie nicht: Die Vorgabe hat die Mächtigkeit des Kontinuums,
aber nur abzählbar viele Aufgaben dürfen abgegeben werden.
Beachte: Die Variante mit den abzählbar vielen Hüten, auf die Du Dich
beziehst, geht anders: Da *sehen* irgendwann fast alle Kandidaten fast
alle Lösungen, was natürlich viel "leichter" ist.

Rainer Rosenthal

unread,

Sep 27, 2021, 6:04:12 PM9/27/21

to

Oh, danke, da habe ich bös was durcheinander gebracht.

Mal schauen, wo ich da falsch abgebogen war.

Gruß,
Rainer

Ulrich Diez

unread,

Sep 28, 2021, 5:23:20 PM9/28/21

to

Es sind ja 2^11 = 2048 verschiedene Antwort-Listen möglich.

Bevor ich mich verkopfe, eine Verständnisfrage:

Ist die Aufgabe so zu verstehen? :

Von denjenigen Teilmengen der Menge an möglichen Antwort-Listen,
bei denen 100%-ig sicher ist, dass sie für jedes Element der Menge an
möglichen Antwort-Listen mindestens ein Element enthalten, welches
sich in maximal drei Stellen von diesem Element der Menge an
möglichen Antwort-Listen unterscheidet, sind diejenigen mit der
kleinsten Anzahl an Elementen gesucht.

Mit freundlichem Gruß

Ulrich (, der die Aufgabe eben erst gelesen hat und noch dabei ist,
sie überhaupt zu verstehen, und, sofern er sie richtig verstanden
hat, wahrscheinlich kapitulieren wird)

Andreas Leitgeb

unread,

Sep 28, 2021, 7:12:07 PM9/28/21

to

Ulrich Diez <ud.usenetco...@web.de> wrote:
> Es sind ja 2^11 = 2048 verschiedene Antwort-Listen möglich.
> Bevor ich mich verkopfe, eine Verständnisfrage:
> Ist die Aufgabe so zu verstehen? :
>
> Von denjenigen Teilmengen der Menge an möglichen Antwort-Listen,
> bei denen 100%-ig sicher ist, dass sie für jedes Element der Menge an
> möglichen Antwort-Listen mindestens ein Element enthalten, welches
> sich in maximal drei Stellen von diesem Element der Menge an
> möglichen Antwort-Listen unterscheidet, sind diejenigen mit der
> kleinsten Anzahl an Elementen gesucht.

Richtig.

Ich hätte lediglich an zwei Stellen statt "Element der Menge an möglichen
Antwort-Listen" einfach "mögliche Antwortliste" geschrieben.

Rainer Rosenthal

unread,

Sep 28, 2021, 7:22:54 PM9/28/21

to

Am 28.09.2021 um 23:23 schrieb Ulrich Diez:
> Es sind ja 2^11 = 2048 verschiedene Antwort-Listen möglich.
>
> Bevor ich mich verkopfe, eine Verständnisfrage:
>
> Ist die Aufgabe so zu verstehen? :
>
> Von denjenigen Teilmengen der Menge an möglichen Antwort-Listen,
> bei denen 100%-ig sicher ist, dass sie für jedes Element der Menge an
> möglichen Antwort-Listen mindestens ein Element enthalten, welches
> sich in maximal drei Stellen von diesem Element der Menge an
> möglichen Antwort-Listen unterscheidet, sind diejenigen mit der
> kleinsten Anzahl an Elementen gesucht.
>

Willkommen im Club.
Stimmt: eine Klasse bekommt den Preis, wenn wenigstens ein Schüler
ausreichend genau geantwortet hat. Um 100%-ig sicher den Preis zu
bekommen, muss sie (wenn sie nicht gerade 2048 Schüler hat) sich etwas
Cleveres einfallen lassen.
Wie klein kann eine Klasse sein, die einen cleveren Plan aufstellen kann?

Schau Dir dazu bitte meine Tapete von 27.09.2021, 09:30 an.
Da hat eine Klasse mit 21 Schülern so clever geantwortet, dass jede der
2048 möglichen 0-1-Listen an höchsten 3 Stellen Unterschiede aufweist.

Ich setze sie der Einfachheit halber nochmal hierher:

Schüler 1: [0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0]
Schüler 2: [0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1]
Schüler 3: [0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1]
Schüler 4: [0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1]
Schüler 5: [0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1]
Schüler 6: [0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0]
Schüler 7: [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1]
Schüler 8: [0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0]
Schüler 9: [0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1]
Schüler 10: [0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]
Schüler 11: [0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1]
Schüler 12: [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
Schüler 13: [1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0]
Schüler 14: [1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0]
Schüler 15: [1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1]
Schüler 16: [1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1]
Schüler 17: [1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1]
Schüler 18: [1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1]
Schüler 19: [1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0]
Schüler 20: [1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1]
Schüler 21: [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0]

> Mit freundlichem Gruß
>
> Ulrich (, der die Aufgabe eben erst gelesen hat und noch dabei ist,
> sie überhaupt zu verstehen, und, sofern er sie richtig verstanden
> hat, wahrscheinlich kapitulieren wird)
>

Bevor Du Dich schaudernd abwendest, kannst Du ja mal schauen, ob ich was
übersehen habe (oder in meinem Rechner ein Bit gekippt ist).
Such doch mal den oder die Schüler, die bei dem Muster
[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
sagen können: "hab ich!".

Gruß,
Rainer

Rainer Rosenthal

unread,

Sep 29, 2021, 6:09:59 AM9/29/21

to

Am 29.09.2021 um 01:22 schrieb Rainer Rosenthal:
> Am 28.09.2021 um 23:23 schrieb Ulrich Diez:
>>
>> Ist die Aufgabe so zu verstehen? :

>> [... richtige Interpretation ...]

>>
>
> Schau Dir dazu bitte meine Tapete von 27.09.2021, 09:30 an.
> Da hat eine Klasse mit 21 Schülern so clever geantwortet, dass jede der
> 2048 möglichen 0-1-Listen an höchsten 3 Stellen Unterschiede aufweist.
>
> Ich setze sie der Einfachheit halber nochmal hierher:
>
> Schüler 1: [0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0]
> Schüler 2: [0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1]

> usw. bis

> Schüler 21: [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0]
>

> Such doch mal den oder die Schüler, die bei dem Muster
> [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
> sagen können: "hab ich!".
>

Das neuronale Netz wird gar nicht schlecht für das Thema trainiert, wenn
es solche konkreten Aufgaben vorgesetzt bekommt. Ich habe nun endlich
auch gedanklich Fortschritte machen können, indem ich mich mit den 330
Positions-Quadrupeln befasst habe, die es bei 11 Positionen gibt:
binomial(11,4) = 330.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Wer einen Preis gewinnen will, muss unbedingt vermeiden, auf irgendeinem
Positions-Quadrupel alles zu vermasseln. Denn dann hat er 4 falsche
Antworten gegeben und ist raus.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Ich glaube, mit diesem Gedanken wirklich weiter zu kommen, um die
minimale Klassengröße K theoretisch herleiten zu können. Schließlich ist
330 schon um Einiges kleiner als 2^11 = 2048. Noch wichtiger aber ist
die neue Perspektive und Begriffsbildung.

Das sind zarte theoretische Pflänzchen.
Die praktische Rumfummelei erzeugt inzwischen Daten-Urwälder.
Die Verarbeitung der 276 gestern berechneten 24-er Lösungspakete
schreitet langsam voran, aber bereits nach der Bearbeitung des 32-ten
Pakets habe ich jede Menge 23-er-Pakete gefunden, genauer: 273.
Mit geduldigem Abwarten werde ich demnächst stolzer Besitzer von über
1000 Lösungspaketen zu K = 23 sein. Nichts spricht dagegen, die bereits
gefundenen 23-er mit der gleichen 2z1v-Methode in 22-er zu wandeln.
Immer getreu dem Motto "Sinnlos - aber nicht trivial!"

Inzwischen werde ich das theoretische Pflänzchen weiter gut versorgen.

Gruß,
RR

jvr

unread,

Sep 29, 2021, 8:28:29 AM9/29/21

to

Vor 52 Jahren hat man von der Mariner-Sonde Bilder kodiert gesendet, und zwar
als 32-bit Worte, derart dass immer 7 Fehler korrigierbar waren. Würde dein Programm
den optimalen Code hierfür in weniger als 50 Jahren bestimmen können?

Nebenbei: Ich glaube, die statistische Methode ist im Prinzip recht gut
anwendbar für diese Art Poblem, wenn man nicht unbedingt das Optimum
braucht, sonder mit einer sehr guten Näherung zufrieden ist. Gefühlsmäßig
würde ich schätzen, dass dein Programm bedeutend schneller zum Ziel käme,
wenn du mehr als 2 Schritte zurückgehen würdest. Probier mal die 3 oder 4
am wenigsten effizienten zu ersetzen, nicht nur 2. (Ich habe nicht alles gelesen,
also ist der Vorschlag vielleicht überholt.)

Rainer Rosenthal

unread,

Sep 29, 2021, 9:37:17 AM9/29/21

to

Am 29.09.2021 um 14:28 schrieb jvr:
> Probier mal die 3 oder 4
> am wenigsten effizienten zu ersetzen, nicht nur 2. (Ich habe nicht alles gelesen,
> also ist der Vorschlag vielleicht überholt.)
>

Allein das Messen der 'Effizienz' dürfte ein großer Aufwand sein.
Um 3 Schritte zurück zu gehen, habe ich begonnen, aber so wie ich das
anpacke, versacke ich in der kombinatorischen Explosion.

Ich habe aber deutliche Beschleunigung für "2 Schritte zurück, 1 vor",
also die Methode 2z1v, und die Verbesserungen kann ich vielleicht für
einen neuen Versuch nutzen, um 3z2v zu realisieren.

Und mit der Betrachtung der Positions-Quadrupel kommt auch Bewegung in
die theoretische Betrachtung. Die anfallenden Datenmassen sollen mich ja
nicht nur zu K = 20 katapultieren (ich habe bereits 5-mal K = 21),
sondern sie sollen auch zeigen, ob es vielleicht gar nicht erreichbar ist.

Die Verteilung der Anzahl von Nullen und Einsen ist übrigens auch sehr
interessant und kann beim Durchblick helfen. Je kleiner die
Klassengrößen K werden, desto deutlicher wird sich - so hoffe ich -
herausstellen, was wichtig ist. Wobei "wichtig" gerne relativ gesehen
werden darf. "Sinnlos - aber nicht trivial!" trifft es ja auch recht gut.

Gruß,
RR

jvr

unread,

Sep 29, 2021, 11:05:22 AM9/29/21

to

Ich weiß nicht, was du da für ein Programm hast - kann mir nicht vorstellen,
dass das mehr als wenige Sekunden Laufzeit braucht. Ich probiere das mal.
Sind doch moderne Zeiten, die wir da haben.

jvr

unread,

Sep 29, 2021, 11:18:15 AM9/29/21

to

Damit ich das nicht nochmal lesen muss: Du suchst also eine minimale Untermenge M von N,
wo N alle 11-stelligen Binärcodes enthält, derart dass jedes n in N Hamming-Abstand <= 3 von einem m in M hat?
Dass also 'Kugeln' mit 'Radius' 3 und Mittelpunkt in M die Menge N überdecken?

Rainer Rosenthal

unread,

Sep 29, 2021, 1:47:29 PM9/29/21

to

Exakt!
Bin gespannt, was Du da erreichen kannst. Insbesonderee im
Sekunden-Bereich. Ich programmiere in Maple und mach's halt so, dass ich
meinen Code noch nach drei Tagen verstehen kann. Effizienz lasse ich
außen vor.
Ich möchte von dem Datenmaterial beim Denken unterstützt werden, und
solange es mit dem Denken hapert, sammle ich.

Gruß,
RR

Ulrich Diez

unread,

Sep 29, 2021, 2:09:35 PM9/29/21

to

Rainer Rosenthal schrieb:

> Bevor Du Dich schaudernd abwendest, kannst Du ja mal schauen, ob ich was
> übersehen habe (oder in meinem Rechner ein Bit gekippt ist).
> Such doch mal den oder die Schüler, die bei dem Muster
> [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
> sagen können: "hab ich!".

unread,

Sep 30, 2021, 11:11:04 AM9/30/21

to

Am 30.09.2021 um 11:10 schrieb Rainer Rosenthal:
> Das erlaubt Analogien zur Anregung des Denkens.
> Nimm ein 11 x 11 Quadrat und als "Kugeln mit Radius 3" verwende 5 x 5
> Quadrate. Das sind in der Manhattan-Metrik die Kugeln mit Radius 3.
> Wieviele Kugeln werden nun gebraucht für die vollständige Überdeckung?
>
> Gibt es beim Original-Problem evtl. auch "systematische Stapelungen",
> wie sie sich hier in der Analogie anbieten? Da legt man die 5 x 5
> Quadrate nebeneinander und merkt, dass 4 noch zu wenig sind. Wenn ich es
> richtig sehe, ist es so ungünstig, dass insgesamt 9 "Kugeln" gebraucht
> werden. Aber das Resultat ist unwichtig. Wichtig ist: gibt es eine
> Stapel-Methode für die Hamming-Kugeln?

also, wenn der Radius "einer" Kugel 3 beträgt, dann ist der Durchmesser
der Kugel d = r * 2 oder d = r^2.
Das heißt: 3 * 2 = 6.
Somit ist der Durchmesser 6 Einheiten (ich lasse mal die Eingliederung
bzw. die Benennung der Einheit(en) weg).

5 x 5 Quadrate: ich gehe mal davon aus, das die 5 eine Skalierung ist.
Weil, "ein" Quadrat von 5x5 = 25 ergibt, also die Länge und die Breite
ungefähr 2,236 Einheiten beträgt.

Also "ein" Quader der "5" ungefähr 2,236 in der Breite und ungefähr
2,236 in der Länge Einheiten hat.

Das macht dann zwar 4,999 also rund 5 Einheiten für einen Quader.
Ich nehme weiter an, das diese 4,999 Einheiten erstmal egal sind, und
ein ganzzahliger Wert verwendet werden soll.

Nun passt aber "eine" Kugel nicht in "einen" Quader, da der d = 6 ist,
und der Quader in der Dimension mit Einheit 5 begrenzt ist.

Ich nehme weiter an, das die Kugel nicht unter 6 Einheiten einen Cut
erleben soll.
Gleiches für die 5 Quader.

+--+--+--+ Das ist ein Rechteck, aber ein Quader kann ja auch ein
| | | | Rechteck sein; Okay. Mann kann aber dieses Rechteck für die
+--+--+--+ weiteren Schritte nicht verwenden, da sonst das Ergebnis
| | | | verwurschtelt wird. Also überlegen wir uns, wie man aus dem
+--+--+--+ 3 * 2 := 6 => 5 machen können.

Denken wir uns nun dieses obige Rechteck als Karte oder, ich sag mal
naiv: Fehrnrohr - Warum?
Nun, "eine" Kugel würde nicht in "einen" Quader passen - zu groß.
wir überlegen:
- 5 * 5 = 25 Einheiten Fläche der Quader verfügbar
- 3 * 6 = 18 Einheiten Fläche der Kugeln verfügbar

Man kann hier schon leicht erkennen, das die 3 Kugeln 7 Einheiten an
Fläche zur Verfügung haben, in denen sie sich nicht bewegen können.
Das heißt, die 3 Kugeln haben ungefähr 2,646 Längen-
und Breiteneinheiten über.

Ich denke mal man hat hier eine Integralgleichung vorliegen, die
als untere Grenze 4,999, und als obere Grenze 4,999 + 2,646 := 7,645
Einheiten hat.
Zur Einfachheit runde ich auf, auf: 5 und 3 := 8.

Wir Überlegen weiter:
25 QuaderEinheiten (max) * 3 Kugeln (max) := 75 QuaderEinheiten

75 QuaderEinheiten
+ 8 QuaderEinheiten
---------------------
= 83 QuaderEinheiten | 100 - 83 = 17

Wir brauchen also 17 Kugeln, um das 5 x 5 Quadrat zu Überdecken.

Ich sag jetzt einfach mal, das diese 17 Kugeln das Minimum sind,
was da so an Preisen ausgelost werden können.

Mal davon abgesehen, bräuchte man einen Würfel als Behälter, weil
so einfach Kugeln stapeln - ehm, das wird irgendwie nix :-)

Alles ohne Gewähr
Jens

Dieter Heidorn

unread,

Sep 30, 2021, 1:41:53 PM9/30/21

to

Jens Kallup schrieb:

> Am 30.09.2021 um 11:10 schrieb Rainer Rosenthal:
>> Das erlaubt Analogien zur Anregung des Denkens.
>> Nimm ein 11 x 11 Quadrat und als "Kugeln mit Radius 3" verwende 5 x 5
>> Quadrate. Das sind in der Manhattan-Metrik die Kugeln mit Radius 3.
>> Wieviele Kugeln werden nun gebraucht für die vollständige Überdeckung?
>>
>> Gibt es beim Original-Problem evtl. auch "systematische Stapelungen",
>> wie sie sich hier in der Analogie anbieten? Da legt man die 5 x 5
>> Quadrate nebeneinander und merkt, dass 4 noch zu wenig sind. Wenn ich
>> es richtig sehe, ist es so ungünstig, dass insgesamt 9 "Kugeln"
>> gebraucht werden. Aber das Resultat ist unwichtig. Wichtig ist: gibt
>> es eine Stapel-Methode für die Hamming-Kugeln?
>
> also, wenn der Radius "einer" Kugel 3 beträgt, dann ist der
> Durchmesser der Kugel d = r * 2 oder d = r^2.

Du hast übersehen, dass Rainer die Manhattan-Metrik verwendet:

"Nimm ein 11 x 11 Quadrat und als 'Kugeln mit Radius 3' verwende

5 x 5 Quadrate. Das sind in der *Manhattan-Metrik* die Kugeln mit
Radius 3."

Du verwendest dagegen die euklidische Metrik in der Ebene, was nichts
mit Rainers Überlegungen zu tun hat.

Dieter Heidorn

Uwe Weiss

unread,

Sep 30, 2021, 3:28:43 PM9/30/21

to

Am 29.09.2021 um 19:47 schrieb Rainer Rosenthal:

> Bin gespannt, was Du da erreichen kannst. Insbesonderee im
> Sekunden-Bereich. Ich programmiere in Maple und mach's halt so, dass ich
> meinen Code noch nach drei Tagen verstehen kann. Effizienz lasse ich
> außen vor.
> Ich möchte von dem Datenmaterial beim Denken unterstützt werden, und
> solange es mit dem Denken hapert, sammle ich.
>

Hi Rainer,

ich bin mir nicht sicher, ob ich die Aufgabe richtig verstanden habe.
Ich bin kein Mathematiker, sondern Informatiker. Deshalb habe ich auf
das Problem mal ein Java-Programm losgelassen, das einen ganz naiven
Ansatz verfolgt: wähle Schritt für Schritt immer den/einen 11-stelligen
Code, der aus der Rest-Suchmenge maximal viele Einträge rauskegelt.

Damit komme ich auf folgende Lösung - die vermutlich nicht optimal ist:

00000000000
00001111111
00110011001
00111100110
01010101010
01011010101
01100110011
01101001100
10010110100
10011001011
10100101101
10101010010
11000011110
11001100001
11110000111
11111111000

Ok. Da ich den Holzhammer bemüht habe, ist der Gewinn an mathematischen
Erkenntnissen natürlich dürftig.

Gruß

-Uwe-

P.S.: Laufzeit des Programms: ca. 100 msec. Die Programm-Erstellung hat
aber länger gedauert ;)

Carlo XYZ

unread,

Sep 30, 2021, 4:29:06 PM9/30/21

to

Uwe Weiss schrieb am 30.09.21 um 21:28:

> Ansatz verfolgt: wähle Schritt für Schritt immer den/einen 11-stelligen
> Code, der aus der Rest-Suchmenge maximal viele Einträge rauskegelt.

Nicht unähnlich der Heuristik, die ich anderswo vorschlug.

> Damit komme ich auf folgende Lösung - die vermutlich nicht optimal ist:
>
> 00000000000
> 00001111111
> 00110011001
> 00111100110
> 01010101010
> 01011010101
> 01100110011
> 01101001100
> 10010110100
> 10011001011
> 10100101101
> 10101010010
> 11000011110
> 11001100001
> 11110000111
> 11111111000

16. Das theoretische Minimum ist 13. :-)

Martin Vaeth

unread,

Sep 30, 2021, 5:25:56 PM9/30/21

to

>
> Du vergisst: Rainer hat nur eine Frage aufgestellt, "ob ese eine
> Stapelmethode für 'Hamming'-Kugeln'" gibt.

Ich glaube nicht, dass Dieter Heidorn das vergessen hat, aber er weiß,
was ich mit Hamming-Kugeln gemeint habe. Die Hamming-Kugel um einen
Punkt P mit Radius r besteht aus allen Punkten mit Hamming-Distanz <= r.

Ich glaube Dir gerne, dass Du meinen Gedankensprüngen nicht folgen
konntest, weil ich nämlich von den 11-stelligen Vektoren mit Koordinaten
0 und 1 in einen anderen Raum gesprungen bin.
(Ich sagte ja, dass Analogien das Denken anregen.)

In dem anderen Raum sind die Vektoren zweistellig und es gibt die 11
Koordinatenwerte 0 bis 10. Das kann man sich gut vorstellen als die
Gitter-Punkte eines Quadrats in der Ebene: (0,0), (0,1) usw.
Als Abstand nehme ich aber nicht die euklidische Metrik, sondern die
oben beschriebene Manhattan-Metrik.

Leider habe ich bei der Rechnung allerlei durcheinander gebracht, denn
meine Pflasterung von 11 x 11 durch 5 x 5 Quadrate war eine nette Idee,
aber mit "Manhattan-Metrik" hat das nichts zu tun.

> Und davon abgesehen, sind meine Werte gerundet, und können andere
> Resultate bringen als erwartet.

Deine Werte basieren auf falschen Grundlagen, genau wie meine.
Die genaue Ausführung erfordert Sorgfalt, aber das Denken wurde
hoffentlich angeregt: Die lustigerweise "eckigen" Kugeln der
Manhattan-Metrik (die Hamming-Kugeln) sollte man besser wie
Pflastersteine einen an den anderen legen. Eine Straße oder Terrasse
oder Garageneinfahrt pflastert man ja gewöhnlich auch nicht so, dass man
die Pflastersteine vom Laster runterkippt und mit einer Dampfwalze
plattdrückt.

>
> Aber die Lösung scheint schon festzustehen: 16.
>

Nein, wie kommst Du darauf?
Das steht nirgends, und deer Entdecker der 16-er-Lösung hat selbst ganz
bescheiden davon gesprochen, das könnte evtl. zu verbessern sein. Und
wenn er das schreibt, dann hat das Gewicht, weil er weiß, wie die 16
zustande gekommen sind. Und er sieht Potential für Verbesserung.

Außerdem wurde lediglich ausgeschlossen, dass Lösungen mit weniger als 9
Punkten existieren.

Gruß,
Rainer

Jens Kallup

unread,

Oct 1, 2021, 7:49:33 AM10/1/21

to

Am 01.10.2021 um 10:04 schrieb Rainer Rosenthal:
> Wenn Du nicht weißt, was die Manhattan-Metrik ist, dann solltest Du
> fragen und nicht einfach weiterlesen und auf irgendwas antworten, was
> danach kommt.
> Denn das Weitere hat üblicherweise mit dem zu tun, was vorher
> geschrieben wurde.
>
> Zur Erklärung (dabei verwende ich 3-stellige Folgen statt 11-stelliger):
> Ich betrachte solche 0-1-Folgen wie 101 oder 000 oder 110 als "Punkte"
> in einem Fantasie-"Raum". Dieser Raum hat natürlich nur 8 Punkte.
> Mit der Manhattan-Metrik haben die Punkte A = 101 und B = 110 den
> "Abstand" 2, weil die Abstände an den Positionen 1, 2 und 3
> zusammengezählt werden:
> Position 1: A hat 1, B hat 1, Abstand an Position 1 ist |1-1| = 0.
> Position 2: A hat 0, B hat 1, Abstand an Position 2 ist |0-1| = 1.
> Position 3: A hat 1, B hat 0, Abstand an Position 3 ist |1-0| = 1.
> Zusammengezählt also 0 + 1 + 1 = 2.

Hallo Rainer,

gibts es da keine 4. Position?
Also, wenn A und B die gleiche Position haben wie bei

A=1, B=1, als 1. Position, und
A=0, B=0, als 4. Position

Wird lezters nicht mehr betrachtet, weil |0-0| = 0. ?

Würde da der Abstand nicht wie folgt sein:

9 Möglichkeiten:

000 - 000 <-- doublete
000 - 111
001 - 100
010 - 010 <-- doublete
011 - 011
100 - 001
101 - 101 <-- doublete
110 - 111
111 - 111 <-- doublete

Wenn man nun das durch einen Sieb/Filter gibt, dann
bleiben ja nur 5 übrig.
Sind vielleicht diese 5 Deine 5 LHS x 5 RHS Fläche ?

LHS RHS
---------
000 - 111
001 - 100
011 - 011
100 - 001
110 - 111

Gruß, Jens

Rainer Rosenthal

unread,

Oct 1, 2021, 8:12:53 AM10/1/21

to

Am 01.10.2021 um 13:49 schrieb Jens Kallup:
> Am 01.10.2021 um 10:04 schrieb Rainer Rosenthal:
>>
>> Zur Erklärung (dabei verwende ich 3-stellige Folgen statt 11-stelliger):

>> ...

>
> gibts es da keine 4. Position?
>

Nein, bei 3-stelligen Folgen gibt es keine 4. Position.

>
> Würde da der Abstand nicht wie folgt sein:
>
> 9 Möglichkeiten:
>
> 000 - 000 <-- doublete

> ...

Interessante Frage, aber was soll ich prüfen? Du hast doch gar keinen
Abstand genannt.

Gruß,
Rainer

Jens Kallup

Oct 1, 2021, 1:13:51 PM10/1/21

to

So, ich nochmal:
habe das Ganze ein wenig gepimpt:

https://www.kallup.net/pub/tmp/news/permu.zip

im Archiv, die Quellcode-Datei sowie die mit
dem MinGW übersetzt.
Falls bei dem Einen oder Anderen Zweifel im
Bezug auf die Binärdatei sind (ich habe nicht
vor irgendwem zu Schaden mit irgendwelchen
Viren oder so), daher die C Quelldatei hier im
Posting.
Kann dann jeder selbst für sich kopieren und
dann mit dem C Compiler der Eigenen Wahl übersetzt
werden.

Euer Schreiberling
Jens

---%<--- schnippp -----

/*
** Datei: permutation.c
** Autor: Jens Kallup <kallu...@web.de>
** Lic : non-profit
** (c) 2021 kallup.net - non-profit
** Nur für Schulungszwecke !
*/

# include <stdio.h>
# include <string.h>

# include <stdint.h> /* für uintN_t */
# include <sys/time.h>

/* Windows 64-Bit Compiler (MinGW64) */
#ifdef __MINGW64__
# undef gettimeofday
# define gettimeofday mingw_gettimeofday
# define timersub(a, b, result) \
do { \
(result)->tv_sec = (a)->tv_sec - (b)->tv_sec; \
(result)->tv_usec = (a)->tv_usec - (b)->tv_usec; \
if ((result)->tv_usec < 0) { \
--(result)->tv_sec; \
(result)->tv_usec += 1000000; \
} \
} while (0)
#endif

#ifndef SUCCESS
# define SUCCESS 0
# define FAILURE 1
#endif

/* globale Variablen, die w#hrend der Laufzeit geänder werden */
uint64_t pos = 0; /* checker */
struct timeval time_elapsed; /* verstrichene Zeit */

struct timeval time_before; /* Timer start */
struct timeval time_after ; /* Timer ende */
struct timeval time_result; /* Timer Ergebnis */

/*
** Funktion zum Pointer-Tausch:
*/
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}

/*
** Funktion zum Ausgeben der Zeichketten-Permutation:
** Parameter 1: Zeichenkette
** Parameter 2: Start - Index
** Parameter 3: Ende - Index
*/

void permute(char *a, uint64_t l, uint64_t r)
{
uint64_t i;
if (l == r) {
gettimeofday(&time_elapsed, NULL);
timersub (&time_elapsed, &time_before, &time_result);
printf("poshex: 0x%016x , posdec: %-16d, str: %s, Zeit:
%ld.%06ld\n",
pos, pos, a,
(uint64_t) time_result.tv_sec,
(uint64_t) time_result.tv_usec);
pos += 1;

}
else
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
permute(a, l+1, r);
swap((a+l), (a+i));
}
}

/*

** Zeichenkette lateinischer Buchstaben
** anstelle von 0 und 1 ...
*/
int main()
{

/* start */
gettimeofday(&time_before, NULL);

char str[] = "ABCDEFGHIJK";
uint8_t n = strlen(str);
permute(str, 0, n-1);

/* ende */
gettimeofday(&time_after, NULL);

timersub(&time_after, &time_before, &time_result);
printf("Durchlauf dauerte: %ld.%06ld\n",
(uint64_t) time_result.tv_sec,
(uint64_t) time_result.tv_usec);

return SUCCESS;
}

-->%---- schnapp -----

Das Ganze schaut im Schnippsel dann ungefähr so aus:

poshex: 0x00000000000016c8 , posdec: 5832, str: ABCEFDJHIGK, Zeit:
29.941792
poshex: 0x00000000000016c9 , posdec: 5833, str: ABCEFDJHIKG, Zeit:
29.957417

irgendwie bekomme ich mit meinen E-Mail Client - Thunderbird
immer einen Wortumbruch an Stelle 80.
Das hab ich noch nicht heraus gefunden, wie man das ändern kann,
weil das ziemlich doof sein kann - manchmal :-)

Jens

Jens Kallup

unread,

Oct 1, 2021, 3:42:50 PM10/1/21

to

so, hab das jetzt erstmal gestoppt, den Durchgang,
ging schon fast 2 Stunden:

/*
** Randbemerkungen:
** poshex: 0x0000000000100d0b , posdec: 1051915, str: ADKBICFGEHJ,
Zeit: 5823.543970
** poshex: 0x0000000000100d0c , posdec: 1051916, str: ADKBICFGJEH,
Zeit: 5823.559595
**
** hier, bei 1.051.916 Möglichleiten habe ich abgebrochen, da das sonst
Stunden
** gedauert hätte.
** Auf den Testrechner, der über 10 Jahre Alt ist, habe ich bis hier
rund 5824 Sekunden
** benötigt. Dies macht dann: 5824 * 60 = 97 Minuten = 1.6 Stunden = 1
Stunde und 43 Minuten.
**
** Ich glaube, wenn ich das anders programmiert hätte, so auf mehrere
Threads oder Computer,
** wäre es schlauer gewesen. Nun gut, was nicht ist, das kann ja noch
werden; to be continued..
*/

Rainer Rosenthal

unread,

Oct 1, 2021, 5:16:26 PM10/1/21

to

Am 30.09.2021 um 11:10 schrieb Rainer Rosenthal:

> Zum Beispiel hat "jvr" es so auf den Punkt gebracht (29.09.2021, 17:18):
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Du suchst also eine minimale Untermenge M von N, wo N alle 11-stelligen
> Binärcodes enthält, derart dass jedes n in N Hamming-Abstand <= 3 von
> einem m in M hat? Dass also 'Kugeln' mit 'Radius' 3 und Mittelpunkt in M
> die Menge N überdecken?
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> Das erlaubt Analogien zur Anregung des Denkens.
> Nimm ein 11 x 11 Quadrat und als "Kugeln mit Radius 3" verwende 5 x 5
> Quadrate. Das sind in der Manhattan-Metrik die Kugeln mit Radius 3.
> Wieviele Kugeln werden nun gebraucht für die vollständige Überdeckung?
>

O je, hier hatte ich gemurkst und an die Maximum-Metrik gedacht. Bei der
sind allerdings die "Kugeln mit Radius 3" achsenparallele 6 x 6
Quadrate. Vier davon bedecken trivialerweise das 11 x 11 Quadrat.

Die Scharte wollte ich auswetzen und habe festgestellt:
Für das 11 x 11 Quadrat werden mindestens 8 Manhattan-Kugeln mit Radius
3 benötigt.

Zur Erinnerung: der Manhattan-Abstand ist die Summe der Absolutwerte der
Koordinaten-Differenzen. In 2 Dimensionen also der Abstand
zwischen [x1,y1] und [x2,y2] gleich |x1-x2| + |y1-y2|.

Es mag bei dem Originalproblem einfacher abzuschätzen sein, wie viele
Hamming-Kugeln mit Radius 3 zur Überdeckung der 2048 0-1-Folgen benötigt
werden, aber zumindest bei diesem kleinen Problem mit 121 Punkten ist
die grobe Abschätzung
"Gesamtzahl der Gitterpunkte geteilt durch Anzahl der Gitterpunkte in
einer Kugel mit Radius 3"
viel zu grob. Denn die Manhattan-Kugel in der Ebene mit Radius 3 hat 25
Gitterpunkte, wenn das Zentrum ein Gitterpunkt ist.
121 / 25 = 4 Rest 21, d.h. es werden mindestens 5 Kugeln benötigt. Aber
5 ist keine gute Abschätzung für die tatsächlich benötigten 8.

Jetzt habe ich viel Zeit vertrödelt auf diesem "Nebenkriegsschauplatz".
Es geht mir doch jetzt darum, Uwes 16 auf Minimalität zu überprüfen.

Gruß,
RR

Rainer Rosenthal

unread,

Oct 2, 2021, 6:15:03 PM10/2/21

to

Am 01.10.2021 um 23:16 schrieb Rainer Rosenthal:
>
> Die Scharte wollte ich auswetzen und habe festgestellt:
> Für das 11 x 11 Quadrat werden mindestens 8 Manhattan-Kugeln mit Radius
> 3 benötigt.
>
> Zur Erinnerung: der Manhattan-Abstand ist die Summe der Absolutwerte der
> Koordinaten-Differenzen. In 2 Dimensionen also der Abstand
> zwischen [x1,y1] und [x2,y2] gleich |x1-x2| + |y1-y2|.
>

> ... Denn die Manhattan-Kugel in der Ebene mit Radius 3 hat 25

> Gitterpunkte, wenn das Zentrum ein Gitterpunkt ist.

Die "Manhattan-Kugeln mit Radius 3" um einen Gitterpunkt sind um 45 Grad
gedrehte Quadrate mit Diagonalenlänge 6.
Ich habe mir das aufgemalt und fand das Bild so hübsch, dass ich es als
Blickfang zum Kapitel "Mathematisches" auf meiner Homepage(*) gesetzt habe.

Mir fielen dann aber ein paar "Einkerbungen" am Rand auf, und schon war
die Idee zu einem neuen Thread geboren:
"Elf mal elf Gitterpunkte überdecken"

Gruß,
RR

(*) http://www.rwro.de

Rainer Rosenthal

unread,

Oct 3, 2021, 8:23:26 AM10/3/21

to

Am 01.10.2021 um 01:21 schrieb Rainer Rosenthal:

> Lösung von Uwe Weiss, 30.09.2021 um 21:28 Uhr:

>
> Schüler 1: [0,0,0,0,0,0,0,0,0,0,0]
> Schüler 2: [0,0,0,0,1,1,1,1,1,1,1]
> Schüler 3: [0,0,1,1,0,0,1,1,0,0,1]
> Schüler 4: [0,0,1,1,1,1,0,0,1,1,0]
> Schüler 5: [0,1,0,1,0,1,0,1,0,1,0]
> Schüler 6: [0,1,0,1,1,0,1,0,1,0,1]
> Schüler 7: [0,1,1,0,0,1,1,0,0,1,1]
> Schüler 8: [0,1,1,0,1,0,0,1,1,0,0]
> Schüler 9: [1,0,0,1,0,1,1,0,1,0,0]
> Schüler 10: [1,0,0,1,1,0,0,1,0,1,1]
> Schüler 11: [1,0,1,0,0,1,0,1,1,0,1]
> Schüler 12: [1,0,1,0,1,0,1,0,0,1,0]
> Schüler 13: [1,1,0,0,0,0,1,1,1,1,0]
> Schüler 14: [1,1,0,0,1,1,0,0,0,0,1]
> Schüler 15: [1,1,1,1,0,0,0,0,1,1,1]
> Schüler 16: [1,1,1,1,1,1,1,1,0,0,0]
>
> Niemand hat bisher eine Lösung für eine kleinere Klasse bieten können.
>

Es gibt jetzt aber eine neue von Martin Vaeth:

Schüler 1: [0,0,0,0,0,0,0,0,0,0,0]
Schüler 2: [0,0,0,0,1,1,1,1,1,1,1]
Schüler 3: [0,0,1,1,0,0,1,1,0,0,1]
Schüler 4: [0,0,1,1,1,1,0,0,1,1,0]
Schüler 5: [0,1,0,1,0,1,0,1,0,1,0]
Schüler 6: [0,1,0,1,1,0,1,0,1,0,1]
Schüler 7: [0,1,1,0,0,1,1,0,0,1,1]
Schüler 8: [0,1,1,0,1,0,0,1,1,0,0]
Schüler 9: [1,0,0,1,0,1,1,0,1,0,0]
Schüler 10: [1,0,0,1,1,0,0,1,0,1,1]
Schüler 11: [1,0,1,0,0,1,0,1,1,0,1]
Schüler 12: [1,0,1,0,1,0,1,0,0,1,0]
Schüler 13: [1,1,0,0,0,0,1,1,1,1,0]
Schüler 14: [1,1,0,0,1,1,0,0,0,0,1]
Schüler 15: [1,1,1,1,0,0,0,0,1,1,1]
Schüler 16: [1,1,1,1,1,1,1,1,0,0,0]

Sie stammt aus dem Thread "Elf mal elf Gitterpunkte überdecken", den ich
angelegt habe, um Gedanken zum Thema Kugel-Überdeckung zu sammeln.
Martin hat mit Posting vom 03.10.2021, 12:13 Uhr, gleich dort
beschrieben, welche Gedanken er verwendet hat. Die obige Lösung ist nur
eine von 2145 Lösungen! Weitere Lösungen hat er nicht mehr abgewartet.

Jetzt gibt es also bereits zwei Experten, deren Meinung mich sehr
interessiert, ob Potential für 15-er Löungen da ist. Uwe hat das nicht
ausgeschlossen.

Gruß,
Rainer

Rainer Rosenthal

unread,

Oct 4, 2021, 5:36:08 AM10/4/21

Rainer Rosenthal

unread,

Oct 6, 2021, 7:17:56 AM10/6/21

to

Am 06.10.2021 um 07:38 schrieb Martin Vaeth:
> Martin Vaeth <mar...@mvath.de> schrieb:
> ...

> Damit andere auch sehen, auf welche Zahlen ich mich hier berufe:

> ...

> Bzgl. des Fortschritts des Algorithmus sind die folgenden Ausgaben
> relevant:
>
> Level 1: 1|330
> Level 2: 1|70
> Level 3: 1|1
> Level 4: 1|216
> Level 5: 1|34
> Level 6: 1|18 [...] 15|18
>
> Dies bedeuetet: Alle 16er Lösungen, die ich bislang gefunden habe,
> fangen mit den selben 6 Listen an (bis Level 5; die erste Liste ist
> per Definition immer 00000000000).

> ...

> Übrigens hatte ich bislang *immer*
>
> Level 7: 1|1
> Level 8: ...|{32,64}
> Level 9: ...|{1,2}
> Level 10-15: ...|{meist deutlich kleiner als 10, oft nur 1 oder 2}
>

Sorry, bin etwas langsam im Kapieren:
Was genau bedeutet 1|330?

Ist die 330 die Zahl, die das erste Binärmuster (Liste von 0-en und
1-en) ergibt?
Wohl eher nicht, denn sonst ist 1|18 ... 15|18 nicht sinnvoll.

Erläuterst Du das bitte ein wenig mehr?

Gruß,
Rainer

Rainer Rosenthal

unread,

Oct 6, 2021, 7:30:33 AM10/6/21

to

Am 04.10.2021 um 22:10 schrieb Martin Vaeth:

> (Falls Du es nicht schaffst, schreib mir per PM und ich sende Dir die
> Datei).

Ich hatte eine PM geschrieben (04.10.2021, 23:50), aber die scheint
verloren gegangen zu sein:
"danke für das Angebot.
alles zwischen 3 und 17000 Lösungen nehme ich dankend entgegen."

Gruß,
Rainer

Rainer Rosenthal

unread,

Oct 6, 2021, 7:50:28 AM10/6/21

to

Ups, sorry, habe gerade Deine Antwort gesehen. Danke!