Schubfachprinzip

Neue Frage »

Chilek Auf diesen Beitrag antworten »
Schubfachprinzip
Hi,

hat jemand Lösungsvorschläge zu dieser Aufgabe.


Gegeben seien ein Quadrat der Seitenlänge 2 und eine positive natürliche Zahl n. Wie viele Punkte muss man innerhalb des Quadraes wählen, so dass mindestens ein Paar höchstens den Abstand WURZEL(2)/n hat?


Merci
AD Auf diesen Beitrag antworten »

Zitat:
Original von Chilek
Gegeben seien ein Quadrat der Seitenlänge 2 und eine positive natürliche Zahl n. Wie viele Punkte muss man innerhalb des Quadraes wählen, so dass mindestens ein Paar höchstens den Abstand WURZEL(2)/n hat?

So formuliert glaube ich kaum, dass die Aufgabe mit dem Schubfachprinzip lösbar ist. Meinst du nicht eher sowas:

Zitat:
Gegeben seien ein Quadrat der Seitenlänge 2 und eine positive natürliche Zahl .

Gib eine hinreichende Anzahl von Punkten an, so dass es bei jeder beliebigen Platzierung dieser Punkte im Quadrat mindestens ein Paar mit höchstens dem Abstand gibt.

Das ist ein himmelweiter Unterschied zu deiner Aufgabenformulierung: Hier muss man nur für ein konkret angegebenes den Nachweis der Existenz dieser kleinen Strecke erbringen - bei deiner Formulierung muss man auch noch beweisen, dass man mit weniger als Punkten garantiert eine Konfiguration findet, wo es eine solche kleine Strecke nicht gibt - viel Spaß, denn das wäre dann wirklich sauschwer.
Chilek Auf diesen Beitrag antworten »

doch leider ist dies die Aufgabenstellung (Formuliert von einem Schweizer Dozenten).

Es gibt auch einen Hinweis zu der Aufgabe.

Hinweis: Zerlegen Sie das Quadrat in gleich grosse, kleine Quadrate und betrachten Sie die Diagonale der kleinen Quadrate.
WebFritzi Auf diesen Beitrag antworten »

Die Aufgabe ist wirklich etwas unglücklich formuliert. Ich denke aber, dass sie so gemeint ist, wie Arthur es auf den Punkt bringt.
AD Auf diesen Beitrag antworten »

Zitat:
Original von Chilek
Hinweis: Zerlegen Sie das Quadrat in gleich grosse, kleine Quadrate und betrachten Sie die Diagonale der kleinen Quadrate.

Das ist mir schon alles klar - nur wirst du auf diesem Weg nur die Aufgabe in meiner Formulierung lösen können. Wer wie was weswegen formuliert hat, ist mir übrigens völlig egal - fest steht, dass die erste Variante um Größenordnungen schwerer zu lösen ist und damit eigentlich hier nicht gemeint sein kann.
Dual Space Auf diesen Beitrag antworten »
RE: Schubfachprinzip
Zitat:
Original von Chilek
Gegeben seien ein Quadrat der Seitenlänge 2 und eine positive natürliche Zahl n. Wie viele Punkte muss man innerhalb des Quadraes wählen, so dass mindestens ein Paar höchstens den Abstand WURZEL(2)/n hat?

Ich würde sogar soweit gehen und sagen dass die Antwort "2 Punkte" die Aufgabe korrekt löst. Immerhin darf ich die Punkte laut Aufgabe "wählen", d.h. deren Platzierung beliebig bestimmen.
 
 
Chilek Auf diesen Beitrag antworten »

Ich denke auch dass die Aufgabenstellung so gemeint ist wie du es sagst. Dieser Dozent ist meist sehr sparsam mit Wörtern in seinen Aufgabestellungen böse

Trotzdem wie ist die Aufgabe dann zu lösen ?
AD Auf diesen Beitrag antworten »

Zitat:
Original von Dual Space
Ich würde sogar soweit gehen und sagen dass die Antwort "2 Punkte" die Aufgabe korrekt löst. Immerhin darf ich die Punkte laut Aufgabe "wählen", d.h. deren Platzierung beliebig bestimmen.

Bist ein Schelm, hast aber Recht. Augenzwinkern

----------------------------------

@Chilek

Überleg dir doch einfach mal, wie ein Teilquadrat aussehen muss, dessen Diagonale gleich ist, und wieviele solche Teilquadrate du brauchst, um das große Quadrat auszufüllen...
WebFritzi Auf diesen Beitrag antworten »
RE: Schubfachprinzip
Zitat:
Original von Dual Space
Zitat:
Original von Chilek
Gegeben seien ein Quadrat der Seitenlänge 2 und eine positive natürliche Zahl n. Wie viele Punkte muss man innerhalb des Quadraes wählen, so dass mindestens ein Paar höchstens den Abstand WURZEL(2)/n hat?

