RSS Feed
Precedenta

Problema 313

05 Decembrie 2010

Jocul alunecării


Într-un joc, un buton se poate mișca orizontal sau vertical într-o poziție liberă. Obiectivul jocului este să miști butonul roșu din colțul stânga-sus la colțul dreapta-jos; poziția liberă la început e întotdeauna în colțul dreapta-jos. De exemplu, următoarele imagini arată cum jocul se poate juca pe o tablă de dimensiune 2 pe 2.

Fie S(m,n) numărul minim de mutări pentru a completa jocul pe o tablă de dimensiune m pe n. De exemplu, se poate verifica că S(5,4) = 25.

Sunt exact 5482 de table diferite pentru care S(m,n) = p2, unde p < 100 e un număr prim.

Câte table există care au S(m,n) = p2, unde p < 106 e un număr prim ?


>> Vezi problema originală <<