Как решить эту задачу без «подбора» значений?

Question

[sinee-pero]

Здравствуйте!
Простите, за возможно столь глупый вопрос, но существует ли универсальный подход к решению этой задачи, например для 18-ти, 54-х и т.д. значных циферблатов? без перебора значений, естественно

Answer 1

[Евгений Шатунов]

Легко. Но для этого на циферблат надо посмотреть под разными углами.

Сперва давай поглядим на него как на арифметическую прогрессию. А1 == 1; А12 == 12; D == 1.
Формула суммы прогрессии: S = (A1 + An) * n / 2;

Вычисляем сумму нашего ряда, она равна 78. И дальше все становится очень просто.

Теперь давай посмотрим на циферблат как на циферблат. У него 12 значений, связанных в кольцо.
Проведя линию и поделив циферблат на две части, мы как бы создаем две области арифметических прогрессий.
При чем сумма сумм этих прогрессий будет равна той сумме, что мы уже посчитали.
Стало быть, нам достаточно найти такой участок на циферблате, сумма чисел которого была бы равна ровно 39 - половине уже рассчитанной сверху суммы. Иначе условие задачи не выполнить.

Выходит так, что элементов в искомой последовательности у нас становится не 12, а 6. D тот же, а вот A1 и A6 у нас неизвестные. Найти их можно через все ту же формулу суммы.

39 == (A1 + A6) * 6/2
13 == A1 + A6
A6 == A1 + D*5
13 == 2*A1 + 5
8 == 2*A1
A1 == 4
A6 == 4 + 5 == 9

Всё. Первая группа - это [4..9], вторая - это [1..3,10..12], суммы обеих последовательностей будут равны 39, а вместе - 78.

UPD:
Почему именно 6 элементов... Смотрим.

Для множества циферблата сумма такова:
78 == ( 1 + 12 ) * 12 / 2

Для подмножества должна выполняться такая сумма:
39 == ( 2A1 + N - 1 ) * N / 2

Определим N из тожественного равенства двух сумм с поправкой что от первой нам надо только половину.
( 1 + 12 ) * 12 / 4 == ( 2A1 + N - 1 ) * N / 2

Замечаем тождественность составляющих выражения и теперь рассмотрим это равенство как систему уравнений:
1 + 12 == 2A1 + N - 1
12 / 4 == N / 2

Вуаля!
N == 6; а из первого равенства очень легко вывести A1, который равен 4.

Comments

[TomasHuk]

Я точно также думал, но застопорился на количестве членов в прогрессии. Почему их ровно половина от общего числа?

[DancingOnWater]

>>ыходит так, что элементов в искомой последовательности у нас становится не 12, а 6
Не факт

[DancingOnWater]

Более того, 9+11 +10 =39

[DancingOnWater]

Все, спекся к концу рабочего дня, считаю плохо

[Евгений Шатунов]

DancingOnWater: Все норм, у всех бывает.
TomashUA: Это заставляет меня отвлекаться от работы! )) Если ни кто не ответит до вечера, подумаю и отвечу.

[TomasHuk]

Кстати, я проверял для 54 цифр. Все сходится при n=27, т.е. половина от всего количества. Поэтому, собственно и спросил.

[Евгений Шатунов]

TomashUA: Может облажался, но вот... обновил пост с доказательством что элементов именно 6 для циферблата на 12 чисел.

[Alew]

А из чего правая часть следует? 39 == ( 2A1 + N - 1 ) * N / 2

[Евгений Шатунов]

Alew: Выше обновления написано же.

[DancingOnWater]

>>Замечаем тождественность составляющих выражения и теперь рассмотрим это равенство как систему уравнений:
Нет, так делать нельзя. У вас два неизвестных и одно уравнение. Однозначно оно не решается

[Евгений Шатунов]

DancingOnWater: Предлагай варианты, не стесняйся, конструктив приемлем всегда. :)
Лично я не вижу оснований для "так делать нельзя".

[DancingOnWater]

Евгений Шатунов: Ниже я привел строгое доказательство. Кстати, его можно обобщить для циферблата с любым количеством чисел.

Answer 2

[Евгений Хлебников]

