L. Fregimus Vacerro (fregimus) wrote,
L. Fregimus Vacerro
fregimus

Деньги. Много денег

Задача простая, даже, пожалуй, детская: fregima привела более изящное доказательство решения, чем я.

Выложен ряд из N монет орлом вверх. На первом шаге переворачивают каждую монету, начиная с первой. На втором — каждую вторую, начиная со второй, на третьем — каждую третью, начиная с третьей, и так далее. На N-ом шаге переворачивают последнюю монету.

Требуется ответить, сколько монет будет лежать вверх решкой после того, как будет перевернута последняя монета. Решение должно быть в O(1), то есть количество вычислений не должно зависеть от числа монет N.

Комментарии не скрываю, так что в них вы можете неожиданно обнаружить ответ, поэтому рекомендую подумать, не заглядывая. Обсуждение, разумеется, всяко приветствуется.
Tags: math
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 45 comments