?

Log in

No account? Create an account

Previous Entry | Next Entry

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

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

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

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

Комментарии не скрываю, так что в них вы можете неожиданно обнаружить ответ, поэтому рекомендую подумать, не заглядывая. Обсуждение, разумеется, всяко приветствуется.

Tags:

Comments

( 45 comments — Leave a comment )
blak_n_wait
Aug. 13th, 2009 05:35 am (UTC)
тупо наугад:
если Н четное, то (Н/2)+1
если Н нечетное, то (Н/2)-1/2
fregimus
Aug. 13th, 2009 05:40 am (UTC)
Для N=6 уже не так.
(no subject) - blak_n_wait - Aug. 13th, 2009 05:42 am (UTC) - Expand
dass
Aug. 13th, 2009 05:40 am (UTC)
1, 4, 9, 25, 36...
fregimus
Aug. 13th, 2009 05:41 am (UTC)
Это легко заметить. А доказательтво?
(no subject) - dass - Aug. 13th, 2009 05:46 am (UTC) - Expand
(no subject) - dass - Aug. 13th, 2009 05:47 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 06:04 am (UTC) - Expand
yurvor
Aug. 13th, 2009 05:42 am (UTC)
Либо я что-то не понимаю, и это слишком просто, либо одно из двух :)

После первых двух шагов решкой вверх будет лежать одна монета - первая. За следующие два шага - ещё одна, третья. И т.п. Итого ответ [N/2]
yurvor
Aug. 13th, 2009 05:43 am (UTC)
А, блин, каждую вторую! Одно из двух :))
(no subject) - fregimus - Aug. 13th, 2009 05:47 am (UTC) - Expand
1istik_figi
Aug. 13th, 2009 06:09 am (UTC)
Решкой вверх будут лежать монеты, номера которых имеют нечетное число делителей, т.е. являются квадратами; всего [\sqrt{N}].
fregimus
Aug. 13th, 2009 06:11 am (UTC)
Да!
1istik_figi
Aug. 13th, 2009 06:31 am (UTC)
А задачка-то довольно изящная. Спасибо за неё.
mikluha_maklai
Aug. 13th, 2009 06:40 am (UTC)
Разве только квадраты имеют нечетное число делителей?
А не любые числа вида
(a1)n1*(a2)n2*...*(ak)nk
где
ai - попарно разные простые числа,
ni - любые положительные целые числа,
k - нечетное
?
(no subject) - dimrub - Aug. 13th, 2009 07:04 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 07:05 am (UTC) - Expand
(no subject) - mikluha_maklai - Aug. 13th, 2009 07:09 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 07:13 am (UTC) - Expand
dimrub
Aug. 13th, 2009 07:03 am (UTC)
Не понимаю. Решкой вверх будут лежать монеты, номер которых является квадратом целого числа. Но таких чисел - abs(sqrt(N)). Как это число посчитать за O(1) - непонятно.
fregimus
Aug. 13th, 2009 07:07 am (UTC)
Именно так и посчитать. А почему нет?
(no subject) - dimrub - Aug. 13th, 2009 07:08 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 07:11 am (UTC) - Expand
(no subject) - dimrub - Aug. 13th, 2009 07:16 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 07:17 am (UTC) - Expand
(no subject) - dimrub - Aug. 13th, 2009 07:18 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 07:31 am (UTC) - Expand
(no subject) - dimrub - Aug. 13th, 2009 07:35 am (UTC) - Expand
(no subject) - dimrub - Aug. 13th, 2009 07:40 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 07:42 am (UTC) - Expand
(no subject) - dimrub - Aug. 13th, 2009 07:45 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 08:55 am (UTC) - Expand
(no subject) - dimrub - Aug. 13th, 2009 09:08 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 09:16 am (UTC) - Expand
(no subject) - dimrub - Aug. 13th, 2009 10:06 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 10:09 am (UTC) - Expand
(no subject) - janatem - Aug. 13th, 2009 09:14 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 09:19 am (UTC) - Expand
timur0
Aug. 13th, 2009 09:14 am (UTC)
Целая часть от корня квадратного из N

Решение: каждая монета будет перевернута столько раз, сколько у ее номера есть различных делителей. Это число только у квадратов нечетно (т.к. все делители разбиваются на пары p*q=N, а только у квадрата есть одинаковые p и q). Т.о. перевернутыми нечетное число раз окажутся только монеты с "квадратными" номерами.
fregimus
Aug. 13th, 2009 09:18 am (UTC)
Да, так. Я какое-то жуткое комбинаторное решение выдал через простые множители, а ребенок вот такое нашел.
(no subject) - timur0 - Aug. 13th, 2009 09:26 am (UTC) - Expand
janatem
Aug. 13th, 2009 09:48 am (UTC)
Хм, так просто, что даже основная теорема арифметики не требуется?
(no subject) - timur0 - Aug. 13th, 2009 10:02 am (UTC) - Expand
(no subject) - janatem - Aug. 13th, 2009 10:43 am (UTC) - Expand
(no subject) - fregimus - Aug. 13th, 2009 10:53 am (UTC) - Expand
( 45 comments — Leave a comment )