szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 13 lut 2018, o 15:15 
Użytkownik

Posty: 15
Lokalizacja: Poznań
Dana jest tablica 15 \times 15 mająca 15 \times 15 pól. Każde pole malujemy na niebiesko, zielono, czerwono. Pokaż, że jakkolwiek byśmy nie pomalowali tablicę, zawsze znajdą się dwa rzędy o takiej samej liczbie pól w którymś kolorze.

Intuicja podpowiada mi, że trzeba skorzystać z zasady szufladkowej Dirichleta.
Czym zatem będą te "szufladki" w tym zadaniu?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2018, o 16:59 
Użytkownik
Avatar użytkownika

Posty: 6328
Pól w jednym kolorze morze być w rzędzie od 0 do 15.
Załóżmy że w każdym rzędzie jest inna liczba pól tego samego koloru. Czyli dla danego koloru liczba pól szachownicy nim pomalowanych waha się od \frac{(0+14) \cdot 15}{2} do \frac{(1+15) \cdot 15}{2}. Dla trzech kolorów suma pól szachownicy nimi pomalowanych jest nie mniejsza od 3 \cdot \frac{(0+14) \cdot 15}{2} =3 \cdot 7 \cdot 15=21 \cdot 15 co jest większe od liczby pól na szachownicy.
Jaki stąd wniosek?
Góra
Mężczyzna Offline
PostNapisane: 14 lut 2018, o 19:21 
Użytkownik

Posty: 15
Lokalizacja: Poznań
Że zgodnie z zasadą szufladkową Dirichleta, znajdą się dwa rzędy o takiej samie liczbie pól w danym kolorze. (Nie można skonstruować 15 sum , aby kżada liczba (w naszym przypadku kolor) nie powtórzyła się między tymi sumami).
Góra
Mężczyzna Offline
PostNapisane: 15 lut 2018, o 12:32 
Użytkownik
Avatar użytkownika

Posty: 6328
Wręcz przeciwnie. Pól jest na tyle mało, że pewnie można nimi pomalować szachownicę.
Przykład takiego pomalowania:
Ukryta treść:    



Przypuszczam jednak, że rzędy w treści zadania należy interpretować nie jako zwykłe rzędy (poziome), lecz wszystkie możliwe - czyli zarówno rzędy (rzędy poziome), jak i kolumny (rzędy pionowe).
Wtedy w powyższym przykładzie mam np: cztery czerwone pola zarówno w 12 rzędzie poziomym, jak i w 12 rzędzie pionowym.
Przy takiej interpretacji także można wykorzystać rozumowanie z poprzedniego postu. Maksymalna ilość różnych liczb pól w tym samym kolorze to: \frac{(1+15)15}{2}=8 \cdot 15. Dla trzech kolorów daje to 3 \cdot  \frac{(1+15)15}{2}=24 \cdot 15 , co jest zdecydowanie mniejsze od ilości pól jakie muszą one pokryć, czyli 2 \cdot 15^2=30 \cdot 15 (tam jest dwójka gdyż pola są liczone rzędami poziomymi, oraz rzędami pionowymi). Wniosek : muszą istnieć powtarzające się liczby pól w tym samym kolorze, więc i rzędy w których one występują.
Góra
Mężczyzna Offline
PostNapisane: 15 lut 2018, o 13:00 
Użytkownik
Avatar użytkownika

Posty: 12433
Lokalizacja: czasem Warschau, czasem Breslau
kerajs, ale przecież ten przykład do treści w pierwotnym rozumieniu też jest zły (choć wtedy faktycznie teza by nie działała), bo wszędzie jest tyle samo zielonych pól, czyli zero. Sorry za czepialstwo.
Góra
Mężczyzna Offline
PostNapisane: 15 lut 2018, o 20:35 
Użytkownik
Avatar użytkownika

Posty: 6328
Bardzo dobrze, że się czepiasz. Nie pomyślałem o takiej interpretacji, gdyż dla mnie nienaturalnym jest zliczanie niepomalowanych pól.

Czyli w tej wersji rząd (zwykły, poziomy rząd) cały pomalowany na czerwono nie mam traktować jako 15 pól czerwonych, ale trójkę liczb: 0 zielonych, 0 niebieskich, 15 czerwonych.
Teraz każdy rząd zawiera 3 liczby, a cała szachownica ma ich 45. Biorąc najmniejsze możliwe zestawy 15 różnych liczb dostaje się 21 \cdot 15 pól co znacząco przekracza ilość pól tej szachownicy, więc są rzędy w których ilość pól w tym samym kolorze się powtórzy.
Teoretycznie największa ilość rzędów o niepowtarzającej się liczbie pól w którymkolwiek z kolorów to 10.

Przepraszam za zamieszanie. Jak widać, moim problemem nie jest rozwiązanie zadania, ale zrozumienie jego treści. Treść tego mnie przerosła.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 kolorowanie grafu dwudzielnego  flashion  0
 Kolorowanie prostokąta - ilość różnych sposobów  marek252  0
 metoda wlaczen i wylaczen, kolorowanie grafu,drzewo binarne  anna_y  0
 kolorowanie totalne  Nesquik  0
 Graf skierowany, kolorowanie  KUOPA  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl