Тест состоит из 30 вопросов, на каждый есть два варианта ответа (один верный, другой нет). За одну попытку Витя отвечает на все вопросы, после чего ему сообщают, на сколько вопросов он ответил верно. Сможет ли Витя действовать так, чтобы гарантированно узнать все верные ответы не позже, чем
  а) после 29-й попытки (и ответить верно на все вопросы при 30-й попытке);
  б) после 24-й попытки (и ответить верно на все вопросы при 25-й попытке)?
(Изначально Витя не знает ни одного ответа, тест всегда один и тот же.)

   Решение

Темы:    [ Индукция (прочее) ] [ Раскладки и разбиения ] [ Перебор случаев ] [ Деление с остатком ]

Сложность: 3- Классы: 6,7,8

Прислать комментарий

Условие

Любую ли сумму из целого числа рублей больше семи, можно уплатить без сдачи денежными купюрами по 3 и 5 рублей?

Решение 1

  Если эта сумма кратна 3 (наименьшее возможное число 9), используем только 3-рублевые купюры. Если при делении на 3 она даёт остаток 1 (наименьшее возможное число 10), то берём две 5-рублевые купюры, остальное доплачиваем 3-рублевыми. Если же при делении на 3 сумма даёт остаток 2 (наименьшее возможное число 8), то берём одну 5-рублевую купюру, остальное доплачиваем 3-рублевыми.

Решение 2

  Докажем это по индукции.
  База: сумму в 8 рублей выплатить можно.
  Шаг индукции. Пусть сумму в n рублей можно выплатить 3- и 5-рублевыми купюрами. Если среди этих купюр есть хоть одна 5-рублевая, то заменив её на две 3-рублевые, мы получим  n + 1  рублей. Если же все купюры 3-рублевые, то их не меньше трёх, и, заменив три 3-рублевые купюры на две 5-рублевые, мы тоже получим  n + 1  рублей.

Ответ

Любую.

Источники и прецеденты использования