11 osób na 15 krzesłach w kinie

Łukasz_1989 · Post autor: **Łukasz_1989** » 16 wrz 2009, o 19:20

W kinie jest 15 krzeseł ustawionych w jednym rzędzie. Na tych krzesłach siedzi 11 osób. Ile przynajmniej osób siedzi obok siebie?

Prosiłbym o możliwie najszybsze zrobienie tego zadania z podaniem sposobu jego rozwiązania a nie tylko odpowiedzi.-- 16 września 2009, 22:22 --Nikt nie potrafi tego zrobić?

Kartezjusz · Post autor: **Kartezjusz** » 17 wrz 2009, o 12:55

W najgorszym dla naszego zadania ułożeniach sadzamy 8 osób na miejscach 1,3,5... zawsze przedzieli ich
puste miejsce. zostaja 3 osoby pierwszą z nich na miejscu 2 lub14(trzy osoby będą miały sąsiada).drugą na miejscu gdzie już jest tłok(2 osoby dodatkowo mają sąsiada)(osoby obok siebie-jedno z miejsc 4 lub12 ,a trzecią tam gdzie już siedzą obok siebie (6 lub 10)(kolejni dwaj z sąsiadami. .Co najmniej Będzie siedziało 7 osób obok siebie.

Łukasz_1989 · Post autor: **Łukasz_1989** » 17 wrz 2009, o 20:57

Kartezjusz, w taki sposób to i ja potrafię to zrobić
Sęk w tym, że rozwiązanie tego typu ma swoje wady - jest skuteczne dla przypadku wyżej ale jakbyśmy mieli np. 12356 miejsc siedzących i np. 8675 osób to już byłby problem...

Może ktoś wie jak to zrobić ogólnie, z wyjaśnieniami tak by można było to zastosować do przypadku n osób i k miejsc;)

Kartezjusz · Post autor: **Kartezjusz** » 18 wrz 2009, o 09:59

Oczywiście n<k.
1.Najpierw zajmujemy miejsca 1,3,5,.... gdy k jest nieparzyste
liu 2,4,6,8... gdy k jest parzyste.
Zostaje nam
\(\displaystyle{ [ \frac{k}{2}]}\) miejsc wolnych,a zostaje \(\displaystyle{ n-[ \frac{k}{2}]osób}\)
Obsadźmy teraz skrajne wolne 2 osobami miejsca:
Będziemy mieli 6 osób sąsiadujących ze sobą. Zostanie n-[ frac{k}{2}]-2.osób. zajmujmy teraz pozostałe wolne miejsca,ale na skrajnych pozycjach:każda osoba przyniesie nam 2 nowe osoby mające sąsiadów miejsca
Czyli odpowiedź:
Co najmniej\(\displaystyle{ 2n-4-2 \cdot [ \frac{n}{2}]+6=2n+2-2[ \frac{n}{2}]}\) osób będzie miało sąsiada.
gdzie [x]-największa liczba całkowita mniejsza od x