Matematyka.pl

Ponieważ mamy \(\displaystyle{ 2008 \cdot 2009}\) kwadratów \(\displaystyle{ 2 \times 2}\), to możemy zaczernić nie więcej niż \(\displaystyle{ 2008 \cdot 2009}\) kwadracików, zatem nie zaczernimy całej tablicy, bo musielibyśmy zaczernić więcej kwadracików.

co do aktualnego zadania, to udało mi się udowodnić, że ciąg jest fajny wtedy i tylko wtedy, gdy po posortowaniu niemalejącym danego ciągu będzie dla każdego \(\displaystyle{ i=1, 2, ..., n}\)zachodzić \(\displaystyle{ a_i \le i}\), ale nie wiem jak policzyć takie ciągi, więc jeszcze się nie będę rozpisywał ;p.

niech liczbą ciągów k-el. będzie \(\displaystyle{ a_k}\). \(\displaystyle{ a_1=1}\) i aby dalej było ok niech \(\displaystyle{ a_0=1}\). załóżmy że ostatni koleś wjechał na \(\displaystyle{ k}\) - te miejsce. skoro wjechał na to miejsce i było ono jedyne wolne to chciał wjechać na jedno z pierwszych k miejsc. nie chce mi się tego tłumaczyć ale chyba każdy teraz widzi że \(\displaystyle{ a_n = \sum_{k=1}^{n}k {n-1 \choose k-1} \cdot a_{k-1}a_{n-k}}\)
po pierwszych kilku wartościach wychodzi na to że zapewne \(\displaystyle{ a_n=(n+1)^{n-1}}\) ale na razie nie udało mi się tego udowodnić.

Zauważmy, że jeżeli każdy biały kwadracik ma stać się czarny, to potrafimy mu przyporządkować kwadrat 2x2, w którym wcześniej były zamalowane na czarno 3 pozostałe kwadraciki, dzięki któremu on stał się czarny. Ale skoro białych kwadracików jest więcej niż \(\displaystyle{ 2008\cdot 2009}\), a kwadratów 2x2 jest dokładnie \(\displaystyle{ 2008\cdot 2009}\), to którymś dwóm kwadracikom został przyporządkowany ten sam kwadrat 2x2, a to niemożliwe.

Kierowców i miejsca parkingowe będziemy numerować od 0.
Skorzystamy z wniosku Świstaka:

Swistak pisze:co do aktualnego zadania, to udało mi się udowodnić, że ciąg jest fajny wtedy i tylko wtedy, gdy po posortowaniu niemalejącym danego ciągu będzie dla każdego \(\displaystyle{ i=1, 2, ..., n}\)zachodzić \(\displaystyle{ a_i \le i}\), ale nie wiem jak policzyć takie ciągi, więc jeszcze się nie będę rozpisywał ;p.

Dowód - łatwe ćwiczenie. Idźmy dalej. Pokażemy, że tych przyporządkowań jest \(\displaystyle{ (n+1)^{n-1}}\). Rozważmy w tym celu wszystkie n-elementowe ciągi o wyrazach ze zbioru \(\displaystyle{ \{0,1,\ldots,n\}}\). Zdefiniujmy na nich relację \(\displaystyle{ (a_1,\ldots,a_{n}) \sim (b_1,\ldots,b_{n}) \iff a_1-b_1 \equiv a_2-b_2 \equiv \ldots \equiv a_{n} - b_{n} (mod n+1)}\). Jest ona oczywiście równoważnościowa, a każda klasa równoważności ma n+1 elementów. Pokażemy, że każda klasa zawiera dokładnie jeden "ciąg parkujący". Weźmy więc dowolny ciąg rozważanego typu i dla każdego \(\displaystyle{ i \in \{0,1,\ldots,n\}}\) niech \(\displaystyle{ a_i}\) oznacza liczbę wystąpień liczby i w naszym ciągu. Oczywiście \(\displaystyle{ \sum_{0}^{n} a_i = n}\). Oznaczmy \(\displaystyle{ b_i = a_i - 1 + \frac{1}{n+1}}\). Mamy więc \(\displaystyle{ \sum_{0}^{n} b_i = 0}\). Zauważmy, że nasz ciąg jest ciągiem parkującym wtedy i tylko wtedy, gdy dla każdego j zachodzi \(\displaystyle{ b_0 + b_1 + \ldots b_j \geq 0}\) (gdyż nierówności te mówią nam, że \(\displaystyle{ a_{n+1}=0}\) oraz spełniony jest Warunek Świstaka). Dalej, zobaczmy, że każdemu ciągowi będącemu w relacji z naszym wybranym odpowiada ciąg \(\displaystyle{ (b'_i)}\) będący cyklicznym przesunięciem rozważanego \(\displaystyle{ (b_i)}\). Pozostaje więc pokazać, że istnieje dokładnie jedno przesunięcie cykliczne \(\displaystyle{ (b'_i)}\) ciągu \(\displaystyle{ (b_i)}\), które spełnia dla każdego j \(\displaystyle{ b'_0 + b'_1 + \ldots b'_j \geq 0}\). Aby to zobaczyć, można np. narysowac sobie wykres ciągu sum częściowych ciągu b_i i zobaczyć, że trzeba wziąć takie przesunięcie, aby "zacząć" od momentu, w którym \(\displaystyle{ b_0 + b_1 + \ldots b_j}\) jest najmniejsze - zauważając jeszcze, że nie ma dwóch takich miejsc, ponieważ wszystkie
\(\displaystyle{ b_0 + b_1 + \ldots b_j}\) mają różną część ułamkową.

Niech \(\displaystyle{ w_{i}, k_{i}}\) oznaczają liczbę wierszy i kolumn, w których występuje liczba i. Łatwo zauważyć, że skoro każda liczba występuje n razy, to musi zachodzić \(\displaystyle{ w_{i}+k_{i} \ge 2\sqrt{n}}\). Sumując to po wszystkich i mamy \(\displaystyle{ \sum_{i=1}^{n} w_{i} + \sum_{i=1}^{n} k_{i} \ge 2n\sqrt{n}}\) z czego wynika teza.

Nazwijmy warunkiem fakt , że w każdej grupie trzech ludzi ktoś musi kogoś znać.
Wpierw wykażemy, że w każdej grupie \(\displaystyle{ n}\) ludzi znajduje się trójkąt znajomych, tj grupa trzech ludzi, gdzie każdy zna każdego albo stół znajomych ,tj. grupa więcej niż trzech ludzi , których można usadowić przy stole, o którym mowa w zadaniu.

Weźmy piątkę dowolnych ludzi z grupy (można to zrobić, gdyż \(\displaystyle{ n \geqslant 5}\) ).
Oczywiście znajduje się tam para ludzi (nazwijmy ich \(\displaystyle{ A}\) i \(\displaystyle{ B}\)), którzy się znają.
Z pozostałej trójki można wybrać dwóch ludzi , którzy się nie znają (w przeciwnym razie trójkąt znajomych znajduje się w tej trójce. Nazwijmy tych dwóch ludzi \(\displaystyle{ C}\) i \(\displaystyle{ D}\). Rozważmy teraz trójki ludzi \(\displaystyle{ CAD}\) i \(\displaystyle{ CBD}\) , które muszą spełniać warunek :
- w trójce \(\displaystyle{ CAD}\) albo \(\displaystyle{ C}\) zna \(\displaystyle{ A}\) albo \(\displaystyle{ D}\) zna \(\displaystyle{ A}\) albo \(\displaystyle{ C}\) zna \(\displaystyle{ A}\) i \(\displaystyle{ D}\) zna \(\displaystyle{ A}\)
- w trójce \(\displaystyle{ CBD}\) (analogicznie , jak w trójce \(\displaystyle{ CAD}\) ) albo \(\displaystyle{ C}\) zna \(\displaystyle{ B}\) albo \(\displaystyle{ D}\) zna \(\displaystyle{ B}\) albo \(\displaystyle{ C}\) zna \(\displaystyle{ B}\) i \(\displaystyle{ D}\) zna \(\displaystyle{ B}\) .
Spośród wszystkich tych możliwości tylko dwie nie tworzą ani trójkąta znajomych , ani stołu znajomych. Są to:
- \(\displaystyle{ C}\) zna \(\displaystyle{ B}\) i nie zna \(\displaystyle{ A}\) oraz jednocześnie \(\displaystyle{ D}\) zna \(\displaystyle{ A}\) i nie zna \(\displaystyle{ B}\)
- \(\displaystyle{ C}\) zna \(\displaystyle{ A}\) i nie zna \(\displaystyle{ B}\) oraz jednocześnie \(\displaystyle{ D}\) zna \(\displaystyle{ B}\) i nie zna \(\displaystyle{ A}\) .
Widzimy jednak , że te możliwości są symetryczne , zatem możemy dalej rozpatrywać tylko jedną . Wybierzmy, np. drugą.
Został nam jeszcze w naszej początkowej piątce ludzi ostatni punkt, którego nie uwzględniliśmy. Nazwijmy go \(\displaystyle{ E}\) .
Rozważmy teraz trójki znajomych \(\displaystyle{ ECB}\) , \(\displaystyle{ ECD}\) i \(\displaystyle{ EAD}\) , które muszą spełniać warunek.
Widzimy , że \(\displaystyle{ E}\) musi znać spośród czwórki osób \(\displaystyle{ A}\) , \(\displaystyle{ B}\), \(\displaystyle{ C}\), \(\displaystyle{ D}\) przynajmniej dwie osoby , gdyż w przeciwnym razie , któraś z powyższych trójek nie spełnia warunku. Poniższy rysunek przedstawia wszystkie możliwości:
link : .
Widzimy , że w każdym przypadku powstanie trójkąt znajomych lub stół znajomych.
Oczywiście, gdy \(\displaystyle{ E}\) zna trzech lub czterech ludzi z \(\displaystyle{ A}\) , \(\displaystyle{ B}\) , \(\displaystyle{ C}\) , \(\displaystyle{ D}\) to również powstaną nam trójkąty znajomych bądź stoły znajomych , gdy wszystkie trójki będą spełniały warunek.
Pokazaliśmy zatem , jak w dowolnej grupie \(\displaystyle{ n}\) ludzi , usadowić przy stole minimum trzy osoby.
Teraz pokażemy, że z ludzi , którzy nie siedzą przy stole na początku imprezy można wybrać jeszcze tyle ludzi i zrobić im miejsca przy stole , że przy stole będzie siedziało minimum \(\displaystyle{ \frac{n}{2}}\) ludzi.

Otóż niech w danej chwili przy stole siedzi \(\displaystyle{ k}\) ludzi . Gdy \(\displaystyle{ k<n-k}\) to zawsze z ludzi , którzy nie siedzą przy stole można wybrać dwóch , którzy się nie znają ( w przeciwnym razie , wśród ludzi którzy nie siedzą przy stole każdy zna każdego , a że jest ich więcej niż \(\displaystyle{ \frac{n}{2}}\) zatem mogą oni stworzyć stół spełniający warunki zadania). \(\displaystyle{ (!)}\)
Nazwijmy tych dwóch ludzi \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) , zaś tych , co siedzą przy stole ponumerujmy przeciwnie do ruchu wskazówek zegara jako \(\displaystyle{ 1}\) , \(\displaystyle{ 2}\) , ... , \(\displaystyle{ K}\).
\(\displaystyle{ (*)}\)Rozważmy teraz \(\displaystyle{ k}\) trójek ludzi , które tworzą para \(\displaystyle{ X}\) , \(\displaystyle{ Y}\) po kolei z każdym człowiekiem przy stole. Trójki te muszą spełniać warunek.
Rozpatrzmy dwa przypadki:
1. \(\displaystyle{ k}\) jest nieparzyste
Oczywiście \(\displaystyle{ k=2p+1}\) dla pewnego \(\displaystyle{ p}\) . Z \(\displaystyle{ (*)}\) mamy , że któryś z ludzi \(\displaystyle{ X}\), \(\displaystyle{ Y}\) musi znać co najmniej \(\displaystyle{ p+1}\) ludzi siedzących przy stole . Oznacza to , że zna on dwóch ludzi , którzy siedzą koło siebie , zatem może zrobić sobie miejsce między nimi i siedzieć przy stole. Stół liczy teraz \(\displaystyle{ k+1}\) ludzi.
2. \(\displaystyle{ k}\) jest parzyste
\(\displaystyle{ k=2p}\). Z \(\displaystyle{ (*)}\) mamy, że któryś z ludzi \(\displaystyle{ X}\), \(\displaystyle{ Y}\) musi znać co najmniej \(\displaystyle{ p}\)ludzi siedzących przy stole. Gdy któryś zna więcej niż \(\displaystyle{ p}\) to sprawa wygląda , jak w punkcie 1. Zaś , gdy obydwaj znają dokładnie \(\displaystyle{ p}\) (\(\displaystyle{ k}\) trójek dalej spełnia warunek) sprawa się komplikuje.
Załóżmy , ze i \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) znają dokładnie \(\displaystyle{ p}\) ludzi siedzących . Gdy Któryś z nich zna jakichś dwóch ludzi siedzących koło siebie to nie ma problemu ze zrobieniem mu miejsca.
Załóżmy dodatkowo, że ani \(\displaystyle{ X}\) ani \(\displaystyle{ Y}\) nie znają dwójki ludzi siedzących obok siebie. Oznacza to , że któryś z nich zna wszystkich ludzi o numerach parzystych , zaś drugi o numerach nieparzystych. Niech , np. \(\displaystyle{ X}\) zna tych o numerach nieparzystych.
Zauważmy , że możemy utworzyć łamaną zamkniętą z ludzi kolejno : \(\displaystyle{ X}\) , \(\displaystyle{ 1}\) , \(\displaystyle{ 2p}\) , \(\displaystyle{ Y}\), \(\displaystyle{ 2}\) , \(\displaystyle{ 3}\) , \(\displaystyle{ 4}\), \(\displaystyle{ ...}\) , \(\displaystyle{ 2p-2}\), \(\displaystyle{ 2p-1}\) , \(\displaystyle{ X}\) ( \(\displaystyle{ X}\) został dwukrotnie napisany jako początek i koniec) . Zauważmy, że ta łamana zawiera \(\displaystyle{ k+2}\) ludzi , oraz , że można ludzi usadowić przy stole zgodnie z ich kolejnością w tej łamanej. Przy stole zasiada zatem w tym momencie \(\displaystyle{ k+2}\) ludzi.



Możemy powtarzać "robienie miejsc" tak długo, aż przy stole będzie siedziało przynajmniej \(\displaystyle{ \frac{n}{2}}\) ludzi ( patrz \(\displaystyle{ (!)}\)).

Koniec.