Wie viele von 1 bis 100 nummerierte und vermischte Kärtchen muss man mindestens ziehen, damit das Produkt der Zahlen sicher durch 6 oder durch 7 teilbar ist?
Wir müssen mindestens 58 Karten ziehen.
Begründung:
Es existieren 57 Karten, bei denen das Produkt weder durch 6 noch durch 7 teilbar ist.
Rechenweg:
In der Summe der Primfaktoren der gezogenen Karten muss entweder die Kombination 2 und 3 oder die 7 vorkommen.
Es gibt 14 Karten, die den Primfaktor 7 enthalten.
Es gibt 50 Karten, die den Primfaktor 2 enthalten.
Es gibt 33 Karten, die den Primfaktor 3 enthalten.
16 Karten enthalten die Primfaktoren 2 und 3.
7 Karten enthalten die Primfaktoren 2 und 7.
4 Karten enthalten die Primfaktoren 3 und 7
Zwei Karten enthalten die Primfaktoren 2, 7 und 3 enthalten.
Daraus folgt, dass
5 von den Karten, die 2 und 7 enthalten, keine 3 enthalten
14 von den Karten, die 2 und 3 enthalten, keine 7 enthalten
2 von den Karten, die 3 und 7 enthalten, keine 2 enthalten
Wir sehen hier 72 Karten in den drei Kreisen.
28 Karten enthalten also keine der Primfaktoren 2, 3 oder 7.
Die 29. gezogene Karte liegt in einem der drei dargestellten Kreise.
Wenn sie in dem Siebener-Kreis läge, hätten wir gewonnen.
Uns interessiert aber der Worst-Case und dieser Worst-Case tritt augenscheinlich auf, wenn wir immer wieder aus dem gleichen Kreis ziehen.
Der mächtigste Kreis ist der Zweier-Kreis. Wir können also zusätzliche 29 Karten ziehen, ohne dass das Produkt durch 6 oder durch 7 teilbar wäre.
Die nächste Zahl jedoch muss zwangsläufig in einem der beiden anderen Kreise liegen.
Wenn du jetzt wissen willst, welche Karten das sind, schau hier:
Die weißen karten sind weder durch 2, 3 oder 7 teilbar.
Die grünen sind ausschließlich durch 2 teilbar.