Може ли помощ за една задача:Куки Монстер има 10чинии.На тях има сътветно 1,2,4,8,16,32,64,128,256,512 кифли.Той може да вземе произволен брой чинии и да изяде от тях по равен брой кифли.Докажете,че не може да изяде всички кифли за 9 хода.
Ще решим следната, по-обща задача: Куки има n ≥ 2 чинии, номерирани от 1 до n, като за всяко k = 1, 2, …, n, в чиния k има 2
k-1 на брой кифли. За един ход Куки може да избере произволен брой чинии и да изяде от тях по равен брой кифли. Да се докаже, че минималният брой ходове, с които Куки може да изяде всички кифли е равен на n.
Доказателството ще извършим по индукция.
При n = 2, Куки има две чинии, в които има съответно 1 и 2 кифли. След първия ход са възможни следните конфигурации: (1, 2) => (0, 2); (1, 0); (1, 1); (0, 1). Следователно Куки не може да изяде всички кифли с един ход. От друга страна, Куки може да изяде всички кифли с два хода по следния начин: (1, 2) => (0, 1) => (0, 0). Следователно при n = 1 твърдението е изпълнено.
Да допуснем, че за някое n = k ≥ 2, минималният брой ходове, с които Куки може да изяде всички кифли е равен на k. Ще докажем, че при n = k + 1, минималният брой ходове, с които Куки може да изяде всички кифли е равен на k + 1.
Понеже кифлите са краен брой, то съществуват и краен брой последователности от ходове, с които Куки може да изяде всички кифли. Следователно съществуват една или няколко последователности от ходове, при които броят ходове е минимален.
Нека П
0 е последователност от минимален брой ходове, с която Куки може да изяде всички кифли.
Понеже 2
0 + 2
1 + 2
2 + . . . + 2
k-1 = 2
k - 1 < 2
k, то в П
0 трябва да има поне един ход, при който Куки изяжда някакъв брой кифли (от 1 до 2
k) само и единствено от чиния k + 1. В противен случай общият брой кифли в чинии от 1 до k трябва да бъде поне 2
k.
Понеже П
0 е последователност от минимален брой ходове, то има точно един ход, на който Куки изяжда кифли само и единствено от чиния k + 1. Няколко различни хода, при които Куки изяжда съответно X
1, Х
2, ..., Х
m, m ≥ 2, само от чиния k + 1, могат да бъдат заменени от един ход (на мястото на X
m), при който той изяжда X
1 + X
2 + . . . + X
m кифли само от чиния k + 1.
Нека П
1 е последователността, която се получава от П
0 като преместим на последно място хода, при който Куки изяжда кифли само и единствено от чиния номер k + 1 и запазим всички останали ходове като последователност при избор на чиниите и брой изядени кифли. Ясно е, че П
1 също е последователност от минимален брой ходове, с която Куки може да изяде всички кифли.
Нека П
2 е последователността, която се получава от П
1 като запазим всички ходове като последователност при избор на чиниите и брой изядени кифли, но без да се изяждат кифли от чиния k + 1, като всички 2
k кифли от чиния k + 1 се изяждат на последния ход. П
2 също е последователност от минимален брой ходове, с която Куки може да изяде всички кифли.
Нека П
3 е последователността, която се получава от П
2 като запазим всички ходове като последователност при избор на чиниите и брой изядени кифли, но премахваме последния ход, на който се изяждат всички 2
k кифли от чиния k + 1. П
3 е последователност, с която се изяждат всички кифли в чинии от 1 до k и понеже П
0, П
1 и П
2 са последователности от минимален брой ходове, то П
3 трябва да бъде последователност от минимален брой ходове, с която се изяждат всички кифли в чинии от 1 до k, защото иначе ще получим противоречие с минималния избор на П
0.
Според индукционното предположение П
3 се състои от k хода и следователно П
0 се състои от k + 1 хода.
С това индукцията е завършена.
При n = 10, минималният брой ходове, с които Куки може да изяде всички кифли е равен на 10.