www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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
Dt. Schulen im Ausland: Mathe-Seiten:

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.vorhilfe.de