Skaka hand -lådprincip

Hej!! :)

Jag behöver hjälp med en klurig uppgift som handlar om lådprincipem. Jag har ingen aning om hur jag ska tänka.

"Visa att ifall det är ett möte mellan 6 personer så kommer minsta två att skaka hand lika många gånger."

Är man fast finns många generella tips, om vi tar två som känns relevanta.

1. "Rita en figur" Försök visualisera handskakningsprocessen då detta ger dig en bättre förståelse för vad problemet handlar om. Grafer, dvs punkter och streck mellan dem är ett vanligt sätt att modellera handskakningar.

2. Förenkla. Om man inte kan lösa problemet kan man försöka göra det enklare och hitta strategier för att lösa det problemet. Om det bara var 2 eller 3 personer, blir det då enklare att bevisa? (Detta kan vara inspiration till ett bevis genom induktion)

Anta att första personen skakar sin hand $n_{1}$ gånger,andra $n_{2}$ gånger,tredje $n_{3}$ ,fjärde $n_{4}$ ,femte $n_{5}$ ,men den sjätte personen ska skaka sin hand $n_{1} g å n g e r e l l e r n_{2} g å n g e r e l l e r n_{3} g å n g e r e l l e r n_{4} g å n g e r e l l e r n_{5} g å n g e r$ eftersom han skakar sin hand med någon av de fem första personer.

Så att minst två personer skakar hand samma gånger.

På mötet finns $n$ personer.

Det går att skaka hand med $0, 1, \cdots, n-1$ personer. Detta är $n$ stycken olika alternativ. Men, det gäller att om en person skakar hand med alla (n-1 gånger) så kan det inte finnas någon som skakar hand med 0 personer. Det gör att alternativen $0$ och $n-1$ inte kan förekomma samtidigt. Alltså har vi $n-1$ stycken möjliga antal handskakningar, och $n$ stycken personer.

Vad säger lådprincipen?

Svara

Visa senaste svar