Цифровой 2018 - часть 2.

Previous Entry Поделиться Next Entry
11 декабря, 2017
e_kaspersky
Новая порция математических задачек под постепенно надвигающийся 2018-й.

Вот такая: про ромашку и закрашивание лепестков.

Однажды русские госхакеры решили поздравить друг друга с Новым Годом и нарисовали огромную такую ромашку с 2018 лепестками. Этакая окружность, на которой нарисованы лепестки. Для пущей красоты они решили закрасить лепестки ромашки. А поскольку они всё-таки программисты, то сделали они это необычным способом. Сначала был покрашен некий произвольный лепесток. Затем хакеры отступили от него на один лепесток по часовой стрелке и закрасили и его тоже. Затем отступили в том же направлении на два лепестка от только что покрашенного (то есть, пропустили один лепесток), потом отступили на три, четыре, пять - и так до бесконечности. То есть, на каждом шаге количество пропущенных лепестков увеличивается на один. Если первым был закрашен нулевой лепесток, то следующий будет номер 1, затем +2 = 3, +3 = 6, +4 = 10, +5 = 15 и так далее по кругу и в бесконечном цикле.

Внимание, вопрос1: какое количество лепестков будет в результате закрашено?

Увидев такие дела, американские госхакеры тоже решили нарисовать свою ромашку. Но поскольку бюджеты у них побогаче будут, то и ромашка получилась поразвесистей. И было закрашено в ней по той же схеме ровно 2018 лепестков.

Вопрос2: сколько лепестков было в американской госхакерской ромашке?

Вопрос3: единственное ли это решение? Хотя еврейский Новый Год и отмечается в совершенно другое время, но израильские госхакеры решили не отставать от своих коллег и тоже нарисовали ромашку, у которой тоже закрашивается ровно 2018 лепестков. Но она отличается от американской. Возможно ли такое?

Поскольку предыдущие задачки про 2018 как-то не вызвали энтузиазма у читающей публики, попробую промотивировать ваши извилины ценными призами первым ответившим правильно и с обоснованиями. А призов у нас много и всяких разных.

Удачи.
Метки:
Previous Entry Поделиться Next Entry

Записи из этого журнала по тегу «chtogdekogda»

  • Ответы о мячах.

    Всем привет! То ли моя недавняя задачка о мячах была слишком сложной, то ли слишком простой, а может быть просто не было достойной мотивации типа…

  • Задача о мячах.

    В эфире регулярная рубрика "О физико-математическом" - лучшая зарядка для ума, чтобы извилины были гладкими и шелковистыми, а серое вещество самой…

  • Воскресное. Рассказы и истории.

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


Заранее извиняюсь, что не досчитал. Осталось вспомнить программирование:)

Логика по первой задаче:
1. Через любое количество циклов, кратное 2018, закрашивание начнет работать как с первого цикла (номера от того текущего, в котором будет алгоритм. плюс 1,3,6,10,15...), потому что можно будет вычитать все, что кратно 2018, т.к. движение идет по кругу.
2. Смотрим в какой номер приведет закрашивание на 2018 цикле: 2018*(2018+1)/2=2037171, это 1009 полных кругов, получается номер 1009, т.е. ровно противоположная от начала алгоритма точка.
3. Значит еще через 2018 циклов алгоритм приведет в начальную точку и далее пойдет все делать повторно.
4. Итого достаточно посчитать, сколько будет закрашено лепестков за 4036 циклов, что и будет ответом на п.1.

Более того, получается, что для нечетного количества лепестков, алгоритм начнет повторяться со второго же повторения (повторение - n циклов закрашивания, где n - количество лепестков), т.к. количество кругов, пройденных алгоритмом не что иное, как (n+1)/2.
А для четного - только с третьего повторения, причем всегда.
Т.е. если число лепестков четное, то нужно 2n циклов закрашивания, а если нечетное - то n.

Дальше либо машинным методом, либо нужно вывести связь между количеством закрашенных и количеством лепестков итого (что, походу, невозможно). Оттуда будут точные ответы на вопросы 1 и 2.

Для точного ответа на вопрос 3 достаточно будет прогнать в алгоритме ромашку +-2 лепестка от американской, чтобы показать, что там закрашиваются 2018, меньше или больше лепестков соответственно. Ой, нет, там же еще могут быть ромашки в разы больше или в разы меньше, для которых закрашивание пройдет за одно или два повторение, а не за два или одно (в зависимости от четности американской ромашки)...Их тоже нужно прогнать возле 2018 закрашиваний, и тогда точно будет ответ.

Upd.
Алгоритм для определения количества закрашенных лепестков:
1. Обозначаем массив из 2018 (n) элементов, все равны 0
2. Запускаем цикл на 4036 (2*n) раз, в котором движемся по алгоритму закрашивания и присваиваем закрашенным номерам лепестков (элементам массива) значения 1.
3. На каждом шагу i определяем номер лепестка как: i*(i+1)/2-n*целаячасть(i*(i+1)/(2*n))
4. Считаем сумму элементов массива - это и есть ответ на первый вопрос. Пусть это будет m.

Для ответа на второй вопрос создаем дополнительный массив в который пишем по 2 значения: количество лепестков n и соответствующее количество закрашенных лепестков m. Запускаем алгоритм по n от 0 и до момента пока m не будет равно 2018. (для нечетных n крутим алгоритм не 2n, а n раз).

Для ответа на третий вопрос запускаем алгоритм 2 дальше, пока m для нечетных n не превысит 2018 и делаем выводы глядя в две окрестности m=2018.


Edited at 2017-12-11 15:04 (UTC)

> Запускаем алгоритм по n от 0 и до момента пока m не будет равно 2018. (для нечетных n крутим алгоритм не 2n, а n раз).

А кто сказал, что у этой задачи конечное число решений?
Пока незачёт...

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

А для ответа на вопрос 2 нам вообще не нужно знать об иных решениях:
"Для ответа на второй вопрос создаем дополнительный массив в который пишем по 2 значения: количество лепестков n и соответствующее количество закрашенных лепестков m. Запускаем алгоритм по n от 0 и до момента пока m не будет равно 2018."

Edited at 2017-12-12 12:18 (UTC)

Ответ на вопрос 1:
1009.

Код для php:
https://yadi.sk/i/r4P1eomJ3QYUuf



Edited at 2017-12-12 12:12 (UTC)

Ой, забыл про первый лелесток, который закрашен произвольно, итого получается
ответ1: 1010
ответ2: 4034
ответ3: таки да, возможно, например: 6051

Обоснование алгоритмов расчета и логики, достаточной для ответов на поставленную задачу, выше.

Судя по ответам, есть "немашинное" решение:) Интересно будет его увидеть.

Edited at 2017-12-12 12:15 (UTC)

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

Да, но задача поставлена явно локально, именно для числа 2018. Такую задачу проще и эффективнее всего решить машинным способом (+ доказательство повторения закрашиваний с шага 2n, разумеется, - без этого машинный способ не достаточен).

Так или иначе, уже стало интересно решить ее в общем случае.

Поздравляю,
Дмитрий, напишите мне на sp@kaspersky.com, я вам приз вышлю :)

?

Log in

No account? Create an account