W manewrach bierze udział oddział złożony z nieparzystej liczby żołnierzy (plus dowódca).
Cytat:Bez ruchu każą tkwić nam tu
Jak długo - nie pamiętam już
Brak nam powietrza słów i snu
W gardłach - zaschniętej śliny kurz
Jak okiem sięgnąć w strony dwie
Okopów linie ciągną się
A my czekamy - mija czas
I do ataku wciąż nie posyłają nas!
Żołnierze są rozmieszczeni w taki sposób, że odległości między dowolną parą są różne. Aby uatrakcyjnić żołnierzom czas, dowódca wydaje rozkaz, aby każdy żołnierz obserwował tego kolegę, który jest najbliżej. Sam dowódca nie bierze udziału w tym zadaniu.
Udowodnić, że co najmniej jeden żołnierz nie jest obserwowany.
Fakt, że liczba żołnierzy jest nieparzysta uniemożliwia żołnierską parafrazę "ty do mnie,a ja do ciebie", a skoro odległość między dwoma żołnierzami nigdy nie jest taka sama, to musi istnieć jedna największa odległość między jednym z żołnierzy, a najbliższym jego kolegą. W tej sytuacji ten żołnierz wprawdzie obserwuje kolegę, ale nie ma go kto obserwować, bo kolega musi mieć kogoś bliżej.
Alek napisał(a):skoro odległość między dwoma żołnierzami nigdy nie jest taka sama, to musi istnieć jedna największa odległość między jednym z żołnierzy, a najbliższym jego kolegą.
Niestety, jest to błędne rozumowanie. Wyobraź sobie, Alku, taką sytuację: wszyscy żołnierze z wyjątkiem dwóch znajdują się wewnątrz koła o średnicy 500 metrów. Zatem wszystkie odległości między tymi żołnierzami są mniejsze niż 500 metrów. Niech każdy z dwóch pozostałych żołnierzy znajduje się w odległości większej niż 1000 metrów od środka tego koła, a jednocześnie ci niech dwaj żołnierze znajdują się w odległości 600 metrów od siebie. Wtedy "największa odległość między jednym z żołnierzy, a najbliższym jego kolegą" dla obu tych żołnierzy będzie taka sama i będą się oni nawzajem obserwować.
Faktycznie
Ha, przyznam że rozumowałem tak samo jak Alek, przeczuwając jednak, że to rozumowanie błędne, więc siedziałem cicho.
A gdyby wykluczyć pary obserwujące się nawzajem i nowy zbiór z nieparzystą liczbą żołnierzy zbadać tylko pod kątem bycia obserwowanym i zastosować moje wcześniejsze, niezbyt trafne, rozumowanie?
Właśnie! Zapomniałem napisać, że to, że rozumowanie jest błędne, nie oznacza, że nieprzydatne!
dauri napisał(a):W manewrach bierze udział oddział złożony z nieparzystej liczby żołnierzy (plus dowódca). Żołnierze są rozmieszczeni w taki sposób, że odległości między dowolną parą są różne. Aby uatrakcyjnić żołnierzom czas, dowódca wydaje rozkaz, aby każdy żołnierz obserwował tego kolegę, który jest najbliżej. Sam dowódca nie bierze udziału w tym zadaniu.
Udowodnić, że co najmniej jeden żołnierz nie jest obserwowany.
Jeśli żołnież X obserwuje najbliżej siebie położonego Y, to i żołnież Y musi obserwować X, o ile inny - Z nie jest bliżej Y (ale dalej niż Y do X) - wówczas Y już nie obserwuje X, a jedynie Z, a Z jego, o ile ktoś nie jest bliżej Z niż Y... itd, aż (zbiór jest skończony) dojdziemy do takiego żołnierza, którego obserwuje przedostatni w tym ciągu będąc jednocześnie obserwowanym przez ostatniego. Pierwszy wtedy nie ma swojego obserwatora.
Proponuję rozwiązanie metodą indukcji.
1) Właściwość jest w oczywisty sposób spełniona dla trzech żołnierzy.
2) Załóżmy, że właściwość jest spełniona dla każdej grupy 2n+1 żołnierzy i rozważmy grupę 2n+3 żołnierzy. Wybieramy dwóch, których dzieli najkrótsza odległość (i patrzą na siebie nawzajem).
- Jeżeli nikt inny nie obserwuje żadnego z tych dwóch, to pozostałe obserwacje odbywają się w grupie 2n+1, dla której zgodnie z założeniem właściwość jest spełniona.
- Jeżeli zaś ktoś z grupy 2n+1 obserwuje jednego z tych dwóch, to jest on żołnierzem obserwowanym przez co najmniej dwóch żołnierzy. A obserwacji jest tyle, ilu jest żołnierzy, więc co najmniej jeden nie jest obserwowany.
W obu przypadkach właściwość jest więc spełniona dla 2n+3 żołnierzy.