szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 gru 2015, o 00:58 
Użytkownik

Posty: 41
Lokalizacja: Brodnica
Czołem,
Nie wiem jak formalnie zapisywać udowodnienia do metody szufladkowej, poza tym czasami nie mam pojęcia jak się zabrać za zadanie.

1. Udowodnij, że wśród dowolnych n+1 liczb całkowitych będzie istniała para liczb różniących się o wielokrotność n

Mamy dane liczby a_0, a_1, ..., a_n
Tworzymy szufladki, które odzwierciedlają możliwe reszty z dzielenia przez n,
Otrzymujemy szufladki: 0, 1, ..., n-1
Rozważamy każdą parę: a_i-a_0, będzie n takich par
Więc mamy n par i n szuflad, więc różnica jednej pary musi dać n.

Jednak, nie jestem pewny czy dobrze zrozumiałem zadanie, bierzemy dowolne n+1 liczb całkowitych,
to czy możemy sobie wziąć np. 1,4,7,9, czy muszą być to kolejne liczby czyli 1,2,3,4,5. W pierwszym przypadku nie do końca to się zgadza.

2. Uzasadnij, że wśród dowolnych pięciu punktów należących do wnętrza kwadratu o boku 2 zawsze są dwa punkty odległe o nie więcej niż \sqrt{2}

3. Udowodnij, że wśród dowolnych n + 1 liczb całkowitych ze zbioru {1,2,...,2n} istnieje taka, która jest wielokrotnością innej.
Góra
Mężczyzna Offline
PostNapisane: 16 gru 2015, o 01:04 
Administrator

Posty: 23730
Lokalizacja: Wrocław
Ad 2 Podziel ten kwadrat na cztery kwadraty o boku 1.

JK
Góra
Mężczyzna Offline
PostNapisane: 16 gru 2015, o 08:54 
Użytkownik

Posty: 15823
Lokalizacja: Bydgoszcz
ad 1. Początek ok: teraz pomyśl ile masz liczb i ile masz szufladek. Co to oznacza (tu się uruchamia ZSD). Co możesz powiedzieć o różnicy dwóch liczb, które sa w tej samej szufladce?

Liczby oczywiście mogą byc dowolne, mogą sie też powtarzac.
Góra
Mężczyzna Offline
PostNapisane: 16 gru 2015, o 17:45 
Użytkownik
Avatar użytkownika

Posty: 3488
Lokalizacja: blisko
W trzecim zauważ, że każdą liczbę od jeden do 2n możesz zapisać w postaci:

2^k(2m+1), 0 \le m \le n-1,

i każdą z tych liczb wkładamy do szuflady o numerze m,

czyli dwie liczby znajdą się w jednej szufladzie:

znaczy że dla dwóch liczb 2m+1 będzie takie samo, czyli w praktyce mamy dwie liczby:


2^ir, oraz2^jr

a one są przez siebie podzielne!
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 zasada wlaczania i wylaczania - zadanie 2  BSD  1
 zasada szufladkowa ?  BSD  2
 liczby podzielne - zasada wlaczania i wylaczania  BSD  3
 3 zadania...  Ciapanek  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl