skoczek i miny

[exupery]

Witam,
Na początku chciałbym przeprosić za wybór działu w którym umieszczam to zadanie, nie mniej jednak ponieważ nie wiedziałem, gdzie mogę je zamieścić, a jako że pochodzi ono z ćwiczeń z algebry abstrakcyjnej(choć nie widzę ścisłej analogii) zamieszczam tutaj.

Mamy sobie skoczka który skacze po prostej linii, wykonuje on n ruchów przy czym każdy jest innej długości i nie większej niż n. Tzn. wykonuje ruchy długości 1;2;3;....n-1;n przy czym w dowolnej kolejności. Czy jest możliwe, aby ustawiając na drodze n-1 min skoczek nie mógł przejść?

[Afish]

Spróbuję udowodnić przez indukcję, że nie da się tak umieścić min, aby skoczek nie mógł przejść, gdyż dla każdego \(\displaystyle{ n}\) skoczek może dojść do pola \(\displaystyle{ \frac{n\left(n+1\right)}{2} + 1}\).
1. \(\displaystyle{ n=2}\)
Przyjmijmy, że skoczek stoi na polu \(\displaystyle{ 1}\) i chce dojść dojść do pola \(\displaystyle{ 4}\). Minę możemy ustawić na polu \(\displaystyle{ 2}\) lub \(\displaystyle{ 3}\). Jeżeli ustawimy na polu \(\displaystyle{ 2}\), to wykonujemy skok o \(\displaystyle{ 2}\), a potem skok o \(\displaystyle{ 1}\). Jeżeli ustawimy na polu \(\displaystyle{ 3}\), to robimy skok o \(\displaystyle{ 1}\), a potem skok o \(\displaystyle{ 2}\). Teza jest spełniona.
2. Przyjmijmy, że dla \(\displaystyle{ n}\) teza jest spełniona. Oznacza to, że skoczek może dojść do pola \(\displaystyle{ \frac{n\left(n+1\right)}{2} + 1}\). Teraz dla \(\displaystyle{ n+1}\) mamy dodatkową minę do ustawienia i jedną możliwość ruchu więcej. Załóżmy, że dodatkową minę ustawimy na na polu \(\displaystyle{ \frac{n\left(n+1\right)}{2} + 1}\). Ale wtedy wykonując jako przedostatni ruch od długości \(\displaystyle{ n+1}\) przeskakujemy to pole i lądujemy na polu, z którego możemy łatwo dojść do pola \(\displaystyle{ \frac{\left( n+1\right)\left(n+2\right)}{2} + 1}\) (gdyż przed wykonaniem przedostatniego ruchu jesteśmy na polu odległym o \(\displaystyle{ k}\) od pola \(\displaystyle{ \frac{n\left(n+1\right)}{2} + 1}\) i mamy do dyspozycji ruchy \(\displaystyle{ k}\) i \(\displaystyle{ n+1}\)). Jeżeli zaś dodatkową minę położymy na dowolnym innym polu, to najpierw dochodzimy do pola \(\displaystyle{ \frac{n\left(n+1\right)}{2} + 1}\), a potem wykonujemy ruch o długości \(\displaystyle{ n+1}\), dzięki któremu dochodzimy do pola \(\displaystyle{ \frac{\left (n+1\right)\left(n+2\right)}{2} + 1}\).
Za wszelkie błędy z góry przepraszam, wakacje są

[Qń]

Ale przecież może też być tak, że nowa mina jest na polu \(\displaystyle{ \frac{n(n+1)}{2}+1}\), a jedną ze starych min przełożymy dalej w ten sposób, żeby była w miejscu na które trafimy po wykonaniu przedostatniego skoku długości \(\displaystyle{ n+1}\).

Oczywiście nie czyni to tezy zadania nieprawdziwą, ale raczej obala dowód indukcyjny (przynajmniej w tej formie).

Q.

[Afish]

Zgadza się. Zorientowałem się, że dowód nie działa kilka minut po wysłaniu posta, ale już byłem poza domem