Kółko 20 XII 2004 - kilka zadanek z kombinatoryki

1. W pewnym kraju jest skończona liczba miast, które poł _{}aczono sieci _{}a dróg jednokierunkowych. Wiadomo, że każde dwa miasta ł _{}aczy pewna droga jednokierunkowa. Wykazać, że istnieje miasto, z którego można odbyć podróż do każdego innego miasta.

2. Niech n i k b_{}ed _{}a liczbami całkowitymi dodatnimi. Danych jest nk przedmiotów (tych samych rozmiarów) i k pudełek, z których każde pomieści n przedmiotów. Każdy przedmiot jest pokolorowany jednym z k różnych kolorów. Wykazać, że można rozmieścić te przedmioty w pudełkach w taki sposób, że w każdym pudełku znajd _{}a si_{}e przedmioty w co najwyżej dwóch kolorach.

3. Na nieskończonej szachownicy dwaj gracze na przemian wpisuj _{}a na wolne jeszcze pola po jednym znaku. Jeden gracz używa znaku ×, a drugi znaku ∘. Na pocz _{}atku gry szachownica jest pusta. Wygrywa ten, kto pierwszy zapełni swoimi znakami jakiś kwadrat o wymiarach 2 × 2. Czy gracz rozpoczynaj _{}acy rozgrywk_{}e może zapewnić sobie zwyci_{}estwo?

4. Mamy do dyspozycji 1999 monet, z których każde dwie maj _{}a różny ci_{}eżar. Dysponujemy urz _{}adzeniem, które pozwala spośród dowolnych trzech monet wskazać t_{}e, której ci_{}eżar zawiera si_{}e pomi_{}edzy ci_{}eżarami dwóch pozostałych. Dowieść, że moneta tysi_{}eczna pod wzgl_{}edem ci_{}eżaru może być wyznaczona przez nasze urz _{}adzenie stosowane nie wi_{}ecej niż 1000000 razy. Udowodnić, że za pomoc _{}a tego urz _{}adzenia miejsce w ci _{}agu ci_{}eżarów można wyznaczyć tylko dla tej monety.

5. Liczby 1, 2, …, 49 rozmieszczono w tablicy 7×7, po czym obliczono sum_{}e liczb w każdym wierszu i każdej kolumnie. Niektóre z tych 14 sum s _{}a nieparzyste, a pozostałe s _{}a parzyste. Niech A oznacza sum_{}e wszystkich nieparzystych sum, a B sum_{}e wszystkich parzystych sum. Czy jest możliwe takie rozmieszczenie liczb, że A = B?

6. Czy można wybrać na płaszczyźnie n < 1000 punktów w ten sposób, by istniało co najmniej 6×n różnych par punktów, pomi_{}edzy którymi jest taka sama odległość? oł. (Wszystko b_{}edzie narysowane na tablicy)