Бьют двое часов

[Doctor Boom]

Мне выложить решение моей усложненной задачи или другие тоже заинтересовались?

[wrest]

Doctor Boom в сообщении #1611459 писал(а):

Мне выложить решение моей усложненной задачи или другие тоже заинтересовались?

Ну у меня получилось, что часы били немного меньше 15 минут
До элегантной формулы я, впрочем, не добрался.

Мне кажется это хорошо бы в олимпиадный раздел и более обобщенно - имеются прогрессии с первым членом нулевым и разностями $d_i$ (у нас это $d_1=2,d_2=3,d_3=5,d_4=7$) и надо найти мощность объединенного множества их членов если количество членов каждой прогрессии $t$ или наоборот, чему равно $t$ если мощность множества равна $n$

[wrest]

Для проверки формул, кто какие придумает, программа на pari/gp:
bom(v,t)=my(b=Set(0));for(i=1,#v,b=setunion(b,Set(vector(t-1,n,n*v[i]))));return(#b)
На вход подаём вектор из темпов боя часов (секунд между ударами), и какой час пробить. Функция возвращает количество слышимых ударов. Если в коде функции убрать решётку, будет возвращать вектор из номеров секунд когда происходили удары.
Если часов двое, одни бьют раз в 2 секунды, вторые раз в 3 секунды и надо пробить 11 часов, то запускаем так:
? bom([2,3],11)
%1 = 18
?
Норм работает где-то до миллионов часов, дальше памяти надо больше гигабайта. Ниже считает полторы секунды:
? bom([2,3,5,7],10^6)
%1 = 2999999
?

pari/gp online: https://pari.math.u-bordeaux.fr/gp.html

[Doctor Boom]

wrest
У меня вышло 119 часов, у вас так же?

-- 30.09.2023, 01:13 --

Ваша прога со мной согласна

-- 30.09.2023, 01:14 --

wrest в сообщении #1611495 писал(а):

До элегантной формулы я, впрочем, не добрался.

А как решали?

-- 30.09.2023, 01:17 --

Я вообще удивлен, что ответ имеется, т.к. 357 ударов наугад выбрал Если бы было 356 или 358 уже бы не было решения

[wrest]

Doctor Boom в сообщении #1611793 писал(а):

Ваша прога со мной согласна

Ну так она ж непосредственно считает, просто вычёркивая дубли.

-- 30.09.2023, 01:23 --

Doctor Boom в сообщении #1611793 писал(а):

А как решали?

Так прогой и решал.
Я покрутился туда и сюда... Вижу, что примерно треть и вокруг неё пляшет (а в вашем примере точно треть, $119=357\dfrac13$).
Но формула не вышла из меня.

[Doctor Boom]

wrest
Читерство А я решал как и прошлую легкую задачу, методом последовательных приближений (только через калькулятор)

[wrest]

Doctor Boom
Ну у нас выходит сколько-то (четыре в вашей постановке) интервалов времени (секунд). Первый -- пока бьют быстрые часы. С нулевой по $d_1t$=$2t$-ю секунду. В этом интервале ударами будут числа (номера секунд) не взаимно простые с $\prod \limits _{i>0} d_i=2\cdot 3 \cdot 5 \cdot 7=210$. Начиная с $d_1t+1=2t+1$ секунды по $d_2t=3t$-ю секунду ударами будут числа (номера секунд) не взаимно простые с $\prod \limits _{i>1} d_i =3 \cdot 5 \cdot 7=105$ и т.п., последний интервал (в нашем случае) с $5t+1$ по $7t$, там нужные нам числа только те, которые делятся на $7$ Вот и надо их посчитать, в каждом интервале... и записать красивую формулу.

[Doctor Boom]

wrest
Здорово, а как бы вы считали, ручками, на олимпиаде?
Я делал так, сначала $357-1=356$, секунду запоминаем. Потом $356$ нацело делим на $4$, получаем некое $a_0$, считаем $4a_0$ и потом из него вычитаем сначала все попарные совпадения секунд, потом по три, но уже складываем и т.д. с помощью формулы включений/исключений, получаем некое конечное $b_1$, потом нацело делим $356-b_1$ на $4$ и прибавляем к $a_0$, получаем $a_1$, и далее повторяем до тех пор, пока не найдем некое $b_i=356$, и тогда конечный ответ $a_i+1$

-- 30.09.2023, 04:46 --

wrest в сообщении #1611799 писал(а):

...и записать красивую формулу

эх, математики

[wrest]

Doctor Boom в сообщении #1611805 писал(а):

Здорово, а как бы вы считали, ручками, на олимпиаде?

Ну формула-то у меня есть, просто она пока не помещается на полях этого форума

[wrest]

В общем, формула такая.
Обозначим целочисленное деление обратным слэшем. Т.е.$a$\$b=\lfloor \frac ab \rfloor$.
Тогда количество ударов для случая четырёх бьющих часов с темпами в 2,3,5 и 7 секунд будет
n(t)=4*(t-1)-3*((t-1)\7)-2*((t-1)\5)-(t-1)\3+(t-1)\15+(t-1)\21-(t-1)\105+2*((t-1)\35)+1
Надо как-то свернуть её поплотнее, пока не придумал как именно.
Так уж и быть, запишу тексом

$$n(t+1)=4t-3\left\lfloor \dfrac t7\right\rfloor -2\left\lfloor \dfrac t5\right\rfloor - \left\lfloor \dfrac t3\right\rfloor +\left\lfloor \dfrac {t}{3\cdot 5}\right\rfloor + \left\lfloor \dfrac {t}{3 \cdot7}\right\rfloor +2 \left\lfloor \dfrac {t}{5 \cdot 7}\right\rfloor - \left\lfloor \dfrac {t}{3 \cdot 5 \cdot 7}\right\rfloor +1$$

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

Поясню как дошёл до жизни такой...
Я смотрел на то как растёт функция $n(t)$. Первые разности $D(t)=n(t+1)-n(t)$ равны $4, 4, 3, 4, 2, 3, 1, 4, 3,\dots$ Длина цикла равна $3\cdot 5 \cdot 7=105$ т.е. $D(i)=D(105k+i), k \in \mathb Z$
Единицы стоят там, где количество часов кратно 7. То есть единиц всего
$c1(t)=\left \lfloor \dfrac {t-1}{7} \right \rfloor$
Двойки там где делится на 5 за исключением номеров делящихся на 7, т.е. двоек всего
$c2(t)=\left \lfloor \dfrac {t-1}{5} \right \rfloor - \left \lfloor \dfrac {t-1}{5 \cdot7} \right \rfloor$
Тройки там, где номер делится на 3 за исключением тех где делится на 5 или 7, то есть
$c3(t)=\left \lfloor \dfrac {t-1}{3} \right \rfloor - \left \lfloor \dfrac {t-1}{3 \cdot 5}\right \rfloor - \left \lfloor \dfrac {t-1}{3 \cdot7}\right \rfloor+\left \lfloor \dfrac {t-1}{3 \cdot 5 \cdot7} \right \rfloor$
Ну а четвёрки - всё остальное.
$c4(t)=t-(c1(t)+c2(t)+c3(t))$
Осталось только сложить и добавить первый удар в нулевую секунду:
$n(t)=1\cdot c1(t)+2\cdot c2(t)+3 \cdot c3(t) + 4 \cdot c4(t) +1$

[wrest]

Doctor Boom в сообщении #1611805 писал(а):

а как бы вы считали, ручками, на олимпиаде?

Ну вот на калькуляторе бы и считал, хотя нацело делить вроде несложно и на бумажке.
Но это ещё конечно не олимпиадный уровень. Т.е. уровень обобщения пока недостаточный.

-- 30.09.2023, 20:42 --

Gepidium и Doctor Boom
Спасибо вам за задачу, интересно получилось.