Die Mathe-Redaktion - 23.09.2018 14:54 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 426 Gäste und 34 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von ZetaX Naphthalin
Olympiade-Aufgaben » Bundeswettbewerb Mathematik » Bundeswettbewerb Mathematik 2018, 2. Runde
Druckversion
Druckversion
Antworten
Antworten
Autor
Schule Bundeswettbewerb Mathematik 2018, 2. Runde
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 1913
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-09-09 15:11


Hallo,
in den letzten Jahren wurden nach Einsendeschluss Lösungsideen zur 2. Runde in Threads diskutiert. Da noch keiner offen ist, möchte ich hiermit anfangen.

1. Aufgabe
Anja und  Bernd  nehmen abwechselnd  Steine  von  einem  Haufen  mit  anfangs  <math>n</math> Steinen (<math>n  \geq  2</math>). Anja beginnt und  nimmt  in ihrem  ersten  Zug  wenigstens  einen,  aber  nicht  alle  Steine  weg.  Danach  nimmt,  wer  am  Zug ist,  mindestens  einen,  aber  höchstens so  viele  Steine  weg,  wie  im  unmittelbar vorhergehenden Zug weggenommen  wurden.  Wer  den letzten Stein  wegnimmt,  gewinnt. Bei welchen  Werten von  <math>n</math>  kann  Anja den Gewinn  erzwingen, bei  welchen  kann  es  Bernd?

Eine Lösungsidee: Anja kann den Sieg erzwingen, wenn <math>n</math> keine Zweierpotenz ist. Sei also <math>n_1:=n</math> keine Zweierpotenz. Es gibt es eine ganze Zahl <math>k_1</math> mit <math>2^{k_1}\mid n_1</math> und <math>2^{k_1+1}\nmid n_1</math>. Im ersten Zug entfernt Anja <math>2^{k_1}</math> Steine, dies sind nicht alle, da <math>n_1</math> keine Zweierpotenz ist. Die Anzahl der Steine ist nun durch <math>2^{k_1+1}</math> teilbar. Bernd darf maximal <math>2^k</math> Steine entfernen, also insbesondere nicht alle. Bernd entfernt nun eine beliebige Anzahl von Steinen. Übrig bleiben <math>n_2\geq 2^{k_1+1}-2^{k_1}=2^{k_1}</math> Steine. Wenn <math>n_2</math> also eine Zweierpotenz ist, dann <math>2^{k_1}</math> und dann kann Anja auch alle Steine entfernen.
 Sei also <math>n_2</math> keine Zweierpotenz. Es gibt es eine ganze Zahl <math>k_2</math> mit <math>2^{k_2}\mid n_2</math> und <math>2^{k_2+1}\nmid n_2</math>. Im nächsten Zug entfernt Anja <math>2^{k_2}</math> Steine. Dies geht hoffentlich. Eine Begründung fehlt mir noch.

Außerdem fehlt mir noch eine Begründung, warum Bernd gewinnt, wenn n eine Zweierpotenz ist.


Die anderen Aufgaben habe ich mir noch gar nicht so richtig angeguckt.
Hat von euch jemand am Wettbewerb teilgenommen?

Viele Grüße



  Profil  Quote  Link auf diesen Beitrag Link
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 2907
Aus: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-09-09 15:49

\(\begingroup\)
Huhu ochen,

Anja* (und auch Bernd, sollte er am Zug sein) kann immer den Sieg erzwingen, wenn eine ungerade Anzahl von Steinen auf dem Stapel liegt (der ziehende Spieler nimmt dann einen Stein).

Beginnt das Spiel mit einer geraden Anzahl $n=2^k \cdot r$ mit $k$ maximal, so sind die Fälle $r=1$ und $r=2m-1$** zu unterscheiden.

Wie Du richtig analysierst, kann Anja auch im zweiten Falle den Sieg erzwingen (sie entfernt 2 Steine...). Im ersten dagegen nicht. Die Analyse erscheint mit straight forward, und ich habe sie demzufolge nicht durchgeführt...

Der junge Mann, mit dem ich Schach trainiere, nimmt an diesem Wettbewerb teil, hat aber - nach zugegeben bereits sehr überschaubarem Erfolg in der ersten Runde - leider den Einsendetermin für die zweite Runde "verpasst" (Schuld war natürlich eine Mitschülerin!).

Mein Post trägt sicher nicht zur Lösung der Aufgabe bei, aber ich möchte die allzu menschliche Geschichte doch gerne verewigen.

lg, AK.

