Problem Tygodnia #7

Historia, regulamin, zadania i oceny Konkursów oraz Ligi prowadzonej na Forum.
Liga
Gość Specjalny
Gość Specjalny
Posty: 168
Rejestracja: 29 wrz 2006, o 18:17
Płeć: Mężczyzna
Lokalizacja: Forum Matematyka.pl

Problem Tygodnia #7

Post autor: Liga » 23 maja 2011, o 00:48

W ośmiu pudełkach znajduje się po sześć piłek. Każda z piłek jest pokolorowana jednym z \(\displaystyle{ n}\) kolorów. W każdym pudełku znajdują się różnokolorowe piłki oraz żadna z par kolorów nie występuje więcej niż w jednym pudełku. Wyznacz najmniejszą liczbę kolorów spełniającą warunki zadania (i pokaż przykład kolorowania piłek).

pytanie dodatkowe: Ile wynosi \(\displaystyle{ n}\) dla 10 pudełek po 8 piłek w każdym?

darek20
Użytkownik
Użytkownik
Posty: 874
Rejestracja: 4 paź 2010, o 08:16
Płeć: Mężczyzna
Lokalizacja: wszedzie
Podziękował: 248 razy
Pomógł: 10 razy

Problem Tygodnia #7

Post autor: darek20 » 26 maja 2011, o 15:26

dla n=23 można tak ustawić np.:
\(\displaystyle{ \begin{array}{rrrrrrr}1&3&4&5&6&7\\1&8&9&10&11&12\\1&13&14&15&16&17\\2&3&8&13&18&19\\2&4&9&14&20&21\\2&5&10&15&22&23\\6&11&16&18&20&22\\7&12&17&19&21&23\end{array}}\)

a czy można mniej

ps nie wiem jak to ujac w latex, zeby lepiej wygladało
Ostatnio zmieniony 26 maja 2011, o 16:48 przez luka52, łącznie zmieniany 1 raz.
Powód: Np. w tabelkę ująć.

Liga
Gość Specjalny
Gość Specjalny
Posty: 168
Rejestracja: 29 wrz 2006, o 18:17
Płeć: Mężczyzna
Lokalizacja: Forum Matematyka.pl

Problem Tygodnia #7

Post autor: Liga » 30 maja 2011, o 09:58

darek20 - odpowiedź jest prawidłowa. Gratulacje dla pyzola, który jako jedyny nadesłał prawidłowe rozwiązanie. Oto ono:
pyzol pisze:Cóż odpowiem na apelację administratora. Ostatni post zmobilizował mnie, żebym do tego przysiadł. O ile dobrze zrozumiałem zadanie (i ile ) to nie wygląda tak strasznie i dziwi mnie, że nikt z kółkowiczów jeszcze go nie rozwiązał. Dla zaoszczędzenia waszego czasu wpiszę najpierw, że odpowiedź wyszła mi 23. Po co coś sprawdzać, jeśli ma zły wynik.
Zauważmy na starcie, że każde dwa pudełka mogą mieć tylko jeden kolor wspólny.
Prostym schematem możemy dojść do 24 kolorów. Nie będę póki co pisał, bo nie jest to minimalna ilość kolorów. Natomiast będzie to naszym odnośnikiem.
Zacznijmy od możliwości, że jeden kolor wystąpi we wszystkich ośmiu.
Wtedy niestety pozostanie nam \(\displaystyle{ 8\cdot 5}\) miejsc, które będziemy musieli poukładać różnymi kolorami. Podobne założenie możemy zrobić co do siedmiu sześciu i pięciu. W ostatnim przypadku musimy dorzucić przynajmniej 25 piłek o różnych kolorach.Zadanie komplikuje się lekko przy 4 kolorach. Wtedy stracimy 21 kolorów na obłożenie tych 4 pudełek.
I może jakiś rysunek a raczej tabelka:
\(\displaystyle{ \begin{array}{c|c|c|c|c|c|c|c}
*&*&*&*&&&&\\
A1&B1&C1&D1&&&&\\
A2&B2&C2&D2&&&&\\
A3&B3&C3&D3&&&&\\
A4&B4&C4&D4&&&&\\
A5&B5&C5&D5&&&&
\end{array}}\)

Pytanie jest takie czy jesteśmy w stanie pozostałe 4 pudełka obłożyć tymi kolorami. Nie możemy przy tym wliczyć pierwszego, który był już w czterech.
Zostaje nam 20 kolorów i 4 pudełka. Miejsc w nich mamy 24. Zauważmy jednak że do pustego pudełka możemy wstawić tylko po jednym kolorze z obstawionego już pudełka. Nie daje to dużo możliwości maksymalnie możemy zapełnić 16 miejsc. Zapełnimy je tak, żeby żadne z nowych nie miało wspólnego koloru. I tak mamy już ich dużo .
\(\displaystyle{ \begin{array}{c|c|c|c|c|c|c|c}
*&*&*&*&A1&A2&A3&A4\\
A1&B1&C1&D1&B1&B2&B3&B4\\
A2&B2&C2&D2&C1&C2&C3&C4\\
A3&B3&C3&D3&D1&D2&D3&D4\\
A4&B4&C4&D4&&&&\\
A5&B5&C5&D5&&&&
\end{array}}\)

Tym razem zostało nam osiem miejsc i musimy je wypełnić nowymi kolorami.
Nie będę się doliczał ile dokładnie minimalnie potrzeba.
Skwituję, że przynajmniej 2. W takim razie stracimy przynajmniej 23 kolory.
Teraz możemy się zabrać za trójki. Pominą podobny tok rozumowania i zatrzymam się na tym miejscu:
\(\displaystyle{ \begin{array}{c|c|c|c|c|c|c|c}
*&*&*&A1&A2&A3&A4&A5\\
A1&B1&C1&B1&B2&B3&B4&B5\\
A2&B2&C2&C1&C2&C3&C4&C5\\
A3&B3&C3&&&&&\\
A4&B4&C4&&&&&\\
A5&B5&C5&&&&&
\end{array}}\)

Co my tu mamy. Zostało nam 15 miejsc do obstawienia nowymi kolorami. Więc zanurzmy się tylko w te 5 pudełek i powtórzmy tok rozumowania:
\(\displaystyle{ \begin{array}{c|c|c|c|c}
**&**&**&X1&X2\\
X1&Y1&Z1&Y1&Y2\\
X2&Y2&Z2&Z1&Z2
\end{array}}\)

Straciliśmy 16+7=23 kolory. Z dwójkami nie ma sensu się bawić. Bo każdy kolor w tym układzie występuje przynajmniej 2 razy, więc jest to optymalne ułożenie.
Na drugie pytanie nie odpowiadam (jeszcze nie robiłem). Bardzo możliwe, że da się to takim tokiem rozumowania rozwiązać.
Jeśli nadal kogoś interesuje ten problem - można zadanie rozwiązać o wiele szybciej (tzn. wykazać, że minimalna liczba kolorów to 23, co z przykładem rozmieszczenia daje odpowiedź). W tym celu trzeba skorzystać z wypukłości funkcji \(\displaystyle{ \frac{1}{x}}\).

ODPOWIEDZ