Zagadka kaczmarologiczno-batalistyczna

[dauri]

W manewrach bierze udział oddział złożony z nieparzystej liczby żołnierzy (plus dowódca).

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.

[Alek]

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.

[Luter]

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

[Alek]

Faktycznie

[MateuszNagórski]

Ha, przyznam że rozumowałem tak samo jak Alek, przeczuwając jednak, że to rozumowanie błędne, więc siedziałem cicho.

[Alek]

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?

[Luter]

Właśnie! Zapomniałem napisać, że to, że rozumowanie jest błędne, nie oznacza, że nieprzydatne!

[MacB]

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.

[dauri]

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.