Elf unbekannte Aufgaben

272 views
Skip to first unread message

Rainer Rosenthal

unread,
Sep 23, 2021, 4:28:03 AMSep 23
to
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

Gus Gassmann

unread,
Sep 23, 2021, 7:54:31 AMSep 23
to
Müssen alle Lösungsvorschläge gleichzeitig abgegeben werden, oder darf die Mathelehrerin Informationen sammeln?

Fritz Feldhase

unread,
Sep 23, 2021, 9:33:37 AMSep 23
to
On Thursday, September 23, 2021 at 10:28:03 AM UTC+2, Rainer Rosenthal wrote:

> Welche Mathelehrerin kann es schaffen, <usw.>

Ein Mathelehrer kann es nicht schaffen?

Jens Kallup

unread,
Sep 23, 2021, 10:51:04 AMSep 23
to
A hat genau die gleiche Changen wie B, also:

Die 2 ergibt sich aus der Tatsache, das nur 0 - falsch und
1 - richtig, also 2 Möglichkeiten entstehen können.
Da Deine Liste, oder die Anzahl der Fragen 11 beträgt, so
ergibt sich für:

A = B:
A = 2 hoch 11, und
B = 2 hoch 11

A > B ->
A = 2 hoch 11
B = 2 hoch 11 minus 1

B > A ->
A = 2 hoch 11 minus 1
B = 2 hoch 11

beide gleich stark:
A = 2 hoch 11 = 2048 Möglichkeiten
B = 2 hich 11 = 2048 Möglichkeiten

A schwächer als B:
A = 2 hoch 11 minus 1 = 2047

B schwächer als A:
B = 2 hoch 11 minus 1 = 2047

Jens

Brigitta Jennen

unread,
Sep 23, 2021, 12:32:33 PMSep 23
to
Hallo,
die Schüler raten bei jeder Frage zufällig, welches die richtige
Lösung ist.
Die Einzelwahrscheinlichkeit p, die richtige Antwort bei einer der
11 Fragen zufällig richtig zu erraten beträgt p = 0.5
Damit liegt ein Bernoulli-Prozess der Länge n = 11 mit p = 0.5 vor.

Gefordert ist, dass mindestens 8 Fragen richtig beantwortet werden.
Dies ist gleichbedeutend mit dem Gegenereignis, nicht mehr als drei
Fragen falsch zu beantworten.

Berechnung der Einzelwahrscheinlichkeiten mittels Binomialverteilung
B(n;p;k):

p_0 (keine Frage falsch beantwortet) = 0.5^11 = 0.000488
p_1 (eine Frage falsch beantwortet) = 0.5^11*11 = 0.005371
p_2 (zwei Fragen falsch beantwortet) = 0.5^11 * 55 = 0.026855
p_3 (drei Fragen falsch beantwortet) = 0.5^11 * 165 = 0.080566

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

Dies sind die Chancen für einen einzelnen Schüler.

Wenn die Klasse nur aus einem einzigen Schüler besteht, liegt die Wahrscheinlichkeit,
dass er den Preis für 8 Richtige gewinnt, also bei rund 88%.
Bestünde die Klasse aus zwei Schülern, würde die Wahrscheinlichkeit dafür, dass
mindestens einer den Preis gewinnt auf p = 0.9871674 ansteigen.

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.

Hierfür sind 4 Schüler erforderlich.
Wenn die Klasse aus mindestens vier Schülern besteht steigt die Wahrscheinlichkeit,
dass mindestens einer acht Richtige rät auf über 99.9 % an.

Deine Frage:
"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 PMSep 23
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 PMSep 23
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 PMSep 23
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 PMSep 23
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 PMSep 23
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 PMSep 23
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 PMSep 23
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 PMSep 23
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 PMSep 23
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 PMSep 23
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,
Sep 23, 2021, 3:46:20 PMSep 23
to
Am 23.09.2021 um 21:38 schrieb Brigitta Jennen:
>
> Die Antwort ist: n = 58
>
> Wenn die Klasse aus 58 Schülern besteht, liegt die Wahrscheinlichkeit für das
> Ereignis "mindestens einer hat 8 Richtige" bei 99.9%
>

K = 58 ist schon deutlich kleiner als diee vorgeschlagenen 1817, leider
aber ist der 'Sicherheits'-Aspekt vernachlässigt(*).

Es gibt eine Lösung mit K deutlich unter 50 und garantiertem Erfolg.

Gruß,
Rainer

(*) ... schaffen, dass jemand aus ihrer Klasse *sicher* einen Preis gewinnt?

Jens Kallup

unread,
Sep 23, 2021, 4:38:41 PMSep 23
to
mich würde mal interessieren, wie und womit man diesen
Kooifizienten berechnet bekommt.

Jens

Rainer Rosenthal

unread,
Sep 23, 2021, 4:48:57 PMSep 23
to
Am 23.09.2021 um 22:38 schrieb Jens Kallup:
> mich würde mal interessieren, wie und womit man diesen
> Kooifizienten berechnet bekommt.
>

