Forum o Jacku Kaczmarskim
Zagadka kaczmarologiczno-batalistyczna - Wersja do druku

+- Forum o Jacku Kaczmarskim (https://kaczmarski.art.pl/forum)
+-- Dział: Różności (https://kaczmarski.art.pl/forum/forumdisplay.php?fid=6)
+--- Dział: Hyde Park (https://kaczmarski.art.pl/forum/forumdisplay.php?fid=26)
+--- Wątek: Zagadka kaczmarologiczno-batalistyczna (/showthread.php?tid=7415)



Zagadka kaczmarologiczno-batalistyczna - dauri - 06-16-2010

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.


Re: Zagadka kaczmarologiczno-batalistyczna - Alek - 06-16-2010

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.


Re: Zagadka kaczmarologiczno-batalistyczna - Luter - 06-16-2010

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


Re: Zagadka kaczmarologiczno-batalistyczna - Alek - 06-16-2010

Faktycznie Smile


Re: Zagadka kaczmarologiczno-batalistyczna - MateuszNagórski - 06-16-2010

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


Re: Zagadka kaczmarologiczno-batalistyczna - Alek - 06-16-2010

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?


Re: Zagadka kaczmarologiczno-batalistyczna - Luter - 06-16-2010

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


Re: Zagadka kaczmarologiczno-batalistyczna - MacB - 06-17-2010

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.


Re: Zagadka kaczmarologiczno-batalistyczna - dauri - 06-17-2010

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.