Здравейте, на племенничката ми от шести клас дали следната задача по ЗИП:
фигурата кон се намира в долен ляв ъгъл на шахматно поле с размери 5 х 5. Колко различни позиции може да има коня след 3 хода?
Учили са някакви елемнтарни понятия от комбинаторика, но нямам време да си ги припомням и аз. Чудя се дали има някакво елегантно решение, или трябва да изброя "на ръка" възможните комбинации?

Ако коня е на черно поле, тогава след 3 хода ще бъде на бяло поле. Принципно това са 12 позиции от 25 квадратчета. Въпроса е как да се докаже че за три хода може да обиколи всичките...предвид факта че не всеки от осемте хода е възможен поради ограничението в размера.

Здравей. За елегантно решение не знам, но "на ръка" излизат 12:

Съдържаниет е скрито
Влезте за да го видите

Съдържаниет е скрито
Влезте за да го видите

да, това и аз го направих, като минах всички варианти подобно на твоето решение. Въпроса е дали има решение само с комбинации? Например, да разложим движението по двете оси, и да сметнем комбинациите при които едната ос се променя с +/- 1, а другата с+/- 2; но така ще е трудно да се вземат предвид границите на полето....

Защо да е трудно, просто смяташ съответно и по x и по y сумите от трите хода и премахваш решенията, за които сумите са извън интеврала [5;0], за да си вътре в квадрата 5x5 с начална позиция 0;0.
Може и така - от първоначалната позиция са възможни по принцип 2 на степен 2 хода, съответно както си написал +1, -1, +2, -2,
т.е.
(+1+2) (+1-2) (-1+2) (-1-2) (+2+1) (+2-1) (-2+1) (-2-1)
Обаче тези от тях, които са с различен знак на движението по x и по y са еквивалентни, т.е. с еднакъв краен резултат. (-1+2) и (+2-1) са по същество един и същи ход, тъй като крайната позиция на коня е една и съща.
Т.е. от 8 теоретични хода, редуцираме 2 и остават 6.
След това към всяка позиция добавяме по 6 възможни хода,
примерно
(+1+2) + (+1+2), и т.н.
Така се получава 6 на степен 3-та възможни хода.
От тях обаче като отсеем тези, които са извън квадрата както казахме отначало, и като отсеем тривиалните решения, при които конят на третия ход се връща в първоначалното си положение или където има повторения, би могло да се получи някакво по-теоретично решение, но в случая бройките са твърде малко и е по-лесно на ръка да ги преброиш според мен.

Всичко е правилно. Остава само да се покаже, че всяко от 12-те бели полета е възможно. Достатъчно е да се опишат ходовете за 6-те бели полета под главния диагонал. Останалите са ясни предвид симетрията.

А ако някой от ходовете пресича главния диагонал? Какво толкова ще спечелиш от тази "хитрост"?

Да, това е ясно, но са само общи съждения. Въпроса е защо това се дава на деца в 6 клас и как може да се реши до достигане на крайния отговор без "броене на ръка". И въобще възможно ли е "решение с формули", с някакъв хитър подход, без да се намесват сложни комбинаторни разсъждения по-подходящи за ВУЗ?

Разбира се, че ходовете ще пресичат главния диагонал. Какъв е проблема?