| Autor |
Beitrag |
    
Helen
| | Veröffentlicht am Sonntag, den 21. Oktober, 2001 - 11:36: | 
|
Auf einem Kreis sind 101 Ihnen unbekannte Zahlen angeordnet.Jede der 101 Zahlen ist entweder eine Null oder eine Eins.Sie können mit einer Frage die Summe zweier von Ihnen gewählter benachbarter Zahlen herausfinden.Ziel ist es, mit möglichst wenig Fragen die Summe aller 101 Zahlen zu bestimmen.
a.)im günstigen Fall
b.) im ungünstigen Fall
Genauer formuliert:
a.) Ermitteln Sie die kleinste natürliche Zahl m, für die die folgende Aussage gilt:
Es gibt eine Vorgabe der 101 Zahlen, bei der sich die gesuchte Summe durch die Beantwortung von m Fragen erschließen lässt.
b.) Ermitteln Sie die kleinste natürliche ZAhl n, für die die folgende Aussage gilt:
Für jede Vorgabe der 101 Zahlen lässt sich die gesuchte Summe nach Beantwortung von n Fragen erschließen. |
J
| | Veröffentlicht am Sonntag, den 21. Oktober, 2001 - 14:17: |
|
Versuch einer Antwort:
WEnn die anzahl der zahlen gerade wäre, wär es ganz einfach: die summe der 1. und der 2. zahl, dann die summe der 3. und der 4. zhal usw.
Leider ist 101 aber eine ungerade zahl.
du kannst dir aber klarmachen, was passeirt, wenn du nur 5 entsprechend angeordnete zahlen betrachtest. ich nenne sie a,b,c,d,e (in dieser reihenfolge)
Frage zunächst nach den summen a+b sowie c+d.
Wenn eine dieser Summen 0 oder 2 ist, genügt eine weitere frage:
Sei z.B a+b = 0. daraus folgt, dass a= 0 ist und mit der frage nach e+a kannst du e bestimmen. fertig!
Der unsgünstige Fall liegt vor, wenn a+b = c + d = 1 gilt.
Frage nun nach e+a. wenn diese summe den wert 0 oder 2 hat, kennst du wiederum e und bist fertig.
Wenn diese summe wiederum den wert 1 hat, frage nach d+e. Falls auch hier die Summe 1 ist, bleibt dir nichts anderes übrig, als nach b+c zu fragen.
Fazit: es geht darum, zwei aufeinanderfolgende nullen oder einsen zu finden. dies verrät sich durch den summenwert 0 bzw. 2.
im günstigsten fall hast du mit einer der ersten beiden fragen ein solches paar gefunden, dann genügen 3 fragen. im ungünstigsten fall musst du 5 mal fragen.
Analog bei 101 zahlen: im günstigsten fall genügen 51 fragen (nämlich, wenn bei den ersten 50 fragen einmal die summe 0 oder 2 ist).
im ungünstigsten fall musst du 101 mal fragen, wenn nämlich - bei welcher strategie auch immer - die antworten auf die ersten 100 fragen jeweils 1 lauten.
Gruß J
PS: In was für einem unterrichtlichen zusammenhang steht denn diese aufgabe? |
Helen
| | Veröffentlicht am Sonntag, den 21. Oktober, 2001 - 16:47: |
|
DAnke vielmals für die große hilfe! |
|
