 |
A B. 4804. feladat (2016. szeptember) |
B. 4804. Sir Robin meg akarja szabadítani Agnor városát a háromfejű, háromfarkú sárkány rémétől a tavak királynőjétől kapott szablyával. Egy vágással egy fejet, két fejet, egy farkat vagy két farkat vághat le. Ha levágja a sárkány egy fejét, akkor három új fej nő helyette. Ha két fejet vág le, akkor nem nő helyette semmi. Ha egy farkat vág le, akkor két farok nő ki. Végül, ha két farkat vág le, akkor kinő egy új fej. Mennyi az a legkisebb szám, ahány vágással megölheti a sárkányt (vagyis annak nem maradhat egy feje és egy farka sem)?
(Német versenyfeladat)
(3 pont)
A beküldési határidő 2016. október 10-én LEJÁRT.
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).
Statisztika:
286 dolgozat érkezett. 3 pontot kapott: 226 versenyző. 2 pontot kapott: 23 versenyző. 1 pontot kapott: 13 versenyző. 0 pontot kapott: 21 versenyző. Nem versenyszerű: 3 dolgozat.
A KöMaL 2016. szeptemberi matematika feladatai