Aufgabe #49 (IrMO) < MO andere Länder < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 10:45 Sa 09.07.2005 | | Autor: | Hanno |
Hallo an alle!
Wieder ein paar Aufgaben aus der irisichen Mathematik-Olympiade, die meines Erachtens immer wieder besonders schöne Aufgaben zu bieten hat:
Es sei $A$ eine Teilmenge von [mm] $\{0,1,2,...,1997\}$, [/mm] die mehr als $1000$ Elemente beinhaltet. Beweise, dass $A$ entweder eine Zweiterpotenz enthält oder aber zwei Elemente [mm] $a,b\in [/mm] A$, für die $a+b$ eine Zweierpotenz ist.
Liebe Grüße,
Hanno
|
|
| |
|
Hallo Hanno,
Ich hoffe dass meine lösung nicht zu mathematisch unexakt ist!
es können als Summe zweier Zahlen aus A Zweierpotenzen bis [mm] $2^{11}=4024$ [/mm] gebildet werden.
Die Betrachtung der Zerlegung von [mm] 2^{10} [/mm] in Summen liefert:
(1 + 1023) , (2 + 1022) , ... , (511 + 512);
Es gibt also 511 Zahlenpaare von denen in der gesuchten Teilmenge T jeweils nur ein Element auftauchen darf.
Zieht man die Zerlegung von kleiner Zweierpotenzen (etwa [mm] 2^9) [/mm] in Erwägung,
(1 + 511) , (2 + 510) , ... , (255 + 257);
so sieht man, dass es am effektivsten ist jeweils die kleineren Elemene zu streichen (also nicht in T aufzunehmen), da diese auch bei der Bildung von kleineren Zweierpotenzen auftreten können.
Zuletzt betrachte ich noch zerlegungen von [mm] 2^{11}:
[/mm]
(51 + 1997) , (52 + 1996) , ... , (1023 + 1025).
Man sieht, dass nur Zahlen >50 auftreten. Da alle Zahlen <50 aber in mindestens 5 anderen Paaren (für [mm] 2^6 [/mm] bis [mm] 2^{10}) [/mm] enthalten sind, widerspricht dies obiger Überlegung nicht.
Jetzt müssen aber alle Zahlen <1024 und 1024 als Zweierpotenz gestrichen werden.
Damit ergibt sich dann [mm] $T_{max}:= [/mm] [1025;1997]$ bzw. [mm] $\#T \le [/mm] 973$
Jede andere Teilmenge mit mehr als 973 Elementen - also insbesondere auch jede mit mehr als 1000 Elementen - beinhaltet somit entweder eine Zweierpotenz, oder zwei Zahlen, deren Summe eine Zweierpotenz ist. w.z.b.w.
Gruß Samuel
|
|
|
| |
|
Hallo Teletubby,
ich habe den selben Ansatz genommen, wie Du. Hoff mal, das ist richtig. Du musst allerdings aufpassen, dass Du eine Zahl nicht mehrfach streichst.
z.Zg.
unter den 1998 Elementen der Menge B:={0,1,2,...,1997} gibt es mehr als 997 Elemente a, die entweder eine Zweierpotenz sind, oder für die es ein Element a' [mm] \in [/mm] B gibt mit a+a' ist eine Zweierpotenz, bei a <= a'. Die letzte Bedingung verhindert nur, dass ein solches Paar doppelt gezählt wird.
Für jede Zweierpotenz [mm] 2^n [/mm] gibt es darüber hinaus [mm] 2^n [/mm] Arten diese als Summe zweier Zahlen darzustellen.
Für zwei Zahlen aus der Menge B (c,d [mm] \in [/mm] B) gilt c+d <= 1997+1997. Damit ist 2048 die größte darstellbare Zweierpotenz.
Für 2048 gibt es folgende Darstellungen:
51 + 1997
52 + 1995
.
.
1023 + 1025
1024 + 1024
1025 + 1023
1026 + 1022
.
.
1997 + 51
Wenn man die Reihenfolge der Summanden nicht berücksichtigt, dann erhält man also 1024 - 51 + 1 = 974 Zahlenpaare, die nicht enthalten sein dürfen, damit verhindert wird, dass die Zweierpotenz 2048 gebildet werden kann.
Sei nun B' := B \ {51, 52, ..., 1024}
Es gilt also
| B' | = | B | - 974
Damit sind alle Elemente c aus B' entfernt, für die gilt 51 <= c <= 1024. Es gibt somit kein Element c>50 mehr in B' für das c eine Zweierpotenz ist, denn die nächste Zweierpotenz ist 2048.
Falls eines der herausgenommenen Elemente zurück gestellt wird, wäre es wieder möglich die Zahl 2048 aus zwei Elementen zu bilden. Es handelt sich also wirklich um eine minimale Menge, die aus B herausgenommen wurde um B' zu bilden.
Für zwei Elemente c,d [mm] \in [/mm] B' mit c,d <= 50 gilt somit c+d<=100<128. Es ist also 64 die Zweierpotenz, die als Summe zweier Zahlen darstellbar ist.
Es gilt, dass 64 darstellbar ist als
0 + 64
1 + 63
2 + 62
.
.
.
64 + 0
davon sind nur die Zahlen interessant, bei denen beide Summanden kleiner als 51 sind, da alle Zahlen zwischen 51 und 1024 bereits aus B' entfernt wurden.
14 + 50
15 + 49
.
.
.
32 + 32
33 + 31
.
.
.
50 + 14
Wenn man die Reihenfolge nicht beachtet erhält man 32 - 14 + 1=19 Paare.
Sei nun B'':= B' \ {14, 15, ..., 32}.
Damit enthält B'' nur noch die Zahlen 0...13, 33...50, 1025...1997 und es gilt | B \ B'' | = | B | - 974 - 19 = | B | - 993
Die nächste noch darstellbare Zahl ist 0 < 16 < 13 + 13. Denn es gibt keine Zahl zwischen 32 und 64, die eine Zweierpotenz ist.
Für 16 gibt es folgende Darstellungen:
0 + 16
1 + 15
.
.
.
16 + 0
unter den vorhandenen Zahlen gibt es folgende Möglichkeiten:
3 + 13
4 + 12
.
.
.
8 + 8
9 + 7
13 + 3
das sind 6 verschiedene Paare.
Wenn man davon wiederum die niedrigere Zahl entfernt erhält man:
B'''=B'' \ {3, 4, ..., 8}
| B''' | = | B'' | - 6 = | B | - 999 = 998
Somit enthält also B''' bereits jetzt weniger als 1000 Elemente. Damit muss Jede Menge A, die Teilmenge von B ist mit | A | >= 1000 entweder eine Zweierpotenz enthalten, oder zwei Elemente b,c, für die b+c eine Zweierpotenz ist, denn A muß mindestens ein Element aus der Menge B \ B''' enthalten!
Gruß
Jürgen
|
|
|
|
