mateforum.ro

Pe o tabla \( n \times n \), cu \( n^2 \) patratele se aseaza un pion intr-un patratel arbitrar. Pionul presupus a fi intr-un patrat din coloana \( k \), poate fi mutat in orice patrat din linia \( k \). Aratati ca exista o secventa de \( n^2 \) mutari astfel incat orice patrat al tablei este vizitat exact o data si pionul se intoarce la pozitia initiala.

[IMAR 2008, Problema 1]

E suficient sa gasim un astfel de drum care pleaca din coltul stanga sus si se intoarce tot acolo, pentru ca alegand oricare punct facem exact mutarile consecutive din acest drum considerat.

Notam cu \( (m,n) \) patratul de pe linia \( m \) si coloana \( n \).
Pentru \( n=2 \) exista drumul \( (1,1)\to (1,2) \to (2,2) \to (2,1) \to (1,1) \).
Presupunem ca pentru \( n \) mai mare sau egal cu 2 exista un astfel de drum care incepe in (1,1) si are ca ultim patrat (n,1) ( dupa care evident ne putem intoarce in (1,1) ).
Atunci pentru un patrat de latura \( n+1 \) consideram drumul care pleaca din (1,1), parcurge patratul de latura n care contine pe (1,1) si are ultimul varf in (1,n) (folosind ipoteza de inductie)...
Atunci consideram succesiunea de mutari \( (n,1) \to (1,n+1) \to (n+1,2) \to (2,n+1) \to... \to (n+1,n) \to (n,n+1) \to (n+1,n+1) \to (n+1,1) \to (1,1) \).
Deci am gasit un drum si pentru \( n+1 \). Din inductie problema este rezolvata.