| Autor |
Beitrag |
    
cracker
| | Veröffentlicht am Samstag, den 28. Juli, 2001 - 09:58: | 
|
Auf einem Kreis sind n 1 er, n 2er und n 3er angeordent. Gibt es immer einen Kreisbogen, so dass alle Zahlen darin ein Summe von 3n ergeben?
Wäre dankbar für schlaue antworten! |
Matroid (Matroid)
| | Veröffentlicht am Samstag, den 28. Juli, 2001 - 21:34: |
|
Warum gerade auf einem Kreis.
Die Summe der anzuordnenden Zahlen betraegt:
n + 2n + 3n = 6n
Wie soll dann 3n als Summe herauskommen.
Oder hat der Kreis etwas damit zu tun? |
Olaf (Nixwiss)
| | Veröffentlicht am Sonntag, den 29. Juli, 2001 - 10:31: |
|
Du kannst dir die Zahlen auch auf einer Geraden angeordnet vorstellen, das ist nicht so wichtig:
Nimm z.B. die Zahlen
2,1,2,1,3,3,2,3,1
Hier ist n=3. Die Frage lautet, ob es bei jeder beliebigen Anordnung dieser 9 Zahlen immer eine Teilsequenz (diese entspricht dem Kreisbogen) mit der Summe 3n=9 gibt. In dieser besteht eine solche Teilsequenz aus den grünen Zahlen. |
Thomaspreu (Thomaspreu)
| | Veröffentlicht am Sonntag, den 29. Juli, 2001 - 14:18: |
|
Es geht um einen Kreisbogen; also: ein Stück des Kreis, das zusammenhängen ist.
Eine Lösung hab ich jetzt dafür auch nicht. Es sieht fast nach Bundeswettbewerbsniveau aus. Ich persönlich kenne diese aufgabe aber (so) nicht in der aktuellen zweiten Runde des BWM. Also scheint nichts dagegen zu sprechen hier die allgemeine Lösung zu posten. |
Thomaspreu (Thomaspreu)
| | Veröffentlicht am Sonntag, den 29. Juli, 2001 - 14:23: |
|
Tatsächlich reicht die Gerade aus. Denn, wenn ein Kreisbogen 3*n ergibt und in der Geraden wird genau dieser Bogen durchtrennt, gibt es immer den komplementären Bogen (alle Zahlen, die nicht auf dem ersten Bogen drauf sind), der nicht durchtrennt wird. |
Matroid (Matroid)
| | Veröffentlicht am Sonntag, den 29. Juli, 2001 - 15:39: |
|
Ok, verstanden.
Aber man braucht den Kreis.
Für n=2:
1 2 3 3 2 1
enthält keine Gruppe mit Summe 4, wenn man die Zahlen auf einer Strecke anordnet.
Man muß den Kreis schliessen, dann findet man z.B. 2+1+1 = 4
Aber mehr weiß ich noch nicht. |
Olaf (Nixwiss)
| | Veröffentlicht am Sonntag, den 29. Juli, 2001 - 15:49: |
|
Hi Matroid,
nein, für n=2 musst du nicht die Summe 4, sondern 3n=6 hinbekommen. Dann brauchst du auch in deinem Beispiel keinen Kreis:
1,2,3,3,2,1
Die grüne Teilsequenz hat die Summe 6! |
Matroid (Matroid)
| | Veröffentlicht am Sonntag, den 29. Juli, 2001 - 17:45: |
|
Ich versuchs mal algorithmisch.
Verfahren zum Auffinden einer Gruppe mit Summe 3n:
1) Markiere einen beliebigen Anfang
2) Geh nach rechts und addiere die Zahlen, die kommen, bis die Summe >= 3n ist.
Wenn die Summe 3n ist, dann zum Ende
4) Lasse bei den ausgewählten Zahlen von links Zahlen weg, solange bis die Summe der verbleibenden Zahlen <= 3n ist.
Wenn die Summe 3n ist, dann zum Ende
Sonst gehe zu 2.
Ende)
Bei dem Verfahren ist jede Summe, bei der Schritt 2 oder Schritt 3 unterbricht, eine der Zahlen:
3n-2 oder 3n-1 oder 3n oder 3n+1 oder 3n+2.
Andere kommen nicht in Frage, denn dann hätte man ja noch eine weitere Zahl hinzunehmen können oder hätte eine weggelassene Zahl behalten müssen.
Nach jedem Schritt 2 oder 3 hat man entweder eine andere Summe oder die gleiche Summe wie vorher.
Aber immer nur eine von den genannten 5 Zahlen.
Die neue Summe unterscheidet sich von der vorigen maximal um 2 (eine 1 hinzu und eine 3 weg, oder umgekehrt).
Da die erste Auswahl (falls nicht gleich 3n und Fertig) eine Summe größer 3n hat, haben die nicht ausgewählten Zahlen eine Summe kleiner 3n.
D.h. wenn das Verfahren eine Weile läuft, dann könnte man irgendwann genau die jetzt nicht ausgewählten Zahlen in der Auswahl haben.
???
Könnt ihr mir bei der Begründung helfen? |
mrsmith
| | Veröffentlicht am Dienstag, den 31. Juli, 2001 - 10:09: |
|
hallo zusammen,
anschliessend an das Verfahren von Matroid moechte ich folgenden versuch vermerken:
es gibt insgesamt 3n (= anzahl der zahlen auf dem kreis) markierbare anfangspunkte.
angenommen bei keinem dieser anfangspunkte ergibt sich zwischendrin (bei zaehlung in einer bestimmten richtung, die fuer alle anfangspunkte gleich sein soll) als summe 3n, dann gibt es nur folgende drei moeglichkeiten:
1) entweder man erhaelt die summen 3n-1 und 3n+1.
zwischen diesen liegt eine 2. dieser fall kann hoechstens n mal vorkommen, weil es nur n 2er gibt.
2) oder man erhaelt 3n-2, 3n+1, wobei dazwischen eine 3 liegt, was wieder n mal vorkommen kann,
3) oder man erhaelt 3n-1, 3n+2, was ebenfalls n mal vorkommen kann.
nach dieser ueberlegung muessen die beiden faelle 2) und 3) stets direkt hintereinander auftreten, da fuer beide dieselbe 3 gebraucht wird. d.h. "gegenueber" von jeder 3 muss eine 1 auf dem kreisbogen liegen.
wie geht es nach den faellen 2) und 3) weiter?
zwangslaeufig wird auf der markierten seite hinter der 1, die die faelle 2) und 3) verbindet eine 3 stehen muessen, da nur diese die letzte summe 3n+2 auf 3n-1 druecken kann. (dass keine 2 folgen kann ist klar, da ansonsten 3n+2-2 = 3n waere. es kann aber auch keine 1 sein, da ansonsten in der vorletzten sequenz "3n-2 auf 3n+1" durch die neue wahl des anfangspunktes diese auf "3n-3 auf 3n" gesenkt wuerde.) dann muss aber auf der entgegengesetzten seite nach der vorhergehenden ueberlegung zwangslaeufig eine 1 stehen. mit dieser wird aus der summe 3n-1 aber
3n-1 + 1 = 3n. dies ist ein widerspruch. die annahme, dass es keinen kreisbogen gibt, der als summe der zahlen 3n ergibt, war also falsch.
gruss mrsmith. |
pecahuna
| | Veröffentlicht am Mittwoch, den 01. August, 2001 - 09:37: |
|
hallo mrsmith,
die idee ist ja nicht schlecht, aber die ausarbeitung ist lausig.
tatsache ist naemlich, dass nicht fall 3) nach fall 2) kommt, sondern umgekehrt kommt fall 3) zuerst und dann erst fall 2).
die argumentationen im letzten teil muessten also angepasst werden. das ergebnis, dass man einen widerspruch erhaelt, bleibt aber, glaube ich, erhalten.
viele gruesse pecahuna |
Matroid (Matroid)
| | Veröffentlicht am Mittwoch, den 01. August, 2001 - 12:09: |
|
Danke mrsmith und pecahuna.
Damit ist die Aufgabe dann gelöst.
Oder hat noch jemand eine einfachere Idee.
Gruß
Matroid |
|