*) Früher (als alles besser war) hatten die Damen in Beispielaufgaben noch den Anstand, Anna zu heissen
**) $m\in \mathbb{N}-\{0\}$ für unsere Algebraiker, die die 0 so natürlich finden
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
BerndLiefert
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 21.10.2014
Mitteilungen: 390
Aus: Lehramtplanet
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-09-09 16:42


2018-09-09 15:49 - AnnaKath in Beitrag No. 1 schreibt:
*) Früher (als alles besser war) hatten die Damen in Beispielaufgaben noch den Anstand, Anna zu heissen
Anja und Bernd sind wirklich zwei bescheuerte Namen.



  Profil  Quote  Link auf diesen Beitrag Link
TomTom314
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.05.2017
Mitteilungen: 898
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-09-09 20:06

\(\begingroup\)
Eine Beweisidee. Wenn ein Spieler am Zug ist, liegen n Steine auf dem Tisch und es können max k Steine genommen werden -> Paar (n,k). Sei l maximal mit \(2^l\leq k \land n=2^l r\). Beh.: Falls r ungerade (oder \(n\leq k\)) ist, kann der Spieler den Gewinn erzwingen. Ich denke, dieses läßt sich induktiv nach k oder l zeigen.

Ein Spiel fängt immer mit dem Paar (n,n-1) an. Daraus folgt dann
1) Anna(  smile ) gewinnt für \(n\neq 2^{l+1}\)
2) Anna verliert für \(n= 2^{l+1}\), da Bernd nach dem ersten Zug immer eine Gewinnsituation erhält.

Schuld war natürlich eine Mitschülerin!
Diese Wahl wäre mir als Schüler auch nicht so schwer gefallen. biggrin
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 928
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-09-14 19:59

\(\begingroup\)
Kann es sein, dass ihr das hier sehr kompliziert macht?
Oder irgendwie fehlt mir hier noch die vollständige Antwort zu der schönen Aufgabe.

Ich definiere erst mal \(d(z)\) als die höchste Zweierpotenz in der Primfaktorzerlegung von z:
\(z = 2^n \cdot u \to d(z) = 2^n\\
n \in \IN^0; u \in \IN^+; u \equiv 1 \mod 2\)

In der Binärzahl von z entspricht demnach d(z) der letzten 1 samt nachfolgenden Nullen - als kleiner Hinweis, wie man das auch mit Binärzahlen durchspielen kann.



Nun sei die Startzahl des Spiels: \(S_1 \in \IN^{>1}\).
Der i-te Zug von Anja und Bernd seien: \(a_i\) bzw. \(b_i\)
Die Startzahl vor der i-ten Runde (also vor dem Zug \(a_i\)) sei: \(S_i\)

Anjas Gewinnstrategie ist nun (wenn möglich*):
\(a_i = d(S_i) \leq S_i\)

Egal was Bernd macht, damit gewinnt Anja immer...
Was Bernd nehmen kann, ist dann immer:
\(b_i < d(S_i - a_i) \leq S_i - a_i\)

Damit ist auch gezeigt, dass Bernd niemals gewinnen kann (egal was er macht) und Anja irgendwann gewinnen wird (wenn \(d(S_i) = S_i\).


Nun müssen wir nur noch zeigen, dass dies alles den Spielregeln entspricht:

Sei \(S_i = 2^n \cdot u \to d(S_i) = 2^n\)
Damit ergibt sich: \(a_i = 2^n \leq S_i\)
Weiterhin ergibt sich für Bernd: \(S_i - a_i = 2^n \cdot (u-1)\)
Da: \(u-1 \equiv 0 \mod 2\)
\(S_i - a_i = 2^m \cdot v; m > n \to d(S_i - a_i) = 2^m > 2^n\)

Damit ergibt sich:
\(b_i \leq a_i = 2^n < 2^m \leq d(S_i - a_i)\)
(Bernd kann also nie die höchste Zweierpotenz in der Primfaktorzerlegung seiner Steinanzahl nehmen - im Gegensatz zu Anja)

Nun nimmt Bernd also eine Anzahl \(b_i = 2^l \cdot w < d(S_i - a_i)\)
Da: \(2^l \cdot w \leq 2^n \to l \leq n - \log_2 w < n\)

Es ergibt sich somit:
\(S_{i+1} = S_i - a_i - b_i\\
= 2^n \cdot u - 2^n - 2^l \cdot w\\
= 2^l \cdot \left( 2^{n-l} \cdot (u-1) - w\right)\\
= 2^l \cdot u'\)
Der letzte Faktor ist dabei ungerade, da wie soeben gezeigt \(n > l\) und es positiv sein muss.

Somit kann Anja wieder nehmen:
\(a_{i+1} = d(S_{i+1}) = 2^l \leq 2^l \cdot w = b_i\)

Und wir haben alles gezeigt...


Man könnte Anjas Gewinnstrategie somit auch etwas anders beschreiben... sie nimmt immer d(S), wobei S die Anzahl der aktuellen Steine ist; dies entspricht aber auch d(b), wobei b die Anzahl der Steine sind, die Bernd zuletzt nahm.

Es gilt immer:
\(a_i = 2^n = d(S_i)\\
b_i = 2^l \cdot w \leq 2^n = a_i < 2^m = d(S_i - a_i)\\
l < n\\
a_{i+1} = d(S_{i+1}) = 2^l \leq 2^l \cdot w = b_i\)

Damit gewinnt iwann Anja, wenn diese Strategie möglich ist.*



*Wann ist die Strategie nicht möglich?
Wenn \(d(S_1) = S_1 = 2^n\) [also zu Beginn eine Zweierpotent da liegt].
Denn dann müsste Anja mit ihrer Strategie alle Steine nehmen, aber dies ist verboten.


Dann gewinnt Bernd immer, denn:
Fall 1): \(a_1 \geq S_1/2\)
In dem Fall nimmt Anja über die Hälfte und Bernd kann einfach den Rest nehmen.

Fall 2): \(a_1 < S_1/2\)
Somit: \(a_1 = 2^m \cdot v < 2^{n-1} \to m < n-1 < n\)

