www.vorkurse.de
Ein Projekt von vorhilfe.de
Die Online-Kurse der Vorhilfe

E-Learning leicht gemacht.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Teams · Forum · Wissen · Kurse · Impressum
Forenbaum
^ Forenbaum
Status Mathe-Vorkurse
  Status Organisatorisches
  Status Schule
    Status Wiederholung Algebra
    Status Einführung Analysis
    Status Einführung Analytisc
    Status VK 21: Mathematik 6.
    Status VK 37: Kurvendiskussionen
    Status VK Abivorbereitungen
  Status Universität
    Status Lerngruppe LinAlg
    Status VK 13 Analysis I FH
    Status Algebra 2006
    Status VK 22: Algebra 2007
    Status GruMiHH 06
    Status VK 58: Algebra 1
    Status VK 59: Lineare Algebra
    Status VK 60: Analysis
    Status Wahrscheinlichkeitst

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Nuller-Einser-Theorie
Nuller-Einser-Theorie < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Nuller-Einser-Theorie: Wahrscheinlichkeits-Beweis
Status: (Frage) beantwortet Status 
Datum: 22:28 So 26.03.2017
Autor: rabilein1

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.  








        
Bezug
Nuller-Einser-Theorie: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Nuller-Einser-Theorie: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Nuller-Einser-Theorie: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Nuller-Einser-Theorie: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorkurse.de
[ Startseite | Mitglieder | Teams | Forum | Wissen | Kurse | Impressum ]