(Оффтоп)
что-то никто ничего не пишет
![Neutral :|](./images/smilies/icon_neutral.gif)
, а задачка-то интересная!
Чуть менее тривиальный пример -
![$n=30$ $n=30$](https://dxdy-02.korotkov.co.uk/f/9/a/0/9a0e729f7ff81c334e6650acd86df52982.png)
- тоже четное, но степень
![$2$ $2$](https://dxdy-04.korotkov.co.uk/f/7/6/c/76c5792347bb90ef71cfbace628572cf82.png)
здесь уже 1.
Пример с начетным модулем мне пока построить не удалось, но я еще не подходил к компу (а так призываю всех попробовать!), сейчас напишу, почему это не просто.
Пусть
![$M$ $M$](https://dxdy-04.korotkov.co.uk/f/f/b/9/fb97d38bcc19230b0acd442e17db879c82.png)
- натуральное,
![$d|M,d>1$ $d|M,d>1$](https://dxdy-02.korotkov.co.uk/f/9/c/8/9c887a58700ad70c665e63125d1f37d982.png)
. Чтобы покрыть все
![$\mathbb{Z}$ $\mathbb{Z}$](https://dxdy-04.korotkov.co.uk/f/b/9/4/b9477ea14234215f4d516bad55d011b882.png)
, достаточно покрыть
![$\mathbb{Z}_M$ $\mathbb{Z}_M$](https://dxdy-03.korotkov.co.uk/f/2/6/e/26e10b98b4d5a406a7e9f8f364db609782.png)
.
Прогрессия
![$x+dt, t\in\mathbb{Z}$ $x+dt, t\in\mathbb{Z}$](https://dxdy-02.korotkov.co.uk/f/5/b/8/5b87080046a3583c1a8bb38fa63fc4e582.png)
покрывает
![$\frac{M}{d}$ $\frac{M}{d}$](https://dxdy-04.korotkov.co.uk/f/7/c/8/7c8ddd5f6c88a532b7d48fc2a2b4647782.png)
чисел.
Прогрессии
![$x+at, y+bt, t\in\mathbb{Z}$ $x+at, y+bt, t\in\mathbb{Z}$](https://dxdy-01.korotkov.co.uk/f/0/c/9/0c9232dc7ff99271cd6c9da150d63aac82.png)
пересекаются только если
![$\gcd(a,b)|x-y$ $\gcd(a,b)|x-y$](https://dxdy-04.korotkov.co.uk/f/3/6/7/367ff6091fc361e5ed0248a93de3bd5f82.png)
, причем в этом случае они пересекаются по прогрессии с коэффициентом
![$\mathrm{lcm}(a,b)$ $\mathrm{lcm}(a,b)$](https://dxdy-03.korotkov.co.uk/f/a/6/5/a657209ae4f817d5a1f271cac01b81fb82.png)
.
Будем считать, что мы можем у всех прогрессий
![$x_d+dt$ $x_d+dt$](https://dxdy-01.korotkov.co.uk/f/4/1/6/4162656b6950860f875a72edb09e1c9182.png)
можем выбрать
![$x_d$ $x_d$](https://dxdy-04.korotkov.co.uk/f/3/b/8/3b8a8eaa3eec616bd79eae9c0f148b4682.png)
так, что если у любых двух различных прогрессий коэффициенты
![$d$ $d$](https://dxdy-03.korotkov.co.uk/f/2/1/0/2103f85b8b1477f430fc407cad46222482.png)
не взаимно просты, то прогрессии не пересекаются. Это вряд ли возможно в общем случае, но, похоже, в нашем случае, это оказывается близко к истине.
Обозначим
![$C_d=\{a:(\exists t) a\equiv x_d+dt \pmod M\}$ $C_d=\{a:(\exists t) a\equiv x_d+dt \pmod M\}$](https://dxdy-03.korotkov.co.uk/f/a/b/c/abc91a6a6e50088c094db166378d529e82.png)
. Надо, чтобы
![$U=\bigcup\limits_{d>1}=\mathbb{Z}_M$ $U=\bigcup\limits_{d>1}=\mathbb{Z}_M$](https://dxdy-01.korotkov.co.uk/f/c/9/f/c9f727802f4863594ba43eef020ee4a882.png)
.
В предположении выше, мы можем по формуле включений исключений оценить число элементов в
![$U$ $U$](https://dxdy-03.korotkov.co.uk/f/6/b/a/6bac6ec50c01592407695ef84f45723282.png)
:
![$|U|=\sum\limits_{d}C_d-\sum\limits_{d_1<d_2}|C_{d_1}\cap C_{d_2}|+...+(-1)^{k-1}\sum\limits_{d_1<...<d_k}|C_{d_1}\cap ...\cap C_{d_k}|+...$ $|U|=\sum\limits_{d}C_d-\sum\limits_{d_1<d_2}|C_{d_1}\cap C_{d_2}|+...+(-1)^{k-1}\sum\limits_{d_1<...<d_k}|C_{d_1}\cap ...\cap C_{d_k}|+...$](https://dxdy-02.korotkov.co.uk/f/d/6/e/d6e46249c50abe2de66016d05426936382.png)
По предположению
![$C_{d_1}\cap C_{d_2}$ $C_{d_1}\cap C_{d_2}$](https://dxdy-04.korotkov.co.uk/f/7/3/b/73b96efe25e1b383543fde9b4a7d6dfb82.png)
непусто только если
![$d_1\perp d_2$ $d_1\perp d_2$](https://dxdy-01.korotkov.co.uk/f/4/6/9/469a625d1e98fccbe5680cfdd2d1efc082.png)
, и тогда
![$C_{d_1}\cap C_{d_2}=С_{d_1d_2}$ $C_{d_1}\cap C_{d_2}=С_{d_1d_2}$](https://dxdy-03.korotkov.co.uk/f/e/9/8/e98eedd7c4f462134dd44333c04ff85c82.png)
(не тот
![$C_{d_1d_2}$ $C_{d_1d_2}$](https://dxdy-04.korotkov.co.uk/f/3/3/7/337fed9de02a1034cefc19b10f76a44e82.png)
, обозначенный выше, а просто некий класс вычетов по модулю
![$d_1d_2$ $d_1d_2$](https://dxdy-01.korotkov.co.uk/f/c/d/d/cdd4a8b5af60922b0f8b9286e44f888c82.png)
, надеюсь, это не вызовет проблем
![Smile :-)](./images/smilies/icon_smile.gif)
)
Тогда
![$|U|=\sum\limits_{P_1(d)}|C_d|-\sum\limits_{P_2(d)}|C_d|+...+(-1)^{k-1}\sum\limits_{P_k(d)}|C_d|+...$ $|U|=\sum\limits_{P_1(d)}|C_d|-\sum\limits_{P_2(d)}|C_d|+...+(-1)^{k-1}\sum\limits_{P_k(d)}|C_d|+...$](https://dxdy-01.korotkov.co.uk/f/4/d/6/4d6e4c087fbc2c76e3fafd63e00fc37382.png)
,
где
![$P_k(d)$ $P_k(d)$](https://dxdy-01.korotkov.co.uk/f/8/c/a/8ca9b7642743cfd5641da90e7a193cce82.png)
означает "
![$d$ $d$](https://dxdy-03.korotkov.co.uk/f/2/1/0/2103f85b8b1477f430fc407cad46222482.png)
содержит как минимум
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
простых различных делителей".
Положим
![$M=\prod\limits_{k=1}^sp_k^{a_k}$ $M=\prod\limits_{k=1}^sp_k^{a_k}$](https://dxdy-03.korotkov.co.uk/f/6/b/1/6b1a8e1a3f979415c7a370de84b7cf1a82.png)
. Далее ограничимся случаем
![$s=4$ $s=4$](https://dxdy-03.korotkov.co.uk/f/6/7/9/6792bc4ea1023251cf0965ae587c2c5382.png)
и будем считать, что в формуле включений-исключений разность 3-го и 4-го слагаемого неотрицательна
![Smile :-)](./images/smilies/icon_smile.gif)
Тогда
![$|U|\geqslant \sum\limits_{d:d=p^k,k>0}\frac{M}{d}\geqslant M\Leftarrow$ $|U|\geqslant \sum\limits_{d:d=p^k,k>0}\frac{M}{d}\geqslant M\Leftarrow$](https://dxdy-03.korotkov.co.uk/f/6/3/7/6371087df32e01e231f95f206c42fba282.png)
![$L_s=\sum\limits_{k=1}^s\sum\limits_{j=1}^{a_k}\frac{1}{p_k^j}=\sum\limits_{k=1}^s\frac{1-p_k^{-a_k}}{p_k-1}\geqslant 1$ $L_s=\sum\limits_{k=1}^s\sum\limits_{j=1}^{a_k}\frac{1}{p_k^j}=\sum\limits_{k=1}^s\frac{1-p_k^{-a_k}}{p_k-1}\geqslant 1$](https://dxdy-03.korotkov.co.uk/f/e/d/3/ed3fa8e579cc81662a1c3f52770763bd82.png)
Если устремить
![$a_k\to\infty$ $a_k\to\infty$](https://dxdy-04.korotkov.co.uk/f/3/6/e/36e73f0c9694e5104dbceb921088bc4682.png)
, то
![$L_4=\sum\limits_{k=1}^s\frac{1}{p_k-1}=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{10}=1+\frac{1}{60}>1$ $L_4=\sum\limits_{k=1}^s\frac{1}{p_k-1}=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{10}=1+\frac{1}{60}>1$](https://dxdy-04.korotkov.co.uk/f/3/b/a/3ba98d135f3c2c833dee137225321e4482.png)
.
![$L_3<1$ $L_3<1$](https://dxdy-02.korotkov.co.uk/f/d/1/1/d112714e35fbb30726ec622f3f03d9bb82.png)
, именно поэтому взято
![$s=4$ $s=4$](https://dxdy-03.korotkov.co.uk/f/6/7/9/6792bc4ea1023251cf0965ae587c2c5382.png)
![$L_4>1\Leftrightarrow \sum\limits_{k=1}^4\frac{p_k^{-a_k}}{p_k-1}<\frac{1}{60}$ $L_4>1\Leftrightarrow \sum\limits_{k=1}^4\frac{p_k^{-a_k}}{p_k-1}<\frac{1}{60}$](https://dxdy-02.korotkov.co.uk/f/9/9/4/9943f954e518dd079f887ee3504ad1a382.png)
.
Подбором на компе у меня получились оптимальные
![$a_k=5;3;2;1$ $a_k=5;3;2;1$](https://dxdy-02.korotkov.co.uk/f/5/6/b/56b9cfd6481f7671e82112048ab59dc582.png)
, т.е.
![$M=3^5\cdot 5^3\cdot 7^2\cdot 11^1\approx 1,6\cdot 10^9$ $M=3^5\cdot 5^3\cdot 7^2\cdot 11^1\approx 1,6\cdot 10^9$](https://dxdy-02.korotkov.co.uk/f/5/2/0/520ef128f45774236105ec80a68d270882.png)
.
Число
![$M$ $M$](https://dxdy-04.korotkov.co.uk/f/f/b/9/fb97d38bcc19230b0acd442e17db879c82.png)
довольно большое, потому явно покрытие всего
![$\mathbb{Z}_M$ $\mathbb{Z}_M$](https://dxdy-03.korotkov.co.uk/f/2/6/e/26e10b98b4d5a406a7e9f8f364db609782.png)
подобрать трудно. Но зато получается, что искомое ТС
![$m(M)=\infty$ $m(M)=\infty$](https://dxdy-01.korotkov.co.uk/f/c/a/e/cae83051382af5b53182e5106a00325682.png)
, значит и для всех
![$m(x)=\infty$ $m(x)=\infty$](https://dxdy-04.korotkov.co.uk/f/b/9/c/b9cae021971c57195508190e6b45117482.png)
, после чего остается хоть перебором на компе найти
![$m(x)$ $m(x)$](https://dxdy-03.korotkov.co.uk/f/a/8/d/a8d4da3f136efc85b25c5d38ab0497d682.png)
для конечного числа
![$x<M$ $x<M$](https://dxdy-01.korotkov.co.uk/f/0/6/3/063180ff77cc9685aa91c7190038cd8a82.png)
, после чего задача становится теоретически неинтересной
![Smile :-)](./images/smilies/icon_smile.gif)
Также получается, что
![$M$ $M$](https://dxdy-04.korotkov.co.uk/f/f/b/9/fb97d38bcc19230b0acd442e17db879c82.png)
- скорее всего минимальный аргумент, при котором
![$m(x)$ $m(x)$](https://dxdy-03.korotkov.co.uk/f/a/8/d/a8d4da3f136efc85b25c5d38ab0497d682.png)
бесконечна. Но тоже строго обоснования еще нет. Вот наше дело найти явное покрытие
![$\mathbb{Z}_M$ $\mathbb{Z}_M$](https://dxdy-03.korotkov.co.uk/f/2/6/e/26e10b98b4d5a406a7e9f8f364db609782.png)
или обосновать его существование строго.
чем не устраивают две прогрессии:
![$(k,x)=(1,1);(1,2)$ $(k,x)=(1,1);(1,2)$](https://dxdy-01.korotkov.co.uk/f/c/b/c/cbc2027fb47dffacb65d47527ce28f6482.png)
?
Требуются прогрессии только с нечетными неединичными коэффициентами.