Spiel < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:14 So 06.05.2007 | | Autor: | Ares1804 |
| Aufgabe | Jan und Peter spielen das folgende Spiel:
Sie suchen sich eine natürliche Zahl n größer als null aus. Anschließend denkt sich Peter
eine natürliche positive Zahl m, die kleiner ist als n. Diese soll Jan finden. Dazu darf Jan
Peter irgendeine Zahl k nennen, woraufhin Peter ihm im Gegenzug sagt, ob m+k prim ist
oder nicht. Zeige, daß Jan Peters Zahl nach höchstens n−1 Fragen herausbekommen hat. |
Hallo an Alle,
Ich war jetzt zwar länger nicht mehr mathematisch aktiv, versuche aber dennoch mich mit Zahlentheorie auseinander zu setzen. Bei dieser Aufgabe allerdings hab ich gar keine Idee und wäre für jede Form der Unterstützung dankbar.
Viele Grüße M.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:47 Mo 07.05.2007 | | Autor: | rabilein1 |
Irgendwie ist mir die Aufgabe nicht ganz klar.
Da die gedachte Zahl m kleiner ist als n, benötigt man auf jeden Fall höchstens n minus eins Versuche, um m rauszufinden. Dazu bräuchte man nur alle Zahlen von Eins bis n aufzuzählen.
Beispiel: n=8, also darf m höchstens 7 (m<n) sein. Wenn man von 1 bis 7 zählt, hat man höchstens 7 ( 8 minus 1) Zahlen genannt, und m war auf jeden Fall dabei.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:07 Mo 07.05.2007 | | Autor: | Ankh |
Und woher weißt du, welche Zahl es war?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:40 Mo 07.05.2007 | | Autor: | cp3de |
Ich habe das mal bis n = 5 ausprobiert. Eine mögliche Strategie von Jan sollte demnach sein nacheinander k=0,...,n-3 zu erfragen (für n=2 muss Peters Zahl die 1 sein). Beispiel für n = 5:
k=0
Antwort prim: m [mm] \in [/mm] {2;3}
Antwort nicht prim: m [mm] \in [/mm] {1;4}
k=1:
Antwort prim: m [mm] \in [/mm] {1;2;4}
Antwort nicht prim: m [mm] \in [/mm] {3}
k=2:
Antwort prim: m [mm] \in [/mm] {1;3}
Antwort nicht prim: m [mm] \in [/mm] {2;4}
Der letzte Versuch wird dann noch für die korrekte Antwort verbraucht.
Probe:
m = 1
nach k=0: {1;4} und k=2: {1;3}, also {1}
m = 2
nach k=0: {2;3} und k=1: {1;2;4}, also {2}
m = 3
nach k=0: {2;3} und k=1: {3}, also {3}
m = 4
nach k=0: {1;4} und k=2: {2;4}, also {4}
Vielleicht kann ja jemand daraus einen schönen Beweis konstruieren.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:32 Mo 07.05.2007 | | Autor: | MicMuc |
Denk mal an n! + 1
Dann wäre (n! + 1) + k für 0 < k < n+1 stets nicht prim.
Wäre nun beispielsweies n!+1 prim, so beginnst bei
n!
-> Antwort: prim -> k=1 (fertig)
Ist die Antwort nicht prim, so nenne:
n! - 1
-> Antwort: prim -> k=2 (fertig)
So könnte das Spiel weitergehen ...
Allgemeine Idee:
**************
Es exisiert eine Zahl x mit:
x prim, x+k nicht prim für 0 < k < n+1
Nenne dann absteigend die Zahlen x-1 , x-2 , ..., x-(n-1)
Ein möglicher Kandidat für x wäre (siehe oben) n! + 1.
Nur muss n! + 1 nicht prim sein.
Dann bestimme die minimale natürliche Zahl c mit:
(n!+1) - c ist prim.
Setze nun x := (n!+1)-c
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 17:51 Mo 07.05.2007 | | Autor: | MicMuc |
Wie lässt sich die Ratestrategie verbessern, so dass man asymptotisch mit (ln n) Rateversuchen auskommt?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:59 Mo 07.05.2007 | | Autor: | MicMuc |
Oder kann jemand beweisen, dass es eine solche Strategie nicht gibt?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:27 Mi 09.05.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:18 Mi 09.05.2007 | | Autor: | Ares1804 |
Das hilft mir zumindest einmal weiter...Vielen Dank
|
|
|
|
