[Rozgrzewka OM][MIX][Kombinatoryka] Kombinatoryka

[Dumel]

raczej nie masz racji choćby dlatego ze samych ciągów w w których i-ty gość zajmuje i-te miejsce jest n!-- 18 grudnia 2010, 14:50 --

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}}\)

wrzućmy to do macierzy \(\displaystyle{ a \times b}\). 1- egzamin zdany. -1 - niezdany.
teraz weźmy sobie wektorki egzaminatorów: \(\displaystyle{ k_1,k_2,...,k_b}\)
niech \(\displaystyle{ i \neq j}\) oraz niech \(\displaystyle{ k_i}\) i \(\displaystyle{ k_j}\) zgadzają się na \(\displaystyle{ l}\) pozycjach. wtedy \(\displaystyle{ k_i \cdot k_j=l-(a-l)=2l-a \le 2k-a}\)
ponadto oczywiście \(\displaystyle{ k_i \cdot k_i =a}\)
\(\displaystyle{ b}\) jest nieparzyste wiec wektor \(\displaystyle{ k_1+k_2+...+k_b}\) ma wszystkie współrzedne niezerowe czyli \(\displaystyle{ (k_1+k_2+...+k_b)^2 \ge a}\). już prawie koniec:
\(\displaystyle{ a \le (k_1+k_2+...+k_b)^2 \le ab+b(b-1)(2k-a)}\)
a to jest równoważne tezie.

jak ktoś ma pod ręką fajne zadanko to niech wrzuci, bo teraz nie mam żadnego pod ręką

[półpasiec]

Na spotkaniu przedwyborczym pewnej partii każdy członek wybiera spośród uczestników spotkania 10 swoich kandydatów. Grupę ludzi nazwiemy lubianą przez danego członka, jeśli jest w niej co najmniej jeden jego kandydat. Wiadomo, że dla dowolnych sześciu wyborców istnieje dwuosobowa grupa uczestników spotkania lubiana przez każdego z tej szóstki. Dowieść, że istnieje 10 członków partii tworzących grupę lubianą przez wszystkich uczestników spotkania.

[Dumel]

to zadanie nr 9 z BW07 (info by darek20) tu jest rozwiązanie: ... utions.pdf

[Swistak]

To może ja wrzucę dość prosty problem:
W pewnym towarzystwie osób, jeżeli pewne 2 osoby mają taka samą liczbę znajomych, to nie mają żadnych wspólnych znajomych. Udowodnij, że istnieje osoba, która ma dokładnie jednego znajomego, lub nikt nie zna nikogo.

[Swistak]

Coś się zastój zrobił . To ja odkopię z nowym zadaniem:
Pokazać, że zbiór liczb naturalnych można rozbić na 2 rozłączne zbiory takie, że żaden z nich nie zawiera trzech kolejnych wyrazów oraz nieskończonego zbioru arytmetycznego.

[ElEski]

Swistak,
Jeśli jedna osoba zna drugą, to druga zna pierwszą?

[Swistak]

Tak, ale obowiązującym zadaniem jest to z dwoma zbiorami .

[Panda]

toz2zbiorami:    

Niestety niezbyt ładnie

Pokażemy jak skonstruować 2 zbiory \(\displaystyle{ X,Y}\) spełniające warunki.
Bierzemy wszystkie pary \(\displaystyle{ (a,b)}\), gdzie \(\displaystyle{ a,b \in \mathbb{N} \cup {0},a>1,b<a}\) i budujemy z nich ciąg \(\displaystyle{ (a_{1},b_{1}), (a_{2},b_{2}),...}\) taki, że \(\displaystyle{ i < j \Leftrightarrow a_{i} < a_{j} \vee (a_{i} = a_{j} \wedge b_{i} < b_{j})}\). Każdy nieskończony ciąg arytmetyczny o różnicy większej niż \(\displaystyle{ 1}\) jest jednoznacznie reprezentowany przez taką parę.

Zamiast o umieszczaniu liczb w zbiorach \(\displaystyle{ X,Y}\) będziemy mówić o kolorowaniu na kolor \(\displaystyle{ x i y}\).

Teraz już napiszę krótko - idziemy po ciągu i kolorujemy na różne kolory za każdym razem 2 liczby należące do ciągu arytmetycznego reprezentowanego przez aktualnie rozważaną parę - w ten sposób dla danej pary \(\displaystyle{ (a_{i},b_{i})}\) dbamy, by ciąg arytmetyczny postaci \(\displaystyle{ a_{i}x+b_{i}}\) nie był całościowo zawarty w żadnym ze zbiorów. Liczby, które kolorujemy muszą należeć do danego ciągu i być odpowiednio większe (powiedzmy, że o przynajmniej \(\displaystyle{ 3}\), o tyle też przynajmniej niech będą odległe od siebie nawzajem) od maksymalnego spośród aktualnie pokolorowanych - a zawsze kolorujemy po \(\displaystyle{ 2}\), a na początku jest \(\displaystyle{ 0}\), więc zawsze istnieje maksimum. Czyli się da. W ten sposób, dla każdego ciągu arytmetycznego istnieje jakaś para liczb należących do niego, które są różnych kolorów.

