Problem Tygodnia #7

[Liga]

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]

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

[Liga]

darek20 - odpowiedź jest prawidłowa. Gratulacje dla pyzola, który jako jedyny nadesłał prawidłowe rozwiązanie. Oto ono:

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