Question

На столе лежит много карточек,на каждой из них написано одно из трех чисел: 3,13,31.Какое самое маленькое количество карточек нужно взять , чтобы сумма всех чисел на них была равна 104

Answer 1

Ответ: 6 карточек.

Решение: 104 можно получить, взяв 1 карточку с числом 3, 3 карточки с числом 13 и 2 карточки с числом 31. Осталось понять, почему нельзя обойтись меньшим количеством карточек.

Пусть взяты 5 или меньше карточек, и сумма чисел на карточках равна 104.
Карточек с числом 31 надо взять не меньше трёх, иначе сумма чисел будет не превышать 2 * 31 + 3 * 13 = 101. Возьмём три карточки с числом 31, тогда останется набрать сумму 11, использовав не более двух карточек. 11 меньше 13, значит, ни одной карточки с числом 13 брать нельзя, но карточками с числом 3 невозможно получить сумму 11, так как 11 не делится на 3.
Противоречие, значит, пятью карточками (или меньшим количеством) получить сумму 104 нельзя.