Teraz musimy pokolorować resztę tak, żeby nie było \(\displaystyle{ 3}\) kolejnych tego samego koloru.
Między każdymi dwoma już pokolorowanymi są przynajmniej \(\displaystyle{ 2}\) liczby niepokolorowane (bo robiliśmy tak, że różnica wynosiła przynajmniej \(\displaystyle{ 3}\)).
Przede wszystkim, bierzemy każdą pokolorowaną liczbę i jej 2 "sąsiadów" kolorujemy na inne kolory. Następnie, resztę spójnych przedziałów wypełniamy kolorowaniami postaci \(\displaystyle{ ababa...ab}\) - w ten sposób maksymalnie 2 kolejne liczby będą tego samego koloru.
Nasza konstrukcja generuje 2 zbiory spełniające założenie, co dowodzi ich istnienia.

Mógłby ktoś sprawdzić, czy nie ma błędu?

Moje zadanie:

Czy można wybrać na płaszczyźnie \(\displaystyle{ 5}\) punktów takich, że odległości między nimi są równe \(\displaystyle{ 1,2,...,10}\)?

[skazy]

Ukryta treść:    

Załóżmy nie wprost, że takie punkty istnieją. Oznaczmy je jako \(\displaystyle{ A,B,C,D,E}\).
Wybierzmy te dwa punkty (bez straty ogólności \(\displaystyle{ A,B}\)), między którymi odległość jest równa \(\displaystyle{ 1}\). Teraz zauważmy, że niezależnie od odległości \(\displaystyle{ CA}\) oraz \(\displaystyle{ CB}\) (wyrażonych liczbami całkowitymi z zakresu \(\displaystyle{ {2...10}}\)), odległości \(\displaystyle{ AB,BC,CA}\) nie spełnią nierówności trójkąta, a więc jak łatwo zauważyć punkty \(\displaystyle{ A,B,C}\) będą współliniowe, oraz \(\displaystyle{ |CB-CA|=1}\).
Analogicznie można dowieźć, że punkty \(\displaystyle{ A,B,D}\) oraz \(\displaystyle{ A,B,E}\) są współliniowe, a co za tym idzie że wszystkie szukane punkty są współliniowe.

Pozostaje nam do rozpatrzenia układ 5 punktów w jednej linii i 4 odcinków między nimi. Długości tych czterech odcinków lub sumy długości sąsiednich odcinków muszą być równe liczbom z zakresu \(\displaystyle{ {1...10}}\). Tutaj już idzie szybko, łatwo zauważamy że te cztery odcinki mają długości ze zbioru \(\displaystyle{ {1,2,3,4}}\), jeśli pewne sąsiadujące odcinki mają dać po zsumowaniu ich długości wartość \(\displaystyle{ 5}\), to sytuację tę spełniają tylko odcinki o długościach \(\displaystyle{ 1,4}\) lub \(\displaystyle{ 3,2}\). Podobnie dla sumy długości \(\displaystyle{ 6}\), sąsiadować ze sobą muszą odcinki o długościach \(\displaystyle{ 1,2,3}\) lub \(\displaystyle{ 2,4}\).
Jeśli pewne odcinki po zsumowaniu długości mają dać \(\displaystyle{ 9}\), to układ ten spełnia tylko sąsiedztwo odcinków o długościach \(\displaystyle{ 2,3,4}\). Z kolei sumę \(\displaystyle{ 8}\) dają w sąsiedztwie tylko długości \(\displaystyle{ 2,3,4}\). Zatem aby oba powyższe warunki zostały spełnione, możliwe są tylko dwa układy długości odcinków: \(\displaystyle{ 1,3,4,2}\) lub\(\displaystyle{ 2,3,4,1}\) (układy \(\displaystyle{ 2,4,3,1}\) i \(\displaystyle{ 1,4,3,2}\) to te same co powyższe, tylko w odwrotnej kolejności).
W pierwszym układzie nigdy nie uzyskamy sumy \(\displaystyle{ 5}\), a w drugim sumy \(\displaystyle{ 6}\), a zatem punkty szukane w zadaniu nie istnieją.

W przedszkolu wykryto wśród dzieci sześć różnych chorób. Na każdą chorobę choruje dokładnie trójka dzieci (jedno dziecko może cierpieć na więcej niż jedną chorobę). Rozstrzygnąć, czy dzieci da się tak rozdzielić na dwie grupy, żeby w żadnej grupie nie znalazły się wszystkie dzieci chorujące na którąś z chorób?