Klatki z lwami

[tomek1172]

Na ile sposobów jesteśmy w stanie umieścić 5 lwów w 20-tu stojących rzędem klatkach, tak aby każdy lew był w osobnej klatce i aby żadne lwy nie były w sąsiednich klatkach?

[Mruczek]

Hint:    

Trzeba jakby odwrócić sytuację z tego zadania. Wiemy, że w \(\displaystyle{ 15}\) klatkach nic nie umieścimy. Tak jakby ustawiamy je w rzędzie i z \(\displaystyle{ 16}\) miejsc znajdujących się między tymi klatkami (oraz na początku i na końcu) wybieramy \(\displaystyle{ 5}\), w których postawimy klatki z lwami.

[arek1357]

Według mnie ułożyć można trzy równania typu:

\(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=15}\) - dwa równania tego typu gdzie jedna klatka będzie stała na końcu

jedno równanie tego typu:

\(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}=15}\) - gdzie obie klatki stoją na końcach

i jedno równanie tego typu:

\(\displaystyle{ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=15}\) - gdzie na końcach nie ma klatek

\(\displaystyle{ x_{i}}\) oznaczają klatki puste między klatkami z lwami, oczywiście: \(\displaystyle{ x_{i} \ge 1}\)

ilość rozwiązań to:

\(\displaystyle{ 2 \cdot {14 \choose 4} + {14 \choose 3} + {14 \choose 5}}\)

[Mruczek]

Powyższe rozwiązanie można minimalnie przyspieszyć układając tylko jedno równanie a nie trzy.

Ukryta treść:    

\(\displaystyle{ x_{i}}\) - długość przerwy między kolejnymi wybranymi klatkami
Zał, że \(\displaystyle{ x_{0}}\) to przerwa między początkiem rzędu i pierwszą klatką, a \(\displaystyle{ x_{5}}\) to przerwa między piątą klatką a końcem rzędu.
Chcemy policzyć liczbę rozwiązań równania w liczbach całkowitych:
\(\displaystyle{ x_{0} + x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 15}\), gdzie
\(\displaystyle{ x_{i} \ge 0}\), dla \(\displaystyle{ i \in \left\{ 0, 5\right\}}\) oraz
\(\displaystyle{ x_{i} \ge 1}\), dla \(\displaystyle{ i \in \left\{ 1, 2, 3, 4\right\}}\).
Tak więc:
\(\displaystyle{ x_{0} + (x_{1} - 1) + (x_{2} - 1) + (x_{3} - 1) + (x_{4} - 1) + x_{5} = 11}\)
Przyjmijmy:
\(\displaystyle{ y_{i} = x_{i}}\), dla \(\displaystyle{ i \in \left\{ 0, 5\right\}}\) oraz
\(\displaystyle{ y_{i} = x_{i} - 1}\), dla \(\displaystyle{ i \in \left\{ 1, 2, 3, 4\right\}}\).

Teraz szukamy rozwiązań równania:
\(\displaystyle{ y_{0} + y_{1} + y_{2} + y_{3} + y_{4} + y_{5} = 11}\), gdzie \(\displaystyle{ y_{i} \ge 0}\) dla dowolnego \(\displaystyle{ i}\).

Takich rozwiązań jest tyle co \(\displaystyle{ 11}\)-elementowych kombinacji z powtórzeniami ze zbioru \(\displaystyle{ 6}\)-elementowego czyli \(\displaystyle{ {16 \choose 11}}\).