Problem K. 687. (February 2021)

K. 687. There are some toy robots waiting on one side of a street. In each move, it is allowed to instruct exactly four robots to cross the street. For what number of robots is it possible to make all the robots end up on the other side?

(6 pont)

Deadline expired on March 10, 2021.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. 1, 2 és 3 robot esetén nem lehetséges (hiszen nincsen 4 robot, akinek parancsot adunk).

4 robot esetén 1 parancs elegendő.

Belátjuk, hogy páros sok robot esetén megoldható a feladat, páratlan sok robot esetén pedig nem.

Ha a robotok száma 4-gyel osztható, akkor négyesével meg lehet oldani a feladatot.

Ha a robotok száma 4-gyel osztva 2 maradékot ad (és legalább 6), akkor az első hat robotnak (A, B, C, D, E és F) a következő parancsokat adjuk: ABCD, ABCE. Így a D és E robotok átjutottak és a robotok száma a kiindulási oldalon már osztható 4-gyel. Innen a feladat megoldható négyesével átküldve a robotokat.

Ha a robotok száma páratlan, nem lehet megoldani a feladatot, mert egy-egy lépésben páros sok robottal változhat a robotok száma az utca egy-egy oldalán (\(\displaystyle 4-0 = 4\), \(\displaystyle 3-1 = 2\), \(\displaystyle 2-2 = 0\), \(\displaystyle 1-3 = -2\), \(\displaystyle 0-4 = -4\)). Kezdetben páratlan sok robot volt a kiindulási oldalon, így nem lehet a végén \(\displaystyle 0\).

Statistics:

106 students sent a solution.
6 points:	55 students.
5 points:	23 students.
4 points:	8 students.
3 points:	8 students.
2 points:	4 students.
1 point:	4 students.
0 point:	1 student.
Unfair, not evaluated:	1 solutions.
Not shown because of missing birth date or parental permission:	2 solutions.

Problems in Mathematics of KöMaL, February 2021