Die Mathe-Redaktion - 16.11.2018 11:24 - 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 762 Gäste und 22 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: 1945
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-09-09


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: 2972
Aus: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-09-09

\(\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: im letzten Monat
Dabei seit: 21.10.2014
Mitteilungen: 397
Aus: Lehramtplanet
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-09-09


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
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 12.05.2017
Mitteilungen: 905
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-09-09

\(\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: 972
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-09-14

\(\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: 2831
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-09-14


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: 972
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-09-14

\(\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: 2831
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-09-14


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: 972
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2018-09-16

\(\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: 1945
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


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: 972
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-09-17

\(\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: 603
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2018-09-17


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: 972
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-09-17


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: 834
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2018-09-17

\(\begingroup\) \(\newcommand{\End}{\operatorname{End}}\newcommand{\id}{\operatorname{id}}\newcommand{\GL}{\operatorname{GL}}\)
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
salomeMe
Senior Letzter Besuch: im letzten Monat
Dabei seit: 06.10.2015
Mitteilungen: 446
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2018-09-24

\(\begingroup\)
Hallo,

darf man hier auch Fragen zur 4. Aufgabe der 2. Runde stellen?

Es scheint klar zu sein, dass die Anzahl n der Farben nicht unendlich sein kann, da man sonst jede Farbe auf genau einer Gitterlinie des Gitters anordnen könnte. Damit können keine Dreiecke mit gleich gefärbten Ecken entstehen.

Sollte es ein endliches n geben, sodass keine der n Farben zu den geforderten Dreiecken führt, so kann auch jede größere Anzahl an Farben so verteilt werden, dass keins der geforderten Dreiecke entsteht. (Man ersetzt z.B. eine Teilmenge der mit einer der bisherigen Farben gefärbten Gitterpunkte, durch hinzugekommene Farben.)

Bei zwei Farben sollte ein \((2^2+1)\)x\((2^2+1)\) Gitterquadrat ausreichen, um ein gewünschtes Dreieck zu finden.

x o x o x
x o x o x
o x o x o
o x o x o
x o x o x

Falls man keine gleichgefärbten benachbarten Gitterpunkte auf Gitterlinien zulässt, geht es noch schneller:

x o x
o x o
x o x

Meine Vorstellungskraft reicht leider nicht, mir ein Farbmuster mit noch mehr Farben vorzustellen, dass keine der gewünschten Dreiecke erzeugt.

Könnte es sein, dass man bei n Farben immer ein gewünschtes Dreieck findet, wenn man ein Gitterquadrat von \((n^2+1)\)x\((n^2+1)\) Gitterpunkten betrachtet?

Bei n=3 wären die Gitterpunkte z.B. so "gefärbt":

x o - x o - x o - x
x o - x o - x o - x
x o - x o - x o - x
- x o - x o - x o -
- x o - x o - x o -
- x o - x o - x o -
o - x o - x o - x o
o - x o - x o - x o
o - x o - x o - x o
x o - x o - x o - x

Eine Farbe (hier x) tritt bei dieser Musterung einmal mehr als alle anderen auf. Über die ganze Gitterebene betrachtet treten alle Farben mit gleicher Häufigkeit auf. Aber das ist ja noch kein Beweis dafür, dass diese Musterung optimal für das Problem ist.

Viele Grüße
salomeMe


EDIT: Mir ist die Idee gekommen, dass man über dem quadratischen Gitterausschnitt mit \((n^2+1)\) Gitterpunkten je Außenkante die Anzahl der einschreibbaren Quadrate bestimmt. Die Anzahl \(a_n\)  der Quadrate sollte
\[a_n=\sum \limits_{i=1}^{n^2} i^2 = n^2(n^2+1)(2n^2+1)/6\] sein. Selbst wenn man berücksichtigt, dass jeder Gitterpunkt mindestens Ecke von \(n^2\) Quadraten des Gitterausschnittes ist, ist \(a_n\) zu groß, um das Schubfachprinzip direkt anwenden zu können.

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
salomeMe
Senior Letzter Besuch: im letzten Monat
Dabei seit: 06.10.2015
Mitteilungen: 446
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2018-09-28

\(\begingroup\)
Hallo,

würde eventuell folgender Ansatz zu einer Lösung der 4. Aufgabe führen:

In allen quadratischen Teilausschnitten des Gitters, tritt jede der n Farben annähernd gleich häufig auf, falls auf den Außenkanten jeweils ein Vielfaches von n Gitterpunkten liegt.
Als elementare quadratische Gitterausschnitte betrachten wir alle verschiedenen nxn Gitter, in denen jede Farbe die Häufigkeit n hat und in denen keins der gleichschenkligen rechtwinkligen Dreiecke auftritt. Die Anzahl der verschiedenen elementaren quadratischen Gitterausschnitte ist für jedes endliche n ebenfalls endlich.

Falls man zeigen könnte, dass verschiedene elementare quadratische Gitterausschnitte aneinandergereiht immer ein gleichschenkliges rechtwinkliges Dreieck ergeben, blieben nur gleiche elementare quadratische Gitterausschnitte für die Aneinanderreihung übrig und würden eventuell, wie im Beitrag 14 angedeutet, zu den Dreiecken in einem \((n^2+1)\)x\((n^2+1)\) Gitter führen.

Die annähernd gleichen Farbhäufigkeiten, sollen dabei das Erreichen der geringstmöglichen Anzahl gebildeter gleichschenkliger rechtwinkliger Dreiecke bewirken.

Viele Grüße
salomeMe
\(\endgroup\)


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


So, da ich die Korrektur meiner Tüte nun abschließen konnte, wieder mal etwas (nicht repräsentative) Statistik:

Ich hatte 9 Arbeiten zu korrigieren, wobei die meisten dieser Einsendungen (6 Stück) von Teilnehmern (allesamt männlich) kamen, die ihre Schullaufbahn mit dem letzten Schuljahr schon beendet haben. (Es gab aber auch eine Einsendung eines jetzigen Neuntklässlers.) Im Schnitt wurden etwas über 11 Seiten beschrieben, wobei drei Teilnehmer die vierte Aufgabe nicht bearbeitet hatten.

Segnet die Zweit- und Drittkorrektur meine Bewertungsvorschläge ab, und kommt es zu den üblichen Punktgrenzen für die Preise, ergibt sich folgendes Bild:

1. Preis: 2 mal
2. Preis: 0 mal
3. Preis: 5 mal
kein Preis: 2 mal

Dabei stellten die ersten drei Aufgaben größtenteils kein Problem dar; insgesamt 22 (von maximal 27) mal habe ich hier volle Punktzahl vergeben. Schwierigkeiten waren hier doch eher individueller Natur (z.B. bei Aufgabe 1 zwar die korrekte Spielstrategie für ungerade Startzahlen, solche, die gerade aber nicht durch 4 teilbar sind, und solche, die durch 4 aber nicht 8 teilbar sind, angeben zu können, dann aber einen Fehler bei der weiteren Übertragung dieses Schemas auf Teilbarkeit durch höhere Zweierpotenzen zu begehen; oder bei Aufgabe 2 keine Funktion mit den angegebenen Eigenschaften angeben zu können; oder bei Aufgabe 3 sich bei einer analytischen Lösung nicht über das mögliche Verschwinden von auftretenden Nennern Gedanken zu machen).

Der Scharfrichter war -- wie erwartet und auch gewünscht -- die vierte Aufgabe. Hier habe ich bei den Einsendungen, die auch diese Aufgabe bearbeitet hatten, im Schnitt nur knapp 5 von maximal 10 Punkten vergeben können. Zwei Personen hatten richtige Ideen, wie sie für jede beliebige Farbanzahl n zeigen konnten, dass jede Färbung der Gitterpunkte der Ebene mit n Farben mindestens ein gleichschenklig-rechtwinkliges, achsenparalleles Dreieck aus gleichfarbigen Gitterpunkten besitzt. Hier bot sich ein indirekter Beweis an, und dabei die wiederholte Ausnutzung des Dirichlet'schen Schubfachschlusses. Auch wenn diese Idee den übrigen Teilnehmern auch bekannt war, gelang es ihnen nicht, das Argument sauber zu Ende zu bringen, sodass z.B. einmal die Gleichschenkligkeit der zu erzeugenden Dreiecke nur per "hand waving" erzeugt werden konnte, oder man an anderer Stelle nur ganz bestimmte Färbungen betrachtete und "zum Widerspruch führte".

Nichtdestotrotz ist es immer nett, interessante Ideen zu lesen, auf die man selbst gar nicht gekommen wäre. So arbeitet eine analytische Lösung der Geometrie-Aufgabe etwa mit komplexen Zahlen und interpretiert gleiche Winkel dadurch, dass die Quotienten bestimmter Ausdrücke rein reell, also gleich ihrem komplex-Konjugierten sind.


Nun geht der Spaß in die Zweit- und die dann abschließende Drittkorrektur, sodass Anfang November mit der Information über die Ergebnisse gerechnet werden kann. Für mich war es das für diesen BWM-Durchlauf; aber im Dezember startet ja schon der nächste. :)

Viele Grüße
Cyrix



  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]