Nuller-Einser-Theorie < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeigen Sie, dass es zu jeder natürlichen Zahl X mindestens eine natürliche Zahl Y gibt, so dass das Produkt X*Y nur aus Nullen und Einsen besteht. |
Dieses ist eine Anlehnung an diese Aufgabe
Ich weiß nicht, ob es einen "Beweis" für die obige Aufgabe gibt.
Es scheint mir aber plausibel / höchstwahrscheinlich, dass es für jedes X so ein Y gibt, und zwar aus folgenden Gründen:
Im Kleinen Einmaleins gibt es zu jeder Zahl mindestens einen Faktor, bei dem das Produkt auf 0 oder 1 endet
( z.B. 3*7 = 21 oder 6*5 = 30 )
Zu jeder zweistelligen Zahl gibt es mindestens eine zweistellige Zahl, bei der die letzten beiden Ziffern des Produktes 0 oder 1 sind
( z.B. 97*33 = 3201 )
Nun betrachte ich z.B. die Zahl 107
Wenn man diese Zahl mit den Zahlen von 1 bis 100.000 multipliziert, so findet sich kein einziges Ergebnis, dass nur aus Nullen und Einsen besteht.
Trotzdem habe ich die "Hoffnung", dass es doch noch irgendwann zu einem Volltreffer (Produkt besteht nur aus Nullen und Einsen) kommt. Und zwar aufgrund der Wahrscheinlichkeit.
Nehmen wir Faktoren, die bei etwa einer Milliarde liegen:
107 * 934.579.430 < 100.000.000.000
107 * 1.038.421.600 > 111.111.111.111
Damit das Ergebnis zwischen 100.000.000.000 und 111.111.111.111 liegt, gibt es also 103.842.170 mögliche Faktoren
(1.038.421.600 - 934.579.430)
Die rein rechnerische Wahrscheinlichkeit auf einen Treffer wäre bei jedem einzelnen Faktor [mm] 1:5^{11}, [/mm] also 1:48.828.125
(1:5 wegen 0 oder 1 // Es gibt 11 Stellen, die besetzt werden. Ganz vorne steht ja auf jeden Fall eine 1)
103.842.170 dividiert durch 48.828.125 ist mehr als das Zweifache.
In den nächstgrößeren Bereichen (10 Milliarden / 100 Milliarden etc.) verdoppelt sich das Verhältnis zwischen den theoretischen möglichen Faktoren und der Einzelwahrscheinlichkeit jeweils - also auf das etwa Vierfache, Achtfache etc.
Unter diesen Umständen dürfte es äußerst unwahrscheinlich sein, dass es keinen einzigen Faktor gibt, der zu dem gewünschten Ergebnis führt (nur Nullen und Einsen).
Was ich am Beispiel der 107 aufgeführt habe, trifft im Prinzip auch auf alle anderen Zahlen zu.
Das ist sicherlich kein "Beweis", aber es dürfte andererseits höchst unwahrscheinlich sein, dass irgendeine Zahl "durchrutscht" und sie bis ins "Unendliche" keinen Faktor findet, so dass das gewünschte Ergebnis erzielt wird.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:09 Mo 27.03.2017 | | Autor: | Fulla |
> Zeigen Sie, dass es zu jeder natürlichen Zahl X mindestens
> eine natürliche Zahl Y gibt, so dass das Produkt X*Y nur
> aus Nullen und Einsen besteht.
> Dieses ist eine Anlehnung an
> diese Aufgabe
>
> Ich weiß nicht, ob es einen "Beweis" für die obige
> Aufgabe gibt.
Hallo Ralph,
es gibt einen Beweis - einen sehr kurzen sogar!
Betrachte die folgenden [mm]X+1[/mm] Zahlen
1
11
111
1111
...
11...1 ([mm](X+1)[/mm]-mal die Ziffer 1)
und bestimme jeweils den Rest modulo X. Von diesen Resten sind mindestens zwei identisch bzw. zwei dieser Zahlen sind kongruent modulo X, da es [mm]X[/mm] verschiedene mögliche Reste gibt, wir aber [mm]X+1[/mm] verschiedene Zahlen betrachten.
Die Differenz dieser kongruenten Zahlen hat die Form 1...10...0 und ist teilbar durch [mm]X[/mm].
Der Beweis stammt nicht von mir; ich bin darauf gestoßen, als ich mich mit deiner Übungsaufgabe beschäftigt habe.
> Nun betrachte ich z.B. die Zahl 107
>
> Wenn man diese Zahl mit den Zahlen von 1 bis 100.000
> multipliziert, so findet sich kein einziges Ergebnis, dass
> nur aus Nullen und Einsen besteht.
So viele Produkte musst du gar nicht berechnen. Nach obigem System sind nur maximal 108 Divisionen (mit Rest) durchzuführen 
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:31 Mo 27.03.2017 | | Autor: | Fulla |
Hallo nochmal,
mit "Durchprobieren" musst du wohl noch einige Zeit lang rechnen (lassen)...
Ich habe ein kleines Programm geschrieben und rausgefunden, dass
11111111111111111111111111111111111111111111111111111
durch 107 teilbar ist.
Das sollte auch die kleinste Einser-Nuller-Zahl zu 107 sein...
EDIT:
Das ist wohl nicht die kleinste 1-0-Zahl, aber die kleinste, bei der zuerst alle 1er und dann alle 0er kommen.
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:33 Di 28.03.2017 | | Autor: | rabilein1 |
> Ich habe ein kleines Programm geschrieben und
> rausgefunden, dass
>
> 11111111111111111111111111111111111111111111111111111
>
> durch 107 teilbar ist.
Als ich mir das hinsichtlich 99 überlegt habe, bin ich auf
111.111.111.111.111.111
gekommen - weil:
Jede Zahl, die durch 99 teilbar ist, muss durch 9 und durch 11 teilbar sein, undn da gibt es diese "Quersummen-Regeln".
9 Einsen reichen aber "leider" nicht aus, auch nicht in Kombination mit Nullen, also müssen es da 18 Einsen sein, um die Quersummen-Regeln zu erfüllen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:16 Di 28.03.2017 | | Autor: | donquijote |
Hallo,
angenommen X ist nicht durch 2, 3 oder 5 teilbar. Dann gilt für [mm]a\in\mathbb{N}[/mm]:
[mm]10^a\equiv 1[/mm] mod X [mm]\Leftrightarrow X[/mm] teilt [mm]10^a-1\Leftrightarrow X[/mm] teilt [mm]Y=\frac 19*(10^a-1)[/mm], wobei Y die Zahl ist, die aus a Einsen besteht. Somit hat man gut nachprüfbares Kriterium, wann eine Zahl, die nur aus Einsen besteht, durch X teilbar ist. Insbesondere ist das immer für [mm]a=\phi(X)[/mm] der Fall, wobei [mm]\phi(X)[/mm] die Eulersche [mm]\phi[/mm]-Funktion bezeichnet.
Ist X durch 2 oder 5 teilbar, so schreibt man [mm]X=2^b*5^c*Z[/mm] mit ggT(Z,10)=1 und hängt max(b,c) Nullen hinten an. Ist X durch 3 teilbar, so kann die Zahl der Einsen verdreifacht oder verneunfacht werden, um eine durch X teilbare Zahl Y zu erhalten.
Im Beispiel X=107 ist (da X prim ist) [mm]\phi(107)=106[/mm]. Die Ordnung von 10 modulo 107 muss ein Teiler von [mm]\phi(107)[/mm] sein, es kommt also nur 2, 53 und 106 in Frage. Man rechnet nach [mm]10^2\not\equiv 1[/mm] mod 107 und [mm]10^{53}\equiv 1[/mm] mod 107. Damit ist eine aus a Einsen bestehende Zahl Y genau dann durch 107 teilbar, wenn a ein Vielfaches von 53 ist.
Allerdings greift dieses Kriterium nicht in dem Fall, wenn Y aus Nullen und Einsen "gemischt" ist, so dass es noch eine kleinere 0-1-Zahl geben könnte.
|
|
|
|
