Unter beliebigen sieben verschiedenen Zahlen in {1, 2,.., 125} gibt es zwei Zahlen x und y mit x < y ≤ 2x

Question

Aufgabe:

Zeigen Sie: Unter beliebigen sieben verschiedenen Zahlen in {1, 2, . . . , 125} gibt es zwei Zahlen x und y mit x < y ≤ 2x.

Problem/Ansatz:

Leider habe ich diese Aufgabe in einer Klausur nicht richtig bewiesen. Mich interessiert aber jetzt die Lösung. Ich glaube, ich könnte dies am Besten mit einem Widerspruch beweisen. Und ein MC{1,2,...,125} finden, mit 2x+1≤y. Hat jemand eine Ahnung eventuell?

Answer 1

Betrachte mal die Zweierpotenzen und konsultiere Herrn Dirichlet.

(Die Schubfächer werden beschriftet mit "1 und 2", "3 bis 6", "7 bis 14", "15 bis 30", "31 bis 62", "63 bis 125".)

Comments

Da die sieben gewählten Zahlen in sechs Intervallen liegen und mindestens zwei Zahlen im gleichen Intervall sein müssen, existieren immer zwei Zahlen \(x\) und \(y\) mit \(x < y \leq 2x\),  weil \(y \leq 2^{k+1}-1\) und \(x \geq 2^k\).

Irgendwie in die Richtung oder bin ich komplett falsch?

---

Nope, das ist der Sinn des Schubfachprinzips.

---

Hatte das tatsächlich noch nicht. Kann man die Aufgabe auch anders lösen? Bezweifle das dies dann abgefragt wird.

---

Was war das für eine Klausur?

---

mathematischen problemlösen und beweisen. aber halt nur so eine kleine klausur, um zu gucken, ob jeder auf dem gleichen stand ist (vom dem stoff). ich bin mir ziemlich sicher, dass wir das thema noch nicht hatten. ich komme leider mit der aufgabe gar nicht zurecht.

---

Was hattet ihr denn für Konzepte in der Vorlesung dazu?

---

ich bin mir ziemlich sicher, dass wir das thema noch nicht hatten.

Das ist auch kein Schulstoff. Wir machen es in der Begabtenförderung für Klasse 8.

---

es freut mich sehr für die 8. klässler, die dieses konzept schon auswenig können. leider darf ich trotzdem keine konzepte in der uni benutzen, welche wir noch nicht bewiesen haben ;)

diese informationen haben wir z.b. noch "als lösungsweg" bekommen:

uns wurde gesagt, dass man diese aufgabe mit der negation und einem widerspruch lösen kann. man soll sich eine teilmenge m von {1,2,...,125} nehmen mit der mächtigkeit 7. zudem soll man irgendwie von y>2x zu y>= 2x+1 kommen. und mit diese bedingungen dann ins ziel.

vielleicht hilft dir das weiter :) (mir auf jeden fall nicht haha...)

---

Naja, man muss das Konzept auch nicht gehabt haben, um daraus zu kommen. Es geht darum, die Menge so in 6 Teilmengen zu zerlegen, dass je zwei Zahlen aus einer der Teilmenge die Bedingung erfüllen. Da man dann aber 7 Zahlen wählt, weißt man, dass aus mind. einer dieser Teilmengen zwei Zahlen stammen.

Das geht auch, ohne das Schubfachprinzip zu kennen oder es zu beweisen, wenn man entsprechend gut argumentieren kann.