Matematyka.pl

Z listy 10 liczb całkowitych od 1 do 10 chcemy wybrać cztery w taki sposób, że żadne dwie nie znajdują się obok siebie. Przykładowo:
- 2 4 6 8 jest okej
- 1 2 5 8 nie może być

Jak do tego podejść? Dosyć szybko wyszło mi policzenie w głowie przypadków ale wydaje mi się że powinno być jakieś ogólne rozwiązanie w przypadku większej ilości liczb.

Z góry dzięki za pomoc

Powiedzmy, że zamiast dziesięciu kul ustawionych w ciąg, masz siedem i przemalowujesz dowolne cztery. Następnie pomiędzy każde dwie przemalowane wstawiasz jeszcze jedną kulę. Efekt końcowy jest ten sam.

Ten problem to chyba taka klasyka. Załóżmy, że mamy n kolejnych liczb i chcemy wybrać k z nich tak, aby żadne dwie nie stały obok siebie, k<n.
Niech zmienne \(\displaystyle{ x_i}\) oznaczają względną pozycję w ciągu, tzn. odległość od poprzedniej pomalowanej kuli.
Zatem mamy:
\(\displaystyle{ x_1 \ge 1}\)
pozostałe k-1 zmiennych: \(\displaystyle{ x_i \ge 2}\)

I sprowadziliśmy problem do problemu rozwiązań w liczbach całkowitych równania (przy założeniach powyżej:
\(\displaystyle{ x_1+...+x_k \le n}\)
odejmujemy od obu stron 1 i mamy \(\displaystyle{ x_i \ge 1 \forall i=1,...,k}\)
dodajemy k+1-wszą zmienną \(\displaystyle{ x_{k+1} \ge 0}\), aby z nierówności otrzymać równość, zatem
\(\displaystyle{ x_1+...+x_k+x_{k+1}=n-1}\), dodajemy 1 do ostatniej zmiennej, aby była większa lub równa 1.
i mamy:
\(\displaystyle{ x_1+...+x_k+x_{k+1}=n}\)
a rozwiązaniem tego jest n-1 po k (warto zrozumieć dowód w Aspektach Kombinatoryki Bryanta, ciężko go tu napisac)
jeśli nie ma tam gdzieś czeskiego błędu to jest ok