Geburtstag des Diktators
Neue Frage »

03.04.2007, 16:39 Geburtstag des Diktators Auf diesen Beitrag antworten »
Geburtstag des Diktators
Hallo zusammen!

Könnte sein, dass Rätsel die bessere Kategorie gewesen wäre, aber ich kenne die Lösung schon, möchte aber wissen, wieso dies rauskommt.

Ich kenne das Ganze als "Geburtstag des Diktators". Folgendes Szenario. Der Diktator einer kleinen Bananenrepublik hat Geburtstag und will zur Feier des Tages einige Gefangene entlassen. Zur Zeit sitzen 100 Häftlinge ein. Er hat sich folgende Prozedur ausgedacht um diejenigen herauszusuchen, die entlassen werden. Zu Anfang sind alle Zellen zu. Im ersten Durchgang wird jede Zelle aufgeschlossen. Im zweiten Durchgang wird jede zweite Zelle wieder zugeschlossen. Im dritten Durchgang wird jede dritte Zelle entweder auf (wenn zu) oder zu (wenn auf) geschlossen, also zum Beispiel Zelle 6 auf, Zelle 9 zu. Und so weiter, genau 100 Durchgänge.

Die Frage (deren Antwort man leicht programmieren konnte), wie viele und welche Zellen sind nach 100 Durchgängen offen.

Ich verrate die Lösung anfangs mal nicht, wenn jemand selber basteln möchte. Aber ich frage mich, warum sind gerade genau DIESE Zellen offen (die Lösung ist nämlich m. E. nach sehr interessant!)?

Vielen Dank im voraus!
03.04.2007, 16:59 therisen Auf diesen Beitrag antworten »

Hallo,

betrachte mal die zahlentheoretische Teileranzahlfunktion. Damit kommt man schnell auf die Quadratzahlen Augenzwinkern


Gruß, therisen
03.04.2007, 17:03 AD Auf diesen Beitrag antworten »

Amnestie
03.04.2007, 17:11 Geburtstag des Diktators Auf diesen Beitrag antworten »

Das ging ja fix! smile

Ok, das es mit der Teileranzahlfunktion zu tun hat, sehe ich jetzt ein. Aber leider helfen mir leider der Wikipedia-Link, noch der Link zu der (offenen?) Diskussion...
03.04.2007, 17:12 therisen Auf diesen Beitrag antworten »

Ist eine Zelle offen, deren Nummer eine gerade Anzahl an Teilern besitzt?
03.04.2007, 17:17 GdD Auf diesen Beitrag antworten »

Nein, das nicht. Aber WIESO ist das so?

Schon klar, dass ungerade Anzahl an Teilern gleichbedeutend ist mit Qudratzahl. Nur, wie schon gesagt, warum dieser Algorithmus dies bewirkt ist mir völlig schleierhaft...

Entschuldigung, ich stehe glaube ich gerade total auf dem Schlauch!
 Anzeige 
 
03.04.2007, 17:21 therisen Auf diesen Beitrag antworten »

Anfangs sind alle Zellen zu - hat nun eine Zahl eine gerade Anzahl an Teilern, so wird in dieser der Schlüssel um eine gerade Anzahl gedreht - auf, zu, auf, zu, usw. Es endet in jedem Fall mit "zu".


Gruß, therisen
03.04.2007, 17:28 GdD Auf diesen Beitrag antworten »

Ah! Ja, so macht es Sinn! smile

VIELEN DANK!!!
03.04.2007, 21:02 kingskid Auf diesen Beitrag antworten »

hallo,

das rätsel gefällt mir smile

aber wie kann man das denn genau beweisen, dass nur quadratzahlen eine ungerade anzahl von teilern haben? d.h. man müsste erst die primfaktorzerlegung allgemein für quadratzahlen sich überlegen und dann über die teileranzahlfunktion irgendwie zur behauptung kommen...?
`
und wie könnte man das rätsel programmieren? also wenn man die lösung noch nicht weiß... muss man einen algorithmus finden, der alle zahlen mit ungerader anzahl von teilern findet...? d.h. es läuft auf ein programm raus, das alle zahlen von 0 bis 100 in ihre Primfaktoren zerlegt ...?
.. oder man bastelt einfach die aufgabe nach in dem man wirklich die zahlen nacheinander rausstreicht oder wieder dazu fügt... ??

viele grüße
03.04.2007, 21:29 therisen Auf diesen Beitrag antworten »

Die Teileranzahlfunktion ist multiplikativ. Sei und ihre kanonische Primfaktorzerlegung. Dann gilt ; das ist eine einfache kombinatorische Überlegung.
Damit ungerade ist, darf also kein Faktor in diesem Produkt gerade sein - also muss gerade sein für alle .


Gruß, therisen
03.04.2007, 21:48 AD Auf diesen Beitrag antworten »

Oder man macht wieder den Trick mit der Paarbildung:

Teiler und Teiler ... Augenzwinkern
03.04.2007, 21:57 kingskid Auf diesen Beitrag antworten »

aah, dankeschön - und eine zahl bei der alle exponenten in der primfaktorzerlegung gerade sind, ist eine quadratzahl....


jetzt würd mich nur noch das mit dem programm interessieren... verwirrt
03.04.2007, 22:01 therisen Auf diesen Beitrag antworten »

Zitat:
Original von kingskid
jetzt würd mich nur noch das mit dem programm interessieren... verwirrt


Naja, die Sache an sich zu programmieren ist doch nicht sonderlich schwer - die Frage ist nur, was man als gegeben voraussetzt; je nachdem ist das Programm mehr oder weniger optimiert Augenzwinkern
Was für eine Antwort erwartest du also?



Gruß, therisen


PS: Mit den Pärchen hast du's wohl, Arthur Big Laugh
03.04.2007, 22:03 AD Auf diesen Beitrag antworten »

Zitat:
Original von therisen
PS: Mit den Pärchen hast du's wohl, Arthur Big Laugh

Ja - die Beweise werden dann so schön kurz. Und du weißt ja, dass ich das mag. smile
03.04.2007, 22:47 kiste Auf diesen Beitrag antworten »

Zitat:
Original von kingskidjetzt würd mich nur noch das mit dem programm interessieren... verwirrt

Mit nur dem was man aus der Aufgabe weiß:
Man hat ein 1..100 array aus booleans namens T mit standardwerten auf false
code: 
1:
2:
3:
4:
5:
6:
7:

for I in 1 .. 100 loop
   for J in 1 .. 100
      if J mod I = 0 then
         T[J] = !T[J];
      end if;
   end loop;
end loop;
03.04.2007, 23:00 kingskid Auf diesen Beitrag antworten »

oh, jetzt muss ich nur noch das verstehen...
also die booleans sind variablen die entweder "true" oder "false" annehmen, oder...? aber was sind deine standardwerte?
und dann berechnest du den rest der bei division von i.ter komponente durch j.te... ?
was bedeutet das mit dem T[J] ungleich T[J] ... ?

hm ja, hätt ich vielleicht noch dazu schreiben sollen. dachte eigentlich an matlab & als gegeben hätt ich halt schon die sachen aus der aufgabe genommen, hab ja weiter oben noch was dazu geschrieben,... nur nicht unbedingt die pärchenbildung, auch wenns dann schön kurz ist... Augenzwinkern
04.04.2007, 09:53 kingskid Auf diesen Beitrag antworten »

frage hat sich erledigt, habs mit matlab hinbekommen *freu* smile

viele grüße
Wink
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Hochschulmathematik » Sonstiges » Geburtstag des Diktators