In dem Fall verbleiben:
\(S_1 - a_1 = 2^n - 2^m \cdot v = 2^m \cdot \left( 2^{n-m} - v \right) = 2^m \cdot u' \)
Da \(n > m\) und die Differenz positiv sein muss, ist der letzte Faktor ungerade.
Nun liegt also eine Ausgangsbedingung für Bernd vor, in welcher Bernd die Gewinnstrategie von Anja nutzen kann... denn:
\(b_1 = d(S_1 - a_1) = 2^m \leq 2^m \cdot v = a_1\)

Also nun kann Bernd dieselbe Gewinnstrategie wie bei Anja zuvor nutzen und wird iwann gewinnen.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2815
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-09-14 20:18


Moin zusammen,

die gegebene Antwort, dass Bernd genau dann den Sieg erzwingen kann, wenn <math>n</math> eine Zweierpotenz ist, ist korrekt. Martins Lösungsidee sieht prinzipiell auch gut aus, nimmt aber fälschlicherweise an, dass Anja immer die höchste Zweierpotenz, die in der noch vorhandenen Steineanzahl enthalten ist, auch ziehen kann. Dem ist aber nicht so, wenn z.B. Bernd in seinem ersten Zug nur einen Stein zieht, für Anja aber noch mindestens 2 Steine danach auf dem Haufen liegen.

Cyrix

p.s.: Ich korrigiere gerade meine Tüte und habe deshalb natürlich auch die Musterlösungen vorliegen. Aber ich will euch ja nicht den Knobelspaß verderben. :)



  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 928
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-09-14 20:36

\(\begingroup\)
@Cyrix

Wenn Bernd mal 1 Stein nimmt und Anja wirklich ihrer Gewinnstrategie spielt, dann hat sie danach eine ungerade Anzahl an Steinen vor sich liegen und nimmt davon die höchste Zweierpotenz des Produktes, und das ist eben 1 = 2^0 - andernfalls hat Anja nicht ihrer Gewinnstrategie gespielt.

Ebenso: Sollte Bernd mal 12 Steine nehmen, dann wird Anja eine durch 4 aber nicht durch 8 teilbare Anzahl an Steinen vor sich haben und dann 4 nehmen.

\(a_{i+1} = d(b_i) = d(S_{i+1})\)
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2815
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-09-14 22:36


Stimmt, du hast Recht. Ich hatte einen Denkfehler beim Nachvollziehen deiner Lösung. Sie ist natürlich völlig korrekt. :)

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 928
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2018-09-16 12:36

\(\begingroup\)
Sind hier nur Lösungen für diese Aufgabe angebracht (und ich müsste einen neuen Thread eröffnen), oder auch für die anderen Aufgaben möglich ^^
Die zweite Aufgabe mit der Funktion war noch gut ^^


Zuerst nehmen wir an, es gebe eine solche Funktion für alle x, dann gilt für ein n:
\(n = f(1-f(n))\)
Setzen wir nun das Argument \(1-f(n)\) erneut ein:
\(1-f(n) = f(1-f(1-f(n))) = f(1-n)\)

