Problem B. 4804. (September 2016)

B. 4804. With his sword received from the queen of the lakes, Sir Robin wants to free the town of Agnor from a dragon. The dragon has three heads and three tails. With one slash, he may cut off one head, two heads, one tail or two tails. If he cuts off one head, the dragon will immediately grow three heads in its place. If he cuts off two heads, then nothing will grow in its place. If he cuts off one tail, there will be two tails growing immediately. Finally, if he cuts off two tails then the dragon will grow a head. What is the minimum number of cuts needed to kill the dragon (that is, in order that the dragon has no heads or tails remaining at all)?

(German competition problem)

(3 pont)

Deadline expired on October 10, 2016.

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

Megoldás. A farkak száma csak azzal a lépéssel tud csökkenni, amikor 2 farkat vág le, ilyenkor pedig pontosan 2-vel csökken. Azonban szintén ez az egyetlen olyan lépés, aminél megváltozik a fejek számának paritása, így ezt a lépést páratlan sokszor kell végrehajtani, hiszen kezdetben páratlan sok (3) fej van, a végén pedig páros sok (0) lesz. Ha viszont csak egyszer hajtanánk végre ezt a lépést, akkor legalább 1 farok maradna, így legalább háromszor kell végrehajtani. Ez azt jelenti, hogy összességében legalább 6 farkat fog levágni Sir Robin, és mivel kezdetben csak 3 volt, ezért legalább háromszor végre kell hajtani az egy farok levágása lépést, hiszen egyedül ennél nő a farkak száma, és itt is csak 1-gyel. Mivel legalább háromszor végrehajtja a 2 farok levágása lépést, ezért a kezdetben is meglévő 3 fejen kívül még legalább 3 keletkezni fog, így mivel az egyetlen olyan lépés, aminél csökken a fejek száma a 2 fej levágása – és ennél 2-vel csökken –, ezért ezt a lépést legalább 3-szor kell megtennie. Ez már összesen legalább 9 lépés. Most megmutatjuk, hogy ennyi elég is. Sir Robin először háromszor egymás után levág egy-egy farkat, ennek végeredményeképpen a fejek száma 3, a farkak száma 6 lesz. Ezután háromszori 2 farok levágása lépés következik, ami után 6 fej marad, a farkak elfogynak. Végül háromszor levág két-két fejet, és így a fejek is elfogynak. Tehát legalább 9 vágásra van szükség (és ennyi elegendő is).

Statistics:

286 students sent a solution.
3 points:	226 students.
2 points:	23 students.
1 point:	13 students.
0 point:	21 students.
Unfair, not evaluated:	3 solutionss.

Problems in Mathematics of KöMaL, September 2016