Zasada szufladkowa

[hutsaloviaheslav1998]

Zadanie z matematyki dyskretnej dotyczące zasady szufladkowej

Przy okrągłym stole znajduje się 100 miejsc oznaczonych winietkami z nazwiskami stu gości. Goście usiedli przy stole w sposób zupełnie losowy, w taki sposób, że nikt nie usiadł na przypisanym mu miejscu. Pokaż,że możliwe jest obrócenie okrągłego stołu w taki sposób, aby co najmniej dwoje gości siedziało przy swojej winietce

.

[Jerry]

Przyjmijmy, że \(r_i\) jest różnicą pomiędzy pozycją \(i\)-tej osoby przy stole a pozycją winietki tej osoby na stole (licząc w orientacji dodatniej). Skoro nikt nie siedzi na swoim miejscu, to \(r_i\in\{1,2,3,\ldots, 99\}\) . Ponieważ możliwości różnic jest \(99\) a osób \(100\), to istnieją co najmniej dwie osoby, \(k\)-ta i \(n\)-ta takie, że \(r_k=r_n\). Wystarczy wtedy obrócić stół o \(r_k\) pozycji w orientacji ujemnej i będą te osoby siedziały przy swoich winietkach.

Pozdrawiam

[hutsaloviaheslav1998]

A przepraszam. Mam jeszcze jedno pytanie. Dlaczego jest \(r_{i} \in \left\{1,2,....,99 \right\} \), skoro wszystkich jest 100. Chodzi o różnice osób w stosunku do zajmowanych miejsc, czy o co?

[Jerry]

... Dlaczego jest \(r_{i} \in \left\{1,2,....,99 \right\} \), skoro wszystkich jest 100. ...

Gdyby \(r_i=100\), to znaczyłoby, że \(i\)-ta osoba siedzi przy swojej winietce, a to treść zadania wyklucza.

Pozdrawiam

[hutsaloviaheslav1998]

... Dlaczego jest \(r_{i} \in \left\{1,2,....,99 \right\} \), skoro wszystkich jest 100. ...

Gdyby \(r_i=100\), to znaczyłoby, że \(i\)-ta osoba siedzi przy swojej winietce, a to treść zadania wyklucza.

Pozdrawiam

Przepraszam, ale chciałbym dopytać o jeszcze jedną rzecz w związku z tym \(r_{i} \in \left\{1,2,....,99 \right\} \). Czyli jeżeli od 1 do 99 tzn. że jednej osobie już przyporządkowano winiete z odpowiednim nazwiskiem skoro tych osób i winiet jest 100.

[Jerry]

Nie masz za co przepraszać!

... chciałbym dopytać o jeszcze jedną rzecz w związku z tym \(r_{i} \in \left\{1,2,....,99 \right\} \). Czyli jeżeli od 1 do 99 tzn. że jednej osobie już przyporządkowano winiete z odpowiednim nazwiskiem skoro tych osób i winiet jest 100.

Nie! Oznacza to, że co najmniej dwóm osobom przyporządkowana jest ta sama różnica i możliwy jest żądany treścią zadania obrót!

Pozdrawiam
PS. Przeczytaj, proszę, jeszcze raz zasadę szufladkową Dirichleta (w wersji przyjaznej):

Jeżeli \(m\) przedmiotów włoży się do \(n\) różnych szufladek, gdzie \(m > n > 0\) , to w co najmniej jednej szufladce znajdą się co najmniej dwa przedmioty.

i rozwiązanie elementarnego zadania

Wykaż, że wśród jedenastu liczb naturalnych (zapisanych w systemie decymalnym) jest para takich, których różnica jest podzielna przez \(10\).

Rozpatrzmy cyfry jedności tych liczb. Ponieważ cyfr jest \(10\), a liczb \(11\), to istnieją co najmniej dwie liczby o takiej samej cyfrze jedności - to różnica ma w rzędzie jedności \(0\), zatem jest podzielna przez \(10\)