[MIX][Kombinatoryka] mix (15) (tylko dla malarzy)
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
- mol_ksiazkowy
- Użytkownik
- Posty: 11590
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3167 razy
- Pomógł: 750 razy
[MIX][Kombinatoryka] mix (15) (tylko dla malarzy)
1. Dany jest na płaszczyźnie pewien skończony zbiór X punktów kratowych. Czy mozna pokolorować pewne punkty tego zbioru na czerwono, a pozostałe na zielono, tak aby dla dowolnej prostej L równoległej do jednej z osi ox badz oy, bezwzględna wartość różnicy pomiędzy liczbą punktów czerwonych i zielonych leżacych na L jest nie większa od 1 ? Odpowiedz swą uzsadnij
2. Na każdym polu szachownicy namalowano losowo liczby od 1 do 32, przy czym każda z tych liczb, występuje na dwóch polach. Udowodnij że można wybrać 32 pola pomalowane kolejnymi liczbami naturalnymi w taki sposób by w każdej kolumnie znalzało się przynajmniej jedno z wybranych pól.
3. Każda liczbę naturalną pomalowano na jeden z dwóch kolorów. Dowieść, że dla każdej liczby naturalnej \(\displaystyle{ n}\) istnieją różne liczby naturalne \(\displaystyle{ a,b >n}\) t. ze liczby \(\displaystyle{ a, b}\) i \(\displaystyle{ a+b}\) są jednego koloru. *. Czy mozna wskazać pokolorownie zbioru \(\displaystyle{ N}\) trzema kolorami, tak aby teza jak wyzej nie zachodziła?!
4. Każda krawędź wielościanu wypukłego została pomalowana jednym z dwóch kolorów. Udowodnić, ze istnieje wierzchołek A oraz płaszczyzna przechodząca przez A i niezawierająca innych wierzchołków wieloscianu, o tej własnosci, że po każdej jej stronie wszystkie krawędzie wychodzące z A mają jednakowy kolor.
5. Na polach szachownicy n x n rozmieszczono \(\displaystyle{ n^2}\) różnych liczb całkowitych, po jednej na każdym polu. W każdej kolumnie pole z największą liczbą pomalowano na czerwono. Zbiór \(\displaystyle{ n}\) pól szachownicy nazwiemy dopuszczalnym, jeżeli żadne dwa z tych pól nie znajdują się w tym samym wierszu ani w tej samej kolumnie. Spośród wszystkich zbiorów dopuszczalnych wybrano zbiór, dla którego suma liczb umieszczonych na jego polach jest największa. Wykazać, że w tak wybranym zbiorze jest pole czerwone.
6. Każdy punkt okręgu jest pomalowany jednym z trzech kolorów. Dowieść, że pewne trzy punkty jednego koloru są wierzchołkami trójkąta równoramiennego.
7. Pewne pola na szachownicy zamalowano tak, że król nie może przejść od lewego do prawego jej brzegu po polach zamalowanych. Udowodnić, że po nie zamalowanych polach może od dolnego do górnego brzegu szachownicy przejść wieża.
8. Każde pole szachownicy n x n pomalowano na czarno lub biało. Okazało się, ze żadne cztery pola, których środki są wierzchołkami prostokąta o bokach równoległych do krawędzi szachownicy, nie zostały pomalowane tym samym kolorem. Dla jakiej największej wartości n jest to możliwe?
9. Pokratkowana płaszczyzna jest na początku cała pokolorowana na biało. Dozwolone jest wielokrotne wykonywanie takiej operacji: zmiana koloru na przeciwny wszystkich pól należących do kwadratu 3 x 3 lub 4 x 4. Czy za pomocą tych operacji mozna zaczernić klatki pewnego kwadratu 2 x 2 i nie zmienić koloru pozostałych klatek?!
10. Dzielimy płaszczyznę na skończona liczbę regionów rysując w dowolny sposób pewną skończona ilość prostych. Wykazac ze regiony te moga byc pomalowane dwoma kolorami. Regiony które stykają sie tylko w jednym punkcie lub sa rozłaczne moga miec ten sam kolor.
11. Każda liczbe \(\displaystyle{ j \in \{1, ...,326 \}}\) pomalowano jednym z pięciu kolorów: białym, czarnym, żółtym, zielonym, czerwonym. Wykaz ze istnieja takie \(\displaystyle{ i,j,k \ , i \neq j \ i \neq k}\) pomalowane tym samym kolorem i takie ze \(\displaystyle{ i=j+k}\).
12. Kazdy punkt w przestrzeni jest pokolorowany na niebiesko badz na czerowno. Dowiesc, ze istnieje przynajmniej jeden kwadrat o boku długosci 1, i z liczba wiezrchołków niebieskichvrówna 0, 1 lub 4.
13.Dane są względnie pierwsze liczby \(\displaystyle{ n , k}\) t ze \(\displaystyle{ 0<k<n}\). Każdą liczb zbioru \(\displaystyle{ M=\{1,2,...n-1 \}}\) maluje się na niebiesko, albo na biało w ten sposób, że:
a) dla każdego \(\displaystyle{ i}\) ze zbioru M liczby \(\displaystyle{ i}\) oraz \(\displaystyle{ n-i}\) maluje się tym samym kolorem
b) dla każdego \(\displaystyle{ i}\) ze zbioru M różnego od \(\displaystyle{ k}\), liczby \(\displaystyle{ i}\) oraz \(\displaystyle{ |k-i|}\) maluje się tym samym kolorem.
Udowodnić, ze wszystkie liczby ze zbioru M zostaną pomalowane tym samym kolorem.
Uwaga: wszelkie kolorowe rysunki bardzo mile widziane!
no i ""do pedzli"! Powodzenia
2. Na każdym polu szachownicy namalowano losowo liczby od 1 do 32, przy czym każda z tych liczb, występuje na dwóch polach. Udowodnij że można wybrać 32 pola pomalowane kolejnymi liczbami naturalnymi w taki sposób by w każdej kolumnie znalzało się przynajmniej jedno z wybranych pól.
3. Każda liczbę naturalną pomalowano na jeden z dwóch kolorów. Dowieść, że dla każdej liczby naturalnej \(\displaystyle{ n}\) istnieją różne liczby naturalne \(\displaystyle{ a,b >n}\) t. ze liczby \(\displaystyle{ a, b}\) i \(\displaystyle{ a+b}\) są jednego koloru. *. Czy mozna wskazać pokolorownie zbioru \(\displaystyle{ N}\) trzema kolorami, tak aby teza jak wyzej nie zachodziła?!
4. Każda krawędź wielościanu wypukłego została pomalowana jednym z dwóch kolorów. Udowodnić, ze istnieje wierzchołek A oraz płaszczyzna przechodząca przez A i niezawierająca innych wierzchołków wieloscianu, o tej własnosci, że po każdej jej stronie wszystkie krawędzie wychodzące z A mają jednakowy kolor.
5. Na polach szachownicy n x n rozmieszczono \(\displaystyle{ n^2}\) różnych liczb całkowitych, po jednej na każdym polu. W każdej kolumnie pole z największą liczbą pomalowano na czerwono. Zbiór \(\displaystyle{ n}\) pól szachownicy nazwiemy dopuszczalnym, jeżeli żadne dwa z tych pól nie znajdują się w tym samym wierszu ani w tej samej kolumnie. Spośród wszystkich zbiorów dopuszczalnych wybrano zbiór, dla którego suma liczb umieszczonych na jego polach jest największa. Wykazać, że w tak wybranym zbiorze jest pole czerwone.
6. Każdy punkt okręgu jest pomalowany jednym z trzech kolorów. Dowieść, że pewne trzy punkty jednego koloru są wierzchołkami trójkąta równoramiennego.
7. Pewne pola na szachownicy zamalowano tak, że król nie może przejść od lewego do prawego jej brzegu po polach zamalowanych. Udowodnić, że po nie zamalowanych polach może od dolnego do górnego brzegu szachownicy przejść wieża.
8. Każde pole szachownicy n x n pomalowano na czarno lub biało. Okazało się, ze żadne cztery pola, których środki są wierzchołkami prostokąta o bokach równoległych do krawędzi szachownicy, nie zostały pomalowane tym samym kolorem. Dla jakiej największej wartości n jest to możliwe?
9. Pokratkowana płaszczyzna jest na początku cała pokolorowana na biało. Dozwolone jest wielokrotne wykonywanie takiej operacji: zmiana koloru na przeciwny wszystkich pól należących do kwadratu 3 x 3 lub 4 x 4. Czy za pomocą tych operacji mozna zaczernić klatki pewnego kwadratu 2 x 2 i nie zmienić koloru pozostałych klatek?!
10. Dzielimy płaszczyznę na skończona liczbę regionów rysując w dowolny sposób pewną skończona ilość prostych. Wykazac ze regiony te moga byc pomalowane dwoma kolorami. Regiony które stykają sie tylko w jednym punkcie lub sa rozłaczne moga miec ten sam kolor.
11. Każda liczbe \(\displaystyle{ j \in \{1, ...,326 \}}\) pomalowano jednym z pięciu kolorów: białym, czarnym, żółtym, zielonym, czerwonym. Wykaz ze istnieja takie \(\displaystyle{ i,j,k \ , i \neq j \ i \neq k}\) pomalowane tym samym kolorem i takie ze \(\displaystyle{ i=j+k}\).
12. Kazdy punkt w przestrzeni jest pokolorowany na niebiesko badz na czerowno. Dowiesc, ze istnieje przynajmniej jeden kwadrat o boku długosci 1, i z liczba wiezrchołków niebieskichvrówna 0, 1 lub 4.
13.Dane są względnie pierwsze liczby \(\displaystyle{ n , k}\) t ze \(\displaystyle{ 0<k<n}\). Każdą liczb zbioru \(\displaystyle{ M=\{1,2,...n-1 \}}\) maluje się na niebiesko, albo na biało w ten sposób, że:
a) dla każdego \(\displaystyle{ i}\) ze zbioru M liczby \(\displaystyle{ i}\) oraz \(\displaystyle{ n-i}\) maluje się tym samym kolorem
b) dla każdego \(\displaystyle{ i}\) ze zbioru M różnego od \(\displaystyle{ k}\), liczby \(\displaystyle{ i}\) oraz \(\displaystyle{ |k-i|}\) maluje się tym samym kolorem.
Udowodnić, ze wszystkie liczby ze zbioru M zostaną pomalowane tym samym kolorem.
Uwaga: wszelkie kolorowe rysunki bardzo mile widziane!
no i ""do pedzli"! Powodzenia
Ostatnio zmieniony 14 lut 2017, o 23:32 przez Jan Kraszewski, łącznie zmieniany 3 razy.
Powód: Poprawa tematu.
Powód: Poprawa tematu.
- limes123
- Użytkownik
- Posty: 666
- Rejestracja: 21 sty 2008, o 22:48
- Płeć: Mężczyzna
- Lokalizacja: Ustroń
- Podziękował: 26 razy
- Pomógł: 93 razy
[MIX][Kombinatoryka] mix (15) (tylko dla malarzy)
7. Rozwiązanie bardzo intuicyjne. Koloruję wszystkie pola szachownicy i sprawdzam, w którym momencie król nie będzie w stanie dotrzeć z lewego na prawy brzeg. Dopóki istnieje droga połączonych se sobą wierchołkami lub bokami pól zamalowanych, król może przejść, czyli warunkeim koniecznym jest to, aby w pewnym momencie była ciągła przerwa z góry na dół pól niezamalowanych, i po tych polach może przejechać wieża. Nie umiem tego jakoś ładnie zapisać, może ktoś inny będzie w stanie. A tak w ogóle to ciekawy mix
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
[MIX][Kombinatoryka] mix (15) (tylko dla malarzy)
zad. 3. kolory:biały, czarny
jeśli zbiór liczb pomalowanych na pewien kolor jest skończony to teza zachodzi. jeżeli oba zbiory są nieskończone, to:
załóżmy że kolor czarny nie spełnia warunków zadania. weźmy liczby \(\displaystyle{ a,b,c,d>n}\) pomalowane na czarno. wtedy liczby \(\displaystyle{ a+b,a+c,a+d,b+c,b+d,c+d}\) są białe. Załóżmy teraz wbrew tezie że kolor biały też nie sełnia warunków zadania. wobec tego liczba \(\displaystyle{ a+b+c+d}\) jest czarna. Odwracając tezę zadania z istnienia sumy na istnienie różnicy (co na jedno wychodzi) otrzymujemy że liczby \(\displaystyle{ a+b+c,a+b+d,a+c+d,b+c+d}\) są białe. wobec tego np. liczba \(\displaystyle{ 2a+b+c+d}\) musi być z jednej strony biała (\(\displaystyle{ =(a+b+c+d)+a}\)) a z drugiej strony czarna (\(\displaystyle{ =(a+b+c)+(a+d)}\)) - sprzeczność
[ Dodano: 17 Sierpnia 2008, 16:22 ]
limes123, może być jeszcze inna przerwa- dwie styczne przekątne, ale po nich wieża też oczywiście przejdzie
jeśli zbiór liczb pomalowanych na pewien kolor jest skończony to teza zachodzi. jeżeli oba zbiory są nieskończone, to:
załóżmy że kolor czarny nie spełnia warunków zadania. weźmy liczby \(\displaystyle{ a,b,c,d>n}\) pomalowane na czarno. wtedy liczby \(\displaystyle{ a+b,a+c,a+d,b+c,b+d,c+d}\) są białe. Załóżmy teraz wbrew tezie że kolor biały też nie sełnia warunków zadania. wobec tego liczba \(\displaystyle{ a+b+c+d}\) jest czarna. Odwracając tezę zadania z istnienia sumy na istnienie różnicy (co na jedno wychodzi) otrzymujemy że liczby \(\displaystyle{ a+b+c,a+b+d,a+c+d,b+c+d}\) są białe. wobec tego np. liczba \(\displaystyle{ 2a+b+c+d}\) musi być z jednej strony biała (\(\displaystyle{ =(a+b+c+d)+a}\)) a z drugiej strony czarna (\(\displaystyle{ =(a+b+c)+(a+d)}\)) - sprzeczność
[ Dodano: 17 Sierpnia 2008, 16:22 ]
limes123, może być jeszcze inna przerwa- dwie styczne przekątne, ale po nich wieża też oczywiście przejdzie
- mol_ksiazkowy
- Użytkownik
- Posty: 11590
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3167 razy
- Pomógł: 750 razy
[MIX][Kombinatoryka] mix (15) (tylko dla malarzy)
ad 12 Załozmy ze nie istnieje kwadrat jednostkowy z czterema wierzchołkami niebieskimi. Nalezy wtedy pokazac, ze wtedy istnieje kwadrat jednostkowy z trzema badz czterema wierzchołkami czerwonymi. Wezmy punkt P czerwony. A skoro sfera o srodku P i promieniu \(\displaystyle{ \sqrt{2}}\) nie moze byc cała niebieska (załozenie) - istnieje na niej Q czerwony. tj PQ=\(\displaystyle{ \sqrt{2}}\) Wezmy ośmioscian foremny PABCDQ o krawedzi 1. Kwadrat ABCD ma co najmniej jeden wierzcholek czerony, np A. Tak wiec kwadrat APCQ ma co najmniej trzy wierzchołki czerwone. ckd
firmowka, olimpijskie z 1987 r
Ps co do zad 3 , jest ono szczegolnie ciekawe, moze wartałoby cos sobie narysowac...
firmowka, olimpijskie z 1987 r
Ps co do zad 3 , jest ono szczegolnie ciekawe, moze wartałoby cos sobie narysowac...
- limes123
- Użytkownik
- Posty: 666
- Rejestracja: 21 sty 2008, o 22:48
- Płeć: Mężczyzna
- Lokalizacja: Ustroń
- Podziękował: 26 razy
- Pomógł: 93 razy
[MIX][Kombinatoryka] mix (15) (tylko dla malarzy)
6. Wystarczy rozważyć 13-kąt foremny. Z Dirichleta mamy, że co najmniej 5 pkt będzie jednego koloru, i tu już zostaje tylko rozpatrzenie przypadków i w każdym otrzymamy, że nie da się tak wybrać 5 pkt w 13-kącie foremnym, żeby nie otrzymać trójkąta równoramiennego.
[Edit]
Jest też mądre twierdzenie (nie pamiętam kogo), dzięki któremu można uogólnić to na dowolną liczbę kolorów
[Edit2]
Chodziło o twierdzenie van der Waerdena.
[Edit]
Jest też mądre twierdzenie (nie pamiętam kogo), dzięki któremu można uogólnić to na dowolną liczbę kolorów
[Edit2]
Chodziło o twierdzenie van der Waerdena.
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
[MIX][Kombinatoryka] mix (15) (tylko dla malarzy)
zad. 8.
dla n=4 istnieje takie pokolorowanie: kolorujemy na czarno pola A3,A4,B1,B2,B4,C2,C3,D1,D4
udowodnie ze dla \(\displaystyle{ n \ge 5}\) nie mozna w postulowany sposob pokolorowac pol. niech f(x) oznacza sufit z liczby x. rozwazmy pierwszy wiersz tablicy. mozemy zalozyc ze znajduje sie w nim \(\displaystyle{ f( \frac{n}{2})}\) pol czarnych. mozemy tez zalozyc ze leza one w poczatkowych kolumnach bo przemieszanie kolumn nie zmienia warunkow zadania. rozwazmy pozostale n-1 wierszy. jesli w ktoryms z nich w tych poczatkowych kolumnach sa 2 czarne pola to mamy teze. jesli jest caly bialy wiersz (w tym fragmencie) to poniewaz \(\displaystyle{ f( \frac{n}{2}) \ge 3}\) wiec znajdziemy wsrod pozostalych wierszy taki w ktorym (w rozpatrywanym fragmencie) sa 2 pola tego samego koloru i jest ok. pozostal przypadek w ktorym w kazdym z pozostalych fragmentow wierszy jest jedno czarne pole. \(\displaystyle{ f( \frac{n}{2})<n-1}\) z ZSD mamy 2 identyczne skad istnieje prostokat o bialych wierzcholkach ckd
dla n=4 istnieje takie pokolorowanie: kolorujemy na czarno pola A3,A4,B1,B2,B4,C2,C3,D1,D4
udowodnie ze dla \(\displaystyle{ n \ge 5}\) nie mozna w postulowany sposob pokolorowac pol. niech f(x) oznacza sufit z liczby x. rozwazmy pierwszy wiersz tablicy. mozemy zalozyc ze znajduje sie w nim \(\displaystyle{ f( \frac{n}{2})}\) pol czarnych. mozemy tez zalozyc ze leza one w poczatkowych kolumnach bo przemieszanie kolumn nie zmienia warunkow zadania. rozwazmy pozostale n-1 wierszy. jesli w ktoryms z nich w tych poczatkowych kolumnach sa 2 czarne pola to mamy teze. jesli jest caly bialy wiersz (w tym fragmencie) to poniewaz \(\displaystyle{ f( \frac{n}{2}) \ge 3}\) wiec znajdziemy wsrod pozostalych wierszy taki w ktorym (w rozpatrywanym fragmencie) sa 2 pola tego samego koloru i jest ok. pozostal przypadek w ktorym w kazdym z pozostalych fragmentow wierszy jest jedno czarne pole. \(\displaystyle{ f( \frac{n}{2})<n-1}\) z ZSD mamy 2 identyczne skad istnieje prostokat o bialych wierzcholkach ckd
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
[MIX][Kombinatoryka] mix (15) (tylko dla malarzy)
[rzeczywiscie, juz to kasuje]
Ostatnio zmieniony 1 lut 2009, o 20:31 przez Dumel, łącznie zmieniany 1 raz.
- Swistak
- Użytkownik
- Posty: 1874
- Rejestracja: 30 wrz 2007, o 22:04
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 99 razy
- Pomógł: 87 razy
[MIX][Kombinatoryka] mix (15) (tylko dla malarzy)
O ile się nie mylę, to zadanie 5 było kiedyś na Festiwalu Naukowym . Zajęcia prowadził pan Waldemar Pompe i było danych kilka zadań i jeżeli ktoś któreś zrobił, to było ono sukcesywnie ścierna, a na jego miejsce wchodziło następne. Najaktywniejsi dostali nagrodyw postaci książek od Delty, która bodajże nazywała się "O hipotezach i twierdzeniach Delty". Ja poszedłem na te zajęcia z tatą i byłem chyba wtedy może w 4 albo 5 klasie pods. a wszyscy inni byli chyba co najmniej w liceum . Niektórzy poznajdowali taki pokolorowania dla 3 i 4, a potem pan podpowiadał jak udowodnić, że dla 5 się nie da i w pewnym momencie gdy do końca dowodu był potrzebny tylko oczywisty fakt, że gdy mamy 5 ustawień par pól, które można pokolorować biały-biały, biały-czarny, czarny-biały i czarny-czarny, to któreś musi się powtórzyć, ja się zgłosiłem, powiedziałem to i chyba bardziej za odwagę dostałem książkę .
Co do zadań może posiedzę nad nimi, bo lubię zadania "dla malarzy", ale obecnie siedzę w bilbiotece w szkole .
Co do zad. 9, to jego nawet 2 rozwiązania znajdują się w tym temacie: viewtopic.php?t=104158,25
Co do zadań może posiedzę nad nimi, bo lubię zadania "dla malarzy", ale obecnie siedzę w bilbiotece w szkole .
Co do zad. 9, to jego nawet 2 rozwiązania znajdują się w tym temacie: viewtopic.php?t=104158,25
- mol_ksiazkowy
- Użytkownik
- Posty: 11590
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3167 razy
- Pomógł: 750 razy
- mol_ksiazkowy
- Użytkownik
- Posty: 11590
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3167 razy
- Pomógł: 750 razy