Hallo Jens, jetzt sei doch mal so gut, das zu zitieren, wonach Du
fragst. Woher soll ich wissen, was Du meinst?

Von welchem Koeffizienten sprichst Du?

Gruß,
Rainer


Jens Kallup

unread,
Sep 23, 2021, 4:53:02 PMSep 23
to
also ich denke mal, das dies mit Modulus
3 = 1, und
4 = 2

rückwärts berechnet werden könnte.
wobei dann
mod 3 = 1 <--- diese 1, und
mod 4 = 2 <--- diese 2

die möglichen 3 Varianten sein dürften.

wobei sich das ja eigentlich wiederholen
sollte und eine Liste wie:

11 = 3 für den stärksten, und der Rest
10 = 2

ergeben sollte.
In der Bandbreite von 11 Aufgaben:
00000000011 für 3, und
00000000010 für 2

man könnte natürlich die 3 als dritten,
und die 2 als zweiten Platz betrachten.

Aber fairerweise, damit kein Schüler aussen
vorn gehalten wird, und somit alle ein gutes
Ergebnis erhalten, könnte man die beiden
Gruppen 3 und 2 zusammen würfeln und man
erhält dadurch einen Overflow, aber mit
positiver Wirkung.

Also so:

00000000011 3
und 00000000010 2
----------------
= 00000000100 4

man kann am Ergebnis oben eine kleine Anglizmen
erkennen - die führenden Nullen braucht man ja
nicht, übrig bleibt 100 - in Prozent gesehen,
also 100 % - Alle bestanden :-)

Jens

Jens Kallup

unread,
Sep 23, 2021, 4:55:49 PMSep 23
to
    00000000011   3
und 00000000010   2
----------------
=    00000000100   4

natürlich ergibt 3+2 = 5.
Aber die Lehrerinn ist ja auch noch im Spiel.
Die darf ja eigentlich nicht mitberechnet werden.

Somit ergibt sich 3+2 = 5 - eine Lehrerinn = 4

Jens

Jens Kallup

unread,
Sep 23, 2021, 4:58:25 PMSep 23
to
naja, wie ich das so gesehen habe, in Brigittas Post,
wurden 0 Komma Zahl Objekte verwendet.
Und es kam die Frage nach binominalkoofizienten auf.
Daher meine Frage:
inwiefern haben solche Koofizienten eine Rolle, und
wie berechnet man diese.

Jens

Fritz Feldhase

unread,
Sep 23, 2021, 10:22:33 PMSep 23
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?

Keine Ahnung. Leider kenne ich nicht genügend Mathelehrerinnen, um diese Frage zu beantworten.

Daher mache ich mal mit den folgenden Fragen weiter:

> Wie groß muss die Klasse mindestens sein,

Achselzuck, 32 Schüler genügen jedenfalls, um sicher zu stellen, dass jemand aus der Menge dieser Schüler den Preis gewinnt.

Ich gehe nicht davon aus, dass dies die "optimale" Lösung ist, aber immerhin habe ich damit eine obere Grenze für die Anzahl der benötigten Schüler angegeben.

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

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.

Fritz Feldhase

unread,
Sep 23, 2021, 10:27:58 PMSep 23
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 AMSep 24
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 AMSep 24
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 AMSep 24
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 AMSep 24
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 AMSep 24
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 AMSep 24
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 AMSep 24
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 AMSep 24
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 PMSep 24
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 PMSep 24
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 PMSep 24
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 PMSep 24
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 AMSep 25
to
Was hat das mit dem Thema "Elf unbekannte Aufgaben" zu tun?

Gruß,
RR

Fritz Feldhase

unread,
Sep 25, 2021, 7:32:59 PMSep 25
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 PMSep 25
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 AMSep 26
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 AMSep 26
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 AMSep 26
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 PMSep 26
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 PMSep 26
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

Fritz Feldhase

unread,
Sep 26, 2021, 3:46:00 PMSep 26
to
On Sunday, September 26, 2021 at 7:40:58 PM UTC+2, Rainer Rosenthal wrote:

Hallo Rainer,

wenn Du so weiter machst, setz' ich mich auch noch mal hin und schreibe einen Python-Code für die Suche nach solchen Lösungen. :-P

Feldhase

Rainer Rosenthal

unread,
Sep 26, 2021, 3:52:55 PMSep 26
to
Am 26.09.2021 um 21:45 schrieb Fritz Feldhase:
> On Sunday, September 26, 2021 at 7:40:58 PM UTC+2, Rainer Rosenthal wrote:
>
> Hallo Rainer,
>
> wenn Du so weiter machst, setz' ich mich auch noch mal hin und schreibe einen Python-Code für die Suche nach solchen Lösungen. :-P
>
Eigentlich wollte ich ja gerade aufhören, aber wenn Du sowas sagst ...
mach ich halt in Gottes Namen weiter :-)