Для произвольного циферблата :
1 2 3 4…K : получаем арифметическую прогрессию. В которой K – максимальное число на циферблате.
1. Надо убедиться, что сумму арифметической прогрессии можно разделить на 2 части
Сумма арифметической прогрессии : (1+K)*K/2.
Сумма её части(половина) – (1+K)*K/4 – должна быть целым числом.
Из этого следует вывод, что K=4N или K=4N-1 где N – любое число.
2. У нас есть условие, что мы делим циферблат прямой линией. Это значит, что в одной из половин остается часть прогрессии от члена под номером X(в нашем случае член под номером X равен X) до члена Y.
3. Из доказательства формулы суммы арифметической прогрессии (сумма первого члена с последним равна сумме второго члена с предпоследним и т.д.) мы видим, что для поиска решения(нужной суммы) нам надо отсечь p членов с начала и с конца прогрессии.
Для 4N первый член X=1+p, последний Y=4N-p
Для 4N-1 добавим (в прогрессию, не на циферблат) цифру 0. Первый член нужной прогрессии соответственно X=0+p, последний : 4N-1-p

Для 4N:
Сумма необходимой нам последовательности от X до Y : (1+p+4N-p)(4N-2p)/2
Половина суммы от 1 до 4N :4N*(4N+1)/4
4N*(4N+1)/4=(1+p+4N-p)(4N-2p)/2
4N*(4N+1)/2=(4N+1)*(4N-2p)
2N=4N-2p
2p=2N. p=N количество членов последовательности равно 2N
Соответственно первый член для 4N: N+1, последний : 4N-N
Аналогично считаются члены и для 4N-1

Answer 3

[DancingOnWater]

Заход у Евгений Шатунов был правилен, но вот обоснования, что их 6 - нет. А это самое интересное!

Как показано выше, сумма у нас должна быть 39.

Рассмотрим ряд, который не переходит через 12, т.е. является арифметической прогрессией. Вновь вернемся к ее сумме и представим ее в общем виде:
S = k*n ,
где k и n целые числа. При этом есть два варианта: k - это сумма первого и последнего элемента, а 2n - это количество чисел в последовательности, либо наоборот. В общем случае количество возможных решений определяет число комбинаций множителей итоговой суммы S.

В нашем случае 39 имеет только одно разложение (39 = 13*3) 13 элементов у нас быть не может по условию задачи, значит это сумма,а следовательно число элементов n=2*3=6.

Comments

[Дмитрий Ковальский]

Вы видимо торопились ответить. Поправьте пожалуйста ошибки. Их много и некоторые сильно корёжат смысл описанного. При разделении циферблата на 2 части, если одна половина не переходит через 12,то другая перейдет.

[DancingOnWater]

dmitryKovalskiy: ну и пусть переходит, ее не удобно рассматривать

Answer 4

[Adamos]

Как-то попадалась похожая задача, которая имела успешное решение с линией, разделяющей число 12 на 1 и 2 ;)
А так - простейшее решение именно перебором. Поскольку перебор-то невелик: считаем сумму, находим половину, предполагаем, что один из концов линии между 12 и 1, проверяем, можно ли куда-то поместить второй конец, затем перемещаем первый между 1 и 2, снова проверяем второй и т.д. Даже для очень больших циферблатов компьютер решит такую задачу за миллисекунды.

Если хочется интеллекта, пожалуйста: на первом проходе находим единственное решение либо два ближайших неподходящих варианта. На втором получается, что мы из суммы вычитаем то число, на котором начиналась последовательность, но добавляем по 1 на каждый член этой последовательности. Сравниваем результат с теми цифрами, в которые упирается второй конец... в общем, подозреваю, что расчет будет дольше, чем по выше предложенному примитиву.

Answer 5

[cro096]

а есть и общий способ, для циферблатов с четным количеством чисел- решение простое- берем середину между 1 и N (12 для простых часов) и центр циферблата, проводим линию, и через центр строим перпендикуляр к этой линии. все. решение готово.
сумма 6+7 (6,5-0,5 + 6,5+0,5 ) + 5+8 (6,5-1,5 + 6,5+1,5) + 4+9 ( 6,5 -2,5 + 6,5+ 2,5) =
3+10 (6,5-3,5 + 6,5+3,5) +2+11(6,5-4,5+6,5+4,5) + 1+12(6,5-5,5+6,5+5,5).
решение распространяется на любой циферблат с четным количеством чисел.
Если чисел нечетное количество на циферблате- то прямую строим через максимум (13 напрямер) и к ней строим перпендикуляр через центр. доказательство аналогично по структуре.

Comments

[Adamos]

По условиям задачи разделительная линия совершенно не обязательно проходит через центр.

[cro096]

по условиям да, это не требуется, но если сумма от 1 до N и эта сумма четная (N кратно 4 или N+1 кратно 4) то эта линия может проходить и через центр. автор просил алгоритм без переборов и универсальный, предложенный мной удовлетворяет этим требованиям, хотя он и не единственный. правда- придумайте проще.