Es ergibt sich somit:
\(1 = f(n) + f(1-n) \forall n \in \IR\)

Damit lässt sich schonmal die Summe berechnen, wenn es eine solche Funktion gibt:
\(\sum_{i=-2017}^{2018} f(i) = \sum_{i=1}^{2018} (f(i) + f(1-i)) = \sum_{i=1}^{2018} 1 = 2018\)

Nun muss/soll man noch zeigen, dass es eine solche Funktion f gibt.
Wäre denn \(f(x) = ix + \frac{1-i}{2}\) eine zulässige Funktion?

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 1913
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2018-09-17 10:05


Hallo nochmal,

Danke fuer die Loesungen :)
@Martin:
Bei der 2. Aufgabe ist <math>f\colon \mathbb{R}\to\mathbb{R}</math>
<math>\displaystyle f(x)=\begin{cases} x, &x\geq \frac 12\\ 1-x, &x< \frac 12\end{cases}</math>
eine Funktion, die die Funktionalgleichung erfuellt.
Fuer <math>x > \frac 12</math> gilt <math>1-x<\frac 12</math>. Somit folgt fuer <math>x > \frac 12</math>
<math>\displaystyle f(1-f(x))=f(1-x)=1-(1-x)=x</math>.
Fuer <math>x < \frac 12</math> gilt <math>1-x>\frac 12</math>. Somit folgt fuer <math>x < \frac 12</math>
<math>\displaystyle f(1-f(x))=f(1-(1-x))=f(x)=x</math>.
Fuer <math>x=\frac 12</math> gilt
<math>\displaystyle f(1-f(1/2))=f(1-1/2)=f(1/2)=1/2</math>.



  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 928
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-09-17 13:44

\(\begingroup\)
Ich wollte ja eine stetige Funktion... Aber okay. Reelle Funktion ist laut Wiki eben auch kein klar definierter Begriff.

Dann sollte aber auch \(f(x) = |x-1/2| + 1/2\) gehen ^^
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
MeWi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 14.03.2011
Mitteilungen: 563
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2018-09-17 14:11


Die Funktion von ochen ist stetig und stimmt mit der von dir angegebenen Funktion überein.



  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 928
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-09-17 14:33


Okay... Ochens Funktion scheint auch nicht  die Bedingung f(1-f(x)) = x zu erfüllen. Da f nur positive Werte annimmt und es somit für negative x nicht stimmen kann.

Sein Fehler ist auch, dass er in der letzten Zeile für x < 1/2 am Ende dann f(x) = x schreibt, obwohl dies 1-x =/= x ist.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 663
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2018-09-17 15:32

\(\begingroup\)
Eine Menge reeller Funktionen, für die $f(1-f(x))=x$ gilt:

Aus der Funktionalgleichung folgt, dass $f$ bijektiv ist (surjektiv ist klar und injektiv sieht man wegen $f(x)=f(y)\Rightarrow 1-f(x)=1-f(y) \Rightarrow x=y$) und dass $f^{-1}=1-f$. Daher gilt auch, dass $(1-f)\circ f=\operatorname{id}$, womit man durch umstellen $f^2(x)=f(f(x))=1-x$ findet. Daraus folgt auch, dass $f^4=\operatorname{id}$ ist. Ferner folgt, dass $f(1-f(\frac 12))=\frac 12=1-\frac 12=f^2(\frac12)$, also da $f$ injektiv ist $1-f(\frac 12)=f(\frac12)$, d.h. $f(\frac 12)=\frac 12$.
Das motiviert folgende Konstruktion:
Wir zerlegen das Intervall $(\frac 12, \infty)$ in zwei gleichmächtige disjunkte Mengen $A$ und $B$. Sei $g:A\to B$ eine Bijektion. Sei $A':=\{x\in\IR\mid 1-x\in A\}$ und $B':=\{x\in \IR\mid 1-x\in B\}$. Dann sind auch $A'$ und $B'$ disjunkt und es gilt $A'\cup B'=(-\infty, \frac12)$. Wir definieren:\[f(x)=\begin{cases}g(x), &\text{ falls }x\in A\\
1-g^{-1}(x), &\text{ falls }x\in B\\
1-g(1-x), &\text{ falls }x\in A'\\
g^{-1}(1-x), &\text{ falls }x\in B'\\
\frac12, &\text{ falls }x=\frac12\\\end{cases}\]
Jedes so definierte $f$ erfüllt die Funktionalgleichung $f(1-f(x))=x$.

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
ochen hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]