Aufgabe #93 (MexMO),(?) < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 15:53 Do 08.09.2005 | | Autor: | Hanno |
Hallo an alle!
$N$ Studenten sitzen in einem [mm] $m\times [/mm] n$-Block von Stühlen, [mm] $m,n\geq [/mm] 3$. Jeder Student schüttelt mit seinen Sitznachbarn (horizontal,vertikal,diagonal) die Hände. Wenn es insgesamt 1020 Handshakes gab, was ist dann $N$?
Liebe Grüße,
Hanno
|
|
| |
|
Hallo Hanno,
I)
es gibt $(n-2)*(m-2)$ Studenten, die in der der Mitte sitzen, also 8 anderen Studenten die Hand schütteln.
es gibt $2*(n-2)+2(m-2)$ Studenten, die am Rand sitzen, also 5 anderen Studenten die Hand schütteln.
Und zuletzt gibt es noch 4 Studenten, die in einer der Ecken sitzen und 3 Nachbarn begrüßen.
Insgesammt gilt somit:$8nm-16n-16m+32+10n-20+10m-20+12=2040$
[mm] $\gdw [/mm] N = [mm] nm=\frac{6(n+m)+2036}{8}$
[/mm]
II)
es es werde nun m, nach obiger Gleichung, als eine von n abhänge Variable betrachtet. Es gilt: [mm] $m=f(n)=\frac{1018+3n}{4n-3}$
[/mm]
Nun erstelt man eine Wertetabelle von f. Hierbei muss man den Begriff Wertetabelle nicht zu wörtlich nehmen, sondern lediglich die f(n) für n=3,4,... auf ihre Ganzzahligkeit (die man recht schnell erkennet) hin überprüfen.
Man erhällt als erstes Ergebnis n,f(n)=14,20.
Da aber ab $n [mm] \ge [/mm] 17$ $f(n)>n$ ist kann es aus Symmetriegründen von m und n und der Monotonie von f keine weiteren Lösungen geben.
Es gilt also: $N=nm=14*20=280$
Wenn du ne elegante Lösung für die Aufgabe kennst, würd die mich noch interessieren, da meine Rechnerei wohl eher eine Not-Lösung darstellt.
Gruß Samuel
|
|
|
| |
|
Hallo Samuel,
ich glaube, da hat sich ein Fehler eingeschlichen:
> es gibt [mm](n-2)*(m-2)[/mm] Studenten, die in der der Mitte
> sitzen, also 8 anderen Studenten die Hand schütteln.
Dann haben sich aber alle doppelt und dreifach die Hand geschüttelt.
> es gibt [mm]2*(n-2)+2(m-2)[/mm] Studenten, die am Rand sitzen,
> also 5 anderen Studenten die Hand schütteln.
Von den "mittigen" Studenten eine Reihe im Innern wurde den Randstudenten schon die Hand geschüttelt. Sie müssen also als Randstudenten nur untereinander schütteln.
> Und zuletzt gibt es noch 4 Studenten, die in einer der
> Ecken sitzen und 3 Nachbarn begrüßen.
Siehe oben.
> Insgesammt gilt somit:[mm]8nm-16n-16m+32+10n-20+10m-20+12=2040[/mm]
Die richtige Formel müsste meiner Ansicht nach heißen:
handshakes = 3(n-1)(m-1) + (n-1) + (m-1).
Denn wenn alle Studenten ab der 2.Reihe 2. Spalte allen Nachbarn links, oberhalb und links-oberhalb von ihnen (Matrix von "oben" gesehen) die Hand schütteln, dann ist allen die Hand geschüttelt, bis auf denjenigen in der 1. Reihe bzw. 1. Spalte, die untereinander noch nicht geschüttelt haben. Dazu genügt es, wenn jeder seinem linken Nachbarn (1. Reihe) oder seinem Nachbarn über ihm (1. Spalte) die Hand gibt.
Gruß Richard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:09 Mo 12.09.2005 | | Autor: | Sigrid |
Lieber Richard,
> Die richtige Formel müsste meiner Ansicht nach heißen:
> handshakes = 3(n-1)(m-1) + (n-1) + (m-1).
> Denn wenn alle Studenten ab der 2.Reihe 2. Spalte allen
> Nachbarn links, oberhalb und links-oberhalb von ihnen
> (Matrix von "oben" gesehen) die Hand schütteln, dann ist
> allen die Hand geschüttelt, bis auf denjenigen in der 1.
> Reihe bzw. 1. Spalte, die untereinander noch nicht
> geschüttelt haben. Dazu genügt es, wenn jeder seinem linken
> Nachbarn (1. Reihe) oder seinem Nachbarn über ihm (1.
> Spalte) die Hand gibt.
Wenn ich das richtig sehe, fehlt dir jetzt die Verbindung nach rechts-oberhalb.
Das heißt, als Formel ergibt sich
h(n,m) = = 4(n-1)(m-1) + (n-1) + (m-1).
Gruß
Sigrid
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:39 Mo 12.09.2005 | | Autor: | chmul |
Hallo Ihr,
also ich komm immer auf einen etwas anderen Ansatz. Ich bin zwar noch nicht zu einem Ergebnis gekommen, habe mir aber folgendes überlegt:
m sei die Anzahl der horizontalen Sitze;
n sei die Anzahl der vertikalen Sitze;
1020 = (n-2)(m-1)4 + 2(m-1) + 3(m-1) + 1(n-1)
da kein "handshaking" doppelt gewertet werden soll, gibt es n-2 Reihen vertikal (ohne 1te und letzte Reihe) mit m-1 Elementen horizontal (ohne der letzten Reihe), die mit je 4 Nachbarn Händeschütteln (dem unteren, dem diagonal rechts oben, dem rechts sitzenden und dem diagonal rechts unten).
=> (n-2)(m-1)4
Nun bleiben noch die oberste Reihe, die unterste und die rechts äußerste.
oberste Reihe: je 3 ( dem unteren, dem rechts sitzendem und dem rechts diagonal unten sitzendem).
=> 3(m-1)
unterste Reihe: je 2 (dem diagonal rechts oben sitzendem und dem rechts sitzendem)
=> 2(m-1)
rechts äußerste Reihe: je 1 ( dem unteren)
=> 1(n-1)
Vielleicht habe ich auch einen Denkfehler eingebaut, müsste aber glaub ich stimmen.
MfG
chmul
hab noch nen Fehler entdeckt und ausgebessert.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:24 Mo 12.09.2005 | | Autor: | chmul |
also ich hätte auch m=14 und n=20 (und umgekehrt) also Lösung und komm damit auch auf 280.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:17 Mo 12.09.2005 | | Autor: | Toellner |
Liebe Sigrid,
Du hast natürlich recht, ich habe die nach rechts oben vergessen...
Leider reicht dann die Änderung von 3 zu 4 nicht (mehr).
Am besten, wir machen es wie teletubby:
(n-2)(n-2) innere Studenten mit je 4 handshakes,
zwei Rand-Zeilen mit je n-1 linken Nachbar-Handschlägen und
zwei Rand-Spalten mit je m-1 Handschlägen zum Obermann, macht
handshakes = 4(n-2)(m-2) + 2(n-1) + 2(m-1).
Ich hoffe, jetzt stimmts...
Nein, auch nicht.
Samuel (teletubby) hat recht.
Grüße, Richard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:37 Mo 12.09.2005 | | Autor: | Sigrid |
Lieber Richard,
>
> Du hast natürlich recht, ich habe die nach rechts oben
> vergessen...
> Leider reicht dann die Änderung von 3 zu 4 nicht (mehr).
Doch es reicht. Denn die handshakes nach rechts oben, die du an der rechten Seite zu viel zählst, hast du ja an der linken noch nicht gezählt. Du kommst dann auch genau auf die Hälfte von Samuels Lösungsterm.
> Am besten, wir machen es wie teletubby:
> (n-2)(n-2) innere Studenten mit je 4 handshakes,
> zwei Rand-Zeilen mit je n-1 linken Nachbar-Handschlägen
> und
> zwei Rand-Spalten mit je m-1 Handschlägen zum Obermann,
> macht
> handshakes = 4(n-2)(m-2) + 2(n-1) + 2(m-1).
> Ich hoffe, jetzt stimmts...
> Nein, auch nicht.
> Samuel (teletubby) hat recht.
Das hat er auf jeden Fall.
>
> Grüße, Richard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:32 Mo 12.09.2005 | | Autor: | Teletubyyy |
Hallo Richard
>
> ich glaube, da hat sich ein Fehler eingeschlichen:
> > es gibt [mm](n-2)*(m-2)[/mm] Studenten, die in der der Mitte
> > sitzen, also 8 anderen Studenten die Hand schütteln.
> Dann haben sich aber alle doppelt und dreifach die Hand
> geschüttelt.
Meiner Meinung nach, haben sich dann alle genau zweimal die Hände geschüttelt, wenn mann die am Rand und in den Ecken dazunimmt, müsste doch 8nm-16n-16m+32+10n-20+10m-20+12 ganau die Doppelte anzahl der Handschakes ergeben, also nach Vorraussetzung 2040 sein.
Wo liegt also der Fehler?
Gruß Samuel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:01 Mo 12.09.2005 | | Autor: | Toellner |
Hallo Samuel,
Du hast recht, meine Gedanken sind Quatsch! Sorry...
Gruß Richard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:44 Sa 01.10.2005 | | Autor: | dreh |
hi.
also ist doch ganz einfach. man hat nen block mit n*m sitzplaetzen, auf jedem sitzt ein mensch und soll jedem nachbarn die handschuetteln. man unterteilt das handschuetteln einfach in vier richtungen: vonlinks nach rechts, unten nach oben, links unten nach rechts oben und rechts oben nach links unten.
1. links -> rechts
es gibt m reihen und n spalten also gibt es hier: (n-1) * m handshakes
2. unten -> oben
(m-1)*n
3. rechts unten -> links oben
[ (m-1)*(n-m-1) + 2*{ (m-2) + (m-3) + .... + 1}]
4. rechts oben -> links unten
siehe 3.
5. zusammenzaehlen
es gilt : 1 + 2 + 3 + ... + n = n*(n+1)/2
also : 1. + 2. + 3. +4. = (n-1) * m + (m-1)*n + 2*[ (m-1)*(n-m-1) +2*{ (m-2) + (m-3) + .... + 1}]
= 4*m*n - 5*m - 3*n + 3 = 1020
nun muss man nur noch n und m ausrechnen, was aber recht simpel ist.
sers dreh
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:09 Mi 05.10.2005 | | Autor: | Cool-Y |
"4*m*n - 5*m - 3*n + 3 = 1020"
diese formel ist leider falsch. wenn du mal eine 3x3 anordnung ansiehst und die "handshakes" abzählst, kommst du auf 20, und nicht auf 15, was deine formel behauptet. die richtige formel ist die von samuel. und was das eigentlich schwere an der aufgabe ist, ist das auflösen nach m und n in den ganzen Zahlen.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:40 Mo 17.10.2005 | | Autor: | DirkG |
Die Gleichung $4mn-3m-3n-1018=0$ kann man in die Produktdarstellung $(4m-3)(4n-3) = 4081 = [mm] 7\cdot 11\cdot [/mm] 53$ überführen. Wegen [mm] $4m-3\equiv 4n-3\equiv 1\mod [/mm] 4$ bleiben dann nur die Varianten $4m-3=77,4n-3=53$ oder umgedreht $4m-3=53,4n-3=77$ übrig, also $(m,n)=(20,14)$ und $(m,n)=(14,20)$.
Natürlich gibt es theoretisch noch die Variante $4m-3=1,4n-3=4081$, aber ein derart länglicher Hörsaal ist mir noch nicht untergekommen...
|
|
|
|