Es wird natürlich zäh und zäher: aber die elfte Lösung zu K = 22 hat
sich gerade blicken lassen, und es ist erst die Hälfte der
zweiundsechzig 23-er abgeklopft worden.

Frech wie ich bin, warte ich geduldig ab, bis das 22-er-Geschwader
komplett ist. Ich rechne damit, dass ich dann morgen Mittag etwa 20
solche Dinger zur Verfügung habe, um damit das Abenteuer "K = 21" zu
starten.

(Mit dem Schlachtruf "Sinnlos, aber nicht ganz trivial!")

Gruß,
Rainer

Fritz Feldhase

unread,
Sep 26, 2021, 4:16:52 PMSep 26
to
On Sunday, September 26, 2021 at 9:52:55 PM UTC+2, Rainer Rosenthal wrote:

> (Mit dem Schlachtruf "Sinnlos, aber nicht ganz trivial!")

Ganz im Sinne von Loriot: "Ein Leben ohne Mops ist möglich, aber sinnlos." - oder so. :-P

Carlo XYZ

unread,
Sep 26, 2021, 4:20:53 PMSep 26
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 PMSep 26
to
Carlo XYZ schrieb am 26.09.21 um 22:20:

> (Das sind genau \binom{L}{d}-1 viele.)

Bitte streichen.
Der Satz stammt aus einer früheren Version des Postings.

Rainer Rosenthal

unread,
Sep 26, 2021, 5:02:01 PMSep 26
to
Am 26.09.2021 um 22:20 schrieb Carlo XYZ:
>
> 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.

Du beschreibst exakt mein naives Verfahren, wobei ich mangels guter
Ideen für "geschickt" einfach den Zufall habe walten lassen.

Zu meiner Freude hat aber die Nachbesserung mit 2z1v-Methode
aus dem Pool von gerade mal elf 25-ern eine erkleckliche Menge von
24-ern geliefert. Daraus wurden zweiundsechzig 23-er, und momentan habe
ich etwas mehr als die Hälfte von diesen in immerhin bereits dreizehn
22-er verwandeln können. Der Appetit auf K = 21 wächst.

Hinweis: ich bin null stolz auf meine Programmierkunst oder das
eingesetzte Gehirnschmalz. Ich freue mich aber wie Bolle über die
Überraschungen aus dem "Zaubergarten der Mathematik" :-)
Auch das Bild von der einsatzfreudigen Mathe-Lehrerin und ihrer Klasse
gefällt mir sehr, weil die Anzahl um die 20 gut zu dem Bild passt.
Wie im "benachbart"-Thread geschrieben, hat eine Aufgabe aus dem Bereich
"Zwerge raten ihre Hutfarbe" mich zu meinen Untersuchungen inspiriert.

Und jetzt habe ich auch eine entsprechende Modifikation meiner aktuellen
Aufgabenstellung parat. Die werde ich aber vorläufig nicht näher
anschauen. Aber es kann nicht schaden, sie hier schon mal zu präsentieren:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
11 Aufgaben, 11 Kinder, Fehlertoleranz x
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Nehmen wir an, die Klasse hätte 11 Schüler, und die Lehrerin soll den
Kindern wieder helfen, eine "geheime Liste" zu erraten. Wenn sie nur 3
Fehler machen dürfen, wird es wohl nicht klappen.
Darum die Frage: wie viele Fehler müssen erlaubt sein, damit ein Plan
entwickelt werden kann, der ganz sicher funktioniert?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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. Na ja, vielleicht auch nur
potentiell lösbar und nicht aktual, *har* *har*.


Gruß,
RR


Carlo XYZ

unread,
Sep 26, 2021, 5:44:12 PMSep 26
to
Rainer Rosenthal schrieb am 26.09.21 um 23:02:

> Du beschreibst exakt mein naives Verfahren, wobei ich mangels guter
> Ideen für "geschickt" einfach den Zufall habe walten lassen.

Das dürfte ungünstig sein. Wie gesagt, "In erster
Näherung sollte der Hamming-Abstand zwischen v_i
und allen bislang schon abgedeckten Wörtern maximal
sein". Diese Heuristik beruht natürlich auf der Idee,
den Schnitt zwischen der Menge der neu abgedeckten
Wörter und der Menge der vorher abgedeckten klein
zu halten.

Rainer Rosenthal

unread,
Sep 27, 2021, 3:30:43 AMSep 27
to
Am 26.09.2021 um 21:52 schrieb Rainer Rosenthal:
>
> ... um damit das Abenteuer "K = 21" zu starten.
>
> (Mit dem Schlachtruf "Sinnlos, aber nicht ganz trivial!")
>

Hier die erste Lösung zu K = 21:

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]

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

Martin Vaeth

unread,
Sep 27, 2021, 5:39:19 PMSep 27
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 PMSep 27
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 PMSep 28
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 PMSep 28
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 PMSep 28
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 AMSep 29
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 AMSep 29
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 AMSep 29
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 AMSep 29
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 AMSep 29
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 PMSep 29
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 PMSep 29