Matematyka.pl

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