Ich würde sogar soweit gehen und sagen dass die Antwort "2 Punkte" die Aufgabe korrekt löst. Immerhin darf ich die Punkte laut Aufgabe "wählen", d.h. deren Platzierung beliebig bestimmen.


Naja, ich kann auch "100" sagen. Da steht nichts von "mindestens" oder dergleichen.
Chilek Auf diesen Beitrag antworten »

Wie wärs damit?

also ein Quadrat mit Seiten länge 1 hätte eine diagonale von wurzel 2, wäre also n =1 so müsste mann genau einen punkt in die mitte des quadrates setzen, da aber die seitenlänge nun 2 ist muss mann die daraus entstehenden quadrate noch mal in der digitalen einen punkt setzen also 5 punkte

für andere n's muss mann den punkt nicht in die mitte setzen sondern muss auf die diagonale n punkte setzen, mann muss sie also (n+1) teilen, dass muss mann aber mit beiden diagonalen machen, obwohl zu beachten ist, das bei ungeraden zahlen ein punkt auf den anderen fällt siehe bei n=1.

Es entstehen also immer (n+1)^2 subquadrate
da die seitenlänge 2 ist muss das 2 * gemacht werden, somit enstehen (n+1)^4 Subquadrate

nun ist die frage wieviele eckpunkte haben die subquadrate

eigentlich hätte ja jeder 4, nun gibt es aber überschneidungen

pro punkt den wir zeichnen generieren wir 4 subquadrate, also kann mann das ganze noch durch 4 teilen

Wäre das die evtl. Lösung ? ((n+1)^4)/4
AD Auf diesen Beitrag antworten »

Tut mir leid, ich hab kein Wort verstanden: Du verwendest sehr oft das Wort "muss", aber zwingende Logik verbirgt sich da nicht dahinter. unglücklich

Es geht darum, bei einer gegebenen Punktanzahl alle möglichen Punktkonfigurationen im großen Quadrat zu berücksichtigen, nicht irgendwelche speziellen Konfigurationen zu erzeugen - letzteres ist ohne jede Beweiskraft.


EDIT: Eine schwierigere, aber im Grunde genommen auf denselben Prinzipien basierende Aufgabe findest du hier:

IMO Auswahlklausur 2000 Schubfachprinzip
Dual Space Auf diesen Beitrag antworten »
RE: Schubfachprinzip
Zitat:
Original von WebFritzi
Zitat:
Original von Dual Space
Zitat:
Original von Chilek
Gegeben seien ein Quadrat der Seitenlänge 2 und eine positive natürliche Zahl n. Wie viele Punkte muss man innerhalb des Quadraes wählen, so dass mindestens ein Paar höchstens den Abstand WURZEL(2)/n hat?

Ich würde sogar soweit gehen und sagen dass die Antwort "2 Punkte" die Aufgabe korrekt löst. Immerhin darf ich die Punkte laut Aufgabe "wählen", d.h. deren Platzierung beliebig bestimmen.


Naja, ich kann auch "100" sagen. Da steht nichts von "mindestens" oder dergleichen.

Ich habe ja auch nicht behauptet, dass 2 die einzige Lösung wäre. Augenzwinkern
WebFritzi Auf diesen Beitrag antworten »

Du hast wieder recht. smile
AD Auf diesen Beitrag antworten »

Nach den von Dual Space aufgezeigten weiteren Schwächen in der ursprünglichen Aufgabenformulierung will ich nochmal die sinvollen Varianten hier anführen:

Zitat:
(A) Gegeben seien ein Quadrat der Seitenlänge 2 und eine positive natürliche Zahl .

Gib eine hinreichende Anzahl von Punkten an, so dass es bei jeder beliebigen Platzierung dieser Punkte im Quadrat mindestens ein Paar mit höchstens dem Abstand gibt.


Variante (A) wird sicher die sein, die der Aufgabensteller im Sinn hat.

Zitat:
(B) Im wesentlichen wie (A), nur dass die Anzahl diesmal minimal gewählt werden soll:
D.h., besitzt dieselben Eigenschaften wie in (A), zusätzlich muss es aber eine Punktkonfiguration mit Punkten geben, so dass alle Punktpaare einen Abstand größer als haben.

Ich hatte die Originalaufgabenstellung zunächst im Sinne (B) interpretiert und mich deswegen oben entsprechend geäußert.

Wenn man in (B) auch schwerlich eine geschlossene Formel für wird finden können, so sind doch gewisse Abschätzungen möglich. Eine wäre etwa

,

welche sich ziemlich einfach beweisen lässt. Im Grenzübergang kann man durch andere Betrachtungen heuristisch auf die Vermutung



kommen. Wegen der in diesem Grenzübergang vernachlässigbaren Randeffekte ist der Nachweis des schwächeren



noch passabel möglich, aber (**) ist ganz sicher eine harte Nuss. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »