[Rozgrzewka OM][MIX][Kombinatoryka] Kombinatoryka

[binaj]

Żeby było do kompletu

Dana jest tablica \(\displaystyle{ 2009 \times 2010}\). Na początku więcej niż \(\displaystyle{ 2008 \times 2009}\) kwadracików jest białych, a reszta czarnych.
Jeśli w kwadracie \(\displaystyle{ 2 \times 2}\) trzy kwadraciki są czarne, to automatycznie zaczernia się czwarty. Udowodnić, że cała tablica nigdy nie będzie zaczerniona.

[KPR]

Ukryta treść:    

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.

Przy ulicy jednokierunkowej jest n miejsc parkingowych, na których staje n kierowców. Każdy z nich ma swoje ulubione miejsce. Jeśli jest wolne, to staje na nim. Jeżeli nie, to staje na najbliższym wolnym miejscu, które znajduje się dalej. Jeśli takowego nie ma, nie parkuje. Ile jest ciągów przyporządkowujących kolejnym kierowcom ulubione miejsca parkingowe takich, że każdy kierowca zaparkuje?

[XMaS11]

Nie wiem czy tamto rozwiązanie jest dobre, w każdym razie teza wynika z tego, że obwód figury utworzonej przez czarne pola nie rośnie.

[Swistak]

Rozwiązanie Kamila jest w pełni poprawne, jednak jest trochę kiepsko opisane (od 3 osób niezależnie usłyszałem, że go nie rozumieją i ja też na początku nie rozumiałem xp).

A taki se o wniosek:    

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.

[KPR]

Nie chciało mi się tego pisać Ale wystarczy, że jest poprawne.

[Dumel]

to Wojtku teraz mogę dać Ci okazję do popisania się swoimi zdolnościami dydaktycznymi i wytłumaczenia mi tamtego rozwiązania.

-- 29 listopada 2010, 21:11 --

część ostatniego zadania:

Ukryta treść:    

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ć.

[Swistak]

Zatem skoro taka wola ludu, to dokładniej wytłumaczę rozwiązanie Kamila.

Ukryta treść:    

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.

Swoją drogą, to rozwiązanie Filipa jest całkowicie złe ;p.

[limes123]

Mi się rozwiązanie Filipa podoba.
Pozdrawiam

[Swistak]

Będąc spowrotem na forum, może wyjaśnię, czemu rozwiązanie Filipa jest niepoprawne (widzę, że słowo "złe" zostało źle zinterpretowane ;p). Otóż obwód figury złożonej z czarnych pól istotnie nie rośnie, jednak dla zaczernionej tablicy wynosi on \(\displaystyle{ 2\cdot (2009 + 2010)}\), a czarnych pól na początku może być co najwyżej \(\displaystyle{ 2\cdot 2009 -1}\), a obwód takiej figury złożonej z tylu kwadracików sięga \(\displaystyle{ 8\cdot 2009 -8}\) co jest istotnie większe od obwodu całej zaczernionej tablicy. Zatem nie otrzymujemy żadnej sprzeczności analizując obwód.

[limes123]

Zle to chyba zrozumiales moja wypowiedz... Ale spoko;p

[Mama Jerza]

Przy ulicy jednokierunkowej jest n miejsc parkingowych, na których staje n kierowców. Każdy z nich ma swoje ulubione miejsce. Jeśli jest wolne, to staje na nim. Jeżeli nie, to staje na najbliższym wolnym miejscu, które znajduje się dalej. Jeśli takowego nie ma, nie parkuje. Ile jest ciągów przyporządkowujących kolejnym kierowcom ulubione miejsca parkingowe takich, że każdy kierowca zaparkuje?

bez kitu:    

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

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ą.

Mam nadzieję, że w miarę zrozumiale.

Jeśli uznacie że poprawnie to rozwiązałam, oto następne zadanko:

W kwadratową tablicę o rozmiarach \(\displaystyle{ n \times n}\) wpisano n-krotnie każdą z liczb \(\displaystyle{ 1, 2, \ldots , n}\). Pokazać, że w pewnym wierszu lub kolumnie
znajduje się co najmniej \(\displaystyle{ \sqrt{n}}\) różnych liczb.

Buziaki :*

[Dumel]

proponuję aby ktoś zarzucił innym zadaniem bo to jest proste i do tego już z milion razy się na forum pojawiało.

a tak poza tym to bardzo fajne rozwiązanko-- 14 grudnia 2010, 09:25 --alternatywny dowód ostatniego zadania: ... 2&t=382077

[Tata Jerza]

Kobieto, leć mi piwo przynieś, a nie jakieś zadania rozwiązujesz!

Ukryta treść:    

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.

Nowe zadanie: Na przyjęciu spotkało się \(\displaystyle{ n \ge 5}\) osób .Wiadomo, że wśród dowolnych trzech osób pewne dwie znają się. Dowieść, że spośród uczestników przyjęcia można wybrać nie mniej niż \(\displaystyle{ \frac{n}{2}}\) osób i posadzić przy okrągłym stole tak, aby każdy siedział między dwoma swoimi znajomymi.

[Brycho]

Ludzie, błagam, dajcie mi 2 godziny. Mam już dowód tego zadania od Taty Jerza , ale jestem chory i muszę do lekarza iść za 5 minut.-- 16 gru 2010, o 15:04 --

Na przyjęciu spotkało się \(\displaystyle{ n \ge 5}\) osób .Wiadomo, że wśród dowolnych trzech osób pewne dwie znają się. Dowieść, że spośród uczestników przyjęcia można wybrać nie mniej niż \(\displaystyle{ \frac{n}{2}}\) osób i posadzić przy okrągłym stole tak, aby każdy siedział między dwoma swoimi znajomymi.

Oto dowód.

Ukryta treść:    

Nazwijmy warunkiem fakt , że w każdej grupie trzech ludzi ktoś musi kogoś znać.

Początek imprezy

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.

"Robienie miejsc"

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.

Nowe: W konkursie bierze udział \(\displaystyle{ a}\) zawodników, ocenianych przez \(\displaystyle{ b}\) egzaminatorów , gdzie \(\displaystyle{ b \geqslant 3}\) jest liczbą całkowitą i nieparzystą. Każdy egzaminator ocenia każdego uczestnika wydając werdykt : "zdał" lub "nie zdał". Załóżmy , ze \(\displaystyle{ k}\) jest liczbą o tej własności: dla każdych dwóch egzaminatorów ich oceny są zgodne dla co najwyżej \(\displaystyle{ k}\) uczestników. Wykaż , że

\(\displaystyle{ \frac{k}{a} \geqslant \frac{b-1}{2b}}\)

[Damianito]

Edit:

Istotnie, za dużo z pomocą następnych postów pozwoliłem sobie założyć co do treści zadania.