Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03613.jsonl.gz/123

- Wettbewerb 2015
- Neuigkeiten
- Über uns
- Agenda
- Bilder
- Videos
- Training
- Forum
- Archiv
Maus Sam verbrachte seine letzten Sommerferien in den Vereinigten Staaten. Während seiner Reise besuchte er viele interessante Sehenswürdigkeiten, eine davon war eine Ausstellung über Quilts. In dieser Ausstellung sah er einen Quilt mit einem Stern so wie auf dem Bild.
Er bemerkte, dass man folgendes tun kann: Zuerst wählt man eine Ecke des Sterns und setzt sich dorthin. Dann beginnt man, entlang einer der beiden Linien zu laufen, die diese Ecke verlassen, und man läuft in einer geraden Linie, bis man eine andere Ecke erreicht. Jedesmal, wenn man bei einer Ecke ankommt, fährt man weiter auf der anderen Linie, die die Ecke verlässt. Sobald man die Ecke erreicht, bei der man begonnen hat, hört man auf. Für den abgebildeten Stern würde man jede Ecke genau ein Mal besuchen und genau ein Mal entlang jeder Linie laufen.
Verallgemeinert gesagt kann ein solcher Stern mit zwei Zahlen a und b (wobei b < a/2) beschrieben werden – die Anzahl Ecken des Sterns und die Anzahl Ecken, die man überspringt, wenn man entlang einer Linie läuft (inklusive der Ecke, die man verlässt). Wir nennen einen solchen Stern (a,b)-Stern, der abgebildete Stern zum Beispiel ist ein (8,3)-Stern. Um einen solchen Stern zu zeichnen, beginnt man mit einem Kreis. Auf dem Kreis zeichnet man a gleichmässig verteilte Punkte. Dann verbindet man jeden Punkt mit zwei anderen Punkten: mit dem b-ten Punkt im Uhrzeigersinn und mit dem b-ten Punkt im Gegenuhrzeigersinn (d.h. in beiden Richtungen lassen wir b-1 Punkte aus zwischen den beiden Punkten, die mit einer Linie verbunden sind).
Maus Sam fragte sich: «Ist es immer möglich, einen solchen (a,b)-Stern mit einem einzigen Strich zu zeichnen?» Indem er einige Paare (a,b) ausprobierte, merkte er schnell, dass dies nicht der Fall ist. Deshalb würde es ihn nun interessieren, wann es möglich ist und wann nicht.
Versuche, Maus Sam zu helfen: Beweise oder diskutiere die notwendigen und hinreichenden Bedingungen, wann ein solcher Stern mit einem einzigen Strich gezeichnet werden kann und wann nicht. Schreibe auch ein Programm, das diese Bedingungen überprüft, d.h. schreibe ein Programm, das für gegebene a und b berechnet, ob es möglich ist, einen (a,b)-Stern mit einem einzigen Strich zu zeichnen.
Beachte, dass das Beweisen/Argumentieren die meisten Punkte geben wird und nicht eine simple Antwort auf die Frage.
Zwei positive Ganzzahlen a und b (a ≥ 5, 2 ≤ b < a/2).
«Yes», wenn der Stern mit einem einzigen Strich gezeichnet werden kann, sonst «No» (Die Anführungszeichen sind nur zur besseren Lesbarkeit angegeben.).
8 3
Yes
12 4
No