Задача про полоски с дырками

[anahronizm]

waxtep в сообщении #1716726 писал(а):

Пять вилок текущая версия программы на моем нотике будет считать несколько дней, а шесть - несколько лет

Я в шоке. Нет, я понимаю мозгой, что бывают процессы, которые даже комп делает долго, но не представлял, что эта задачка может быть такой впечатляющей.
Вы молодец !
Вы все, кто участвовал и придумывал - все молодцы! Мне бы такие мозги...
Я в шоке!
Даже читать интересно, хоть я и мало что понимаю! Как фантастический роман, честно.
Извините, я верно понял, что такая раскладка не описана в математике в виде формул ?
Ну, когда ставится задача забить дырками полоску заданной длины с участием заданного количества вилок ?
Да чтобы можно было задать и размер дырки и размер интервала.
Или вообще, задать количество зубьев в вилках...
Я уж, пока гайки крутил, думал, какие условия можно наложить, чтобы обеспечить невозможность полного забития дырками при любом количестве вилок.

[waxtep]

anahronizm в сообщении #1716741 писал(а):

Извините, я верно понял, что такая раскладка не описана в математике в виде формул ?
Ну, когда ставится задача забить дырками полоску заданной длины с участием заданного количества вилок ?

Почему же, задача ставится, она с переднего края науки, теории чисел. Здесь уважаемый mihaild приводил пример работы по теме:

mihaild в сообщении #1716332 писал(а):

Например если натуральные числа можно покрыть прогрессиями с разностями $a_1 < a_2 < \ldots < a_k$, то хотя бы одно из $a_i$ делится либо на 2 либо на 3 https://arxiv.org/abs/1703.02133 .

Для меня статься выглядит тяжело, честно скажу; не пытался ее пройти, лишь листал. Видимо, явная формула для максимально возможного покрытия в общем случае неизвестна. Конкретно для Вашей задачи, для одной-четырех вилок получаются значения $4,10,24,41$, что довольно близко к $2k(k+1)=4,12,24,40$ для малых количеств вилок $k$.

anahronizm в сообщении #1716741 писал(а):

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

Вот Вы видимо как раз их и подобрали удачно ни один из периодов $вида 6n\pm1=5,7,11,13,17,19\ldots$ не делится ни на два, ни на три, что в свете приведенной выше статьи означает ту самую невозможность. В целом же:

mihaild в сообщении #1716459 писал(а):

По крайней мере для покрытия всего $\mathbb N$ это вопрос очень сложный. В частности, никто не знает, существует ли покрытие без прогрессий с четной разностью.

Наконец, насчет большого времени счета. Я делаю в лоб, по сути так же двигаю полоски с дырками относительно друг друга, только в программе. Первый проход первой вилки оставляет рисунок проколов OXOXO с периодом $5$; второй проход - OOXOXOO с периодом $7$; совместно они дают рисунок, повторяющийся через каждые $5\cdot7=35$ клеток. Добавляя еще две вилки, надо умножить длину общего периода еще на $11\cdot13\cdot17\cdot19=46\,189$; с четвертой вилкой сложнее, хочется умножить на $23\cdot25$, но так не надо. У нас уже есть период $5$, и нужно рассмотреть пять разных возможных положений проколов первого прохода первой вилки относительно проколов второго прохода четвертой вилки. И так далее. Для десяти вилок длина общего периода $\approx6,8\cdot10^{23}$ в районе числа Авогадро, это много, очень много.

mihaild в сообщении #1716499 писал(а):

Я пока придумал только динамику по маскам, но это уже на 10 вилках посчитать без шансов.

mihaild, Вы как-то изящнее делаете видимо, раз до десяти вилок добрались? Я пока боюсь соваться даже в пять.

-- 31.01.2026, 14:49 --

waxtep в сообщении #1716779 писал(а):

хочется умножить на $23\cdot25$, но так не надо

Или как раз надо, я уж тут сам запутался немного

-- 31.01.2026, 15:17 --

Ну да, для четырёх вилок прогрессии с взаимнопростыми периодами, кроме периода $5$ можно сложить в произвольную кучу, любая комбинация на общем периоде встретится. А потом наложить прогрессию с периодом $5$ в пяти возможных положениях (в силу симметрии задачи достаточно в трех). Это можно аккуратно обобщить на случай любых не взаимнопростых периодов

[mihaild]

waxtep в сообщении #1716779 писал(а):

Вот Вы видимо как раз их и подобрали удачно ни один из периодов $вида 6n\pm1=5,7,11,13,17,19\ldots$ не делится ни на два, ни на три, что в свете приведенной выше статьи означает ту самую невозможность.

Но тут у нас две последовательности с каждым периодом (на фиксированном расстоянии), а не одна.

waxtep в сообщении #1716779 писал(а):

Вы как-то изящнее делаете видимо, раз до десяти вилок добрались?

Я и не добрался. Это грубая прикидка.
Я рассматривал только для полоски длины $8n + 4$ из условия, и там можно динамику по маскам (что проколото). Количество разных вариантов прокола растёт сильно медленее, чем $2^{\text{длина полоски}}$ - для 12 (два прохода одной вилкой) я получил 44 маски, для 20 - 3535, для 28 - 357871, для 36 - 42540036. Поэтому вроде бы если как следует оптимизировать код, может быть можно еще немного продвинуться. Но уверенности нет.

[waxtep]

mihaild в сообщении #1716815 писал(а):

Но тут у нас две последовательности с каждым периодом (на фиксированном расстоянии), а не одна.

В самом деле; значит, не доказана ни возможность покрытия $\mathbb{N}$ таким набором прогрессий, ни противоположное.

mihaild в сообщении #1716815 писал(а):

Я рассматривал только для полоски длины $8n + 4$ из условия, и там можно динамику по маскам (что проколото). Количество разных вариантов прокола растёт сильно медленее, чем $2^{\text{длина полоски}}$ - для 12 (два прохода одной вилкой) я получил 44 маски, для 20 - 3535, для 28 - 357871, для 36 - 42540036. Поэтому вроде бы если как следует оптимизировать код, может быть можно еще немного продвинуться. Но уверенности нет.

Я тоже прикидываю на бумаге возможности продвинуться чуть дальше, пока грустно. Можно так: в оптимальном покрытии (при $k\geqslant2$) гарантированно будет "островок" из четырех проколотых клеток, образованный в клетках $x,x+2$ первым проходом первой вилки и в клетках $x+1,x+3$ ее вторым проходом. К этому островку можно с любой из сторон пристроить прокол от одного из зубцов одного из проходов какой-то другой вилки, а далее уже с двух сторон аналогично. Вариантов, если не наврал, $2^{4k-5}\times(2k-2)!$, что чуть скромнее лобового подхода, но того же характера роста. Для двух вилок - $16$ вариантов, для трех - $3072$, для четырех - $1\,474\,560$ (это в несколько десятков раз шустрее лобового подхода, по идее), для пяти $\approx1,3$ миллиарда, для шести - два триллиона.

[waxtep]

waxtep в сообщении #1716989 писал(а):

в оптимальном покрытии (при $k\geqslant2$) гарантированно будет "островок" из четырех проколотых клеток, образованный в клетках $x,x+2$ первым проходом первой вилки и в клетках $x+1,x+3$ ее вторым проходом.

Корректнее, конечно, так: в оптимальном покрытии (при $k\geqslant2$) гарантированно будет "островок" из четырех проколотых клеток, образованный в клетках $x,x+2$ одним из проходов первой вилки и в клетках $x+1,x+3$ ее другим проходом.

И для $2,3,4$ вилок работает следующее эмпирическое правило для оптимального покрытия: колоть слева и справа от островка надо одинаковое количество раз. Речь только о первых уколах, ближайших к островку; далее он (исходный островок) вовсе необязательно окажется посередине покрытой полосы. Если это правило принять и для больших количеств вилок, объем расчета существенно снизится, тут уже пять, шесть, а то и семь вилок выглядят достижимыми за обозримое время счета. Попробую попозже.

Без картинок это конечно трудно воспринимать Тем не менее, как выглядят первые уколы для оптимального покрытия:
- две вилки, второй проход первой вилки выступает вправо: вилка 2, проход 1, правым зубцом слева; вилка 2, проход 2, правым зубцом справа;
- три вилки, второй проход первой вилки выступает вправо: вилка 3, проход 1, левым зубцом слева; вилка 2, проход 2, левым зубцом справа; вилка 2, проход 1, правым зубцом слева (она же дает "хороший" прокол левым зубцом справа!); вилка 3, проход 2, правым зубцом слева (она же дает "хороший" прокол левым зубцом справа);
- для четырех вилок кое-что аналогичное (три первых укола слева, три справа от островка; удачных совпадений лево/право, как для трех вилок, нет), но надо все таки картинки, попозже

[waxtep]

Под катом обещанная картинка оптимального покрытия для трех вилок. Я про него как раз немного наврал в словесном описании выше, здесь это видно наглядно.
Начинаем с зеленого островка в клетках 14-17, образованного двумя проходами первой вилки. Достраиваем островок слева и справа левым зубцом вилки 3 прохода 1 и левым зубцом вилки 2 прохода 2, соответственно. Островок расширяется до клеток 13-19, и рядом еще образуются мощные соседи 1-6 и 8-11. Достраиваем его слева и справа еще, правым зубцом вилки 2 прохода 1 и левым зубцом вилки 3 прохода 2. Получаем максимальное покрытие в клетках 1-24.

(картинка)

Если принять, что островок должен достраиваться слева и справа каждый раз, количество вариантов еще уменьшится до $2^{2k-2}\times(2k-2)!$, для пяти вилок это вполне обозримые $10\,321\,920$ вариантов; дальше, правда, снова миллиарды, триллионы и т.д. Этот перебор я наверное возьмусь запрограммировать, может быть, что-то еще удастся увидеть

-- 03.02.2026, 01:40 --

И аналогичная картинка для четырех вилок:

(Оффтоп)

[anahronizm]

waxtep в сообщении #1716779 писал(а):

anahronizm в сообщении #1716741

писал(а):
какие условия можно наложить, чтобы обеспечить НЕВОЗМОЖНОСТЬ полного забития дырками при любом количестве вилок Вот Вы видимо как раз их и подобрали удачно ни один из периодов $вида 6n\pm1=5,7,11,13,17,19\ldots$ не делится ни на два, ни на три, что в свете приведенной выше статьи означает ту самую невозможность.

Извините, не понял значения этой фразы.
Из всего вышеизложенного (всех сообщений) у меня сложилось впечатление, что для первоисходной задачи Вы и другие участники диалога доказали ВОЗМОЖНОСТЬ забития вилками полоски любой длины (согласно условий задачи).
Меня интересовало (и интересует), возможен ли вариант, что если мы представим полоску любой длины, то ВСЕГДА найдётся такая полоска, которую будет нельзя забить вилками при первоначальных условиях (соотношение длины полоски, количество вилок, размер их дырок и интервалов проходов).
Я пытался представить возможные ограничения для выполнения такой возможности, но у меня под рукой только карандаш и листок бумаги. (мозгов и времени тоже мало )
Если представить игру на расположение проходов вилок (именно при условии в задаче с длиной полоски, количество вилок, размер их дырок и интервалов проходов), то имеет ли смысл такая игра? Или такая игра обречена на то, что полное забитие досконально каждой полоски невозможно?
Извините, я не математик, поэтому не умею правильно выражаться и плохо понимаю профессиональные выкладки.

[wrest]

anahronizm в сообщении #1717062 писал(а):

доказали ВОЗМОЖНОСТЬ забития вилками полоски любой длины (согласно условий задачи).

Начиная с некоторой, да. Полоску длиной 12 двумя проходами вилкой XOX (первый проход с интервалом 2, т.е. ХОХООХОХОО.. вторая с интервалом 4 т.е. ХОХООООХОХОООО....) проколоть нельзя.

[waxtep]

anahronizm в сообщении #1717062 писал(а):

Извините, не понял значения этой фразы.
Из всего вышеизложенного (всех сообщений) у меня сложилось впечатление, что для первоисходной задачи Вы и другие участники диалога доказали ВОЗМОЖНОСТЬ забития вилками полоски любой длины (согласно условий задачи).
Меня интересовало (и интересует), возможен ли вариант, что если мы представим полоску любой длины, то ВСЕГДА найдётся такая полоска, которую будет нельзя забить вилками при первоначальных условиях (соотношение длины полоски, количество вилок, размер их дырок и интервалов проходов).

Попробую внести ясность:
1. В этой теме мы ничего не доказали; только игрались, баловались, приводили правдоподобные соображения;
2. В Вашей исходной задаче (полоска длиной $8k+4$ клеток, $k$ вилок, два прохода каждой) кажется правдоподобным, что наивной стратегий можно покрыть любую полоску при $k\geqslant9$; а оптимальной при $k\geqslant4$. Ни то, ни другое не доказано;
3. Отдельный интересный вопрос: можно ли в Вашей постановке задачи начиная с какого-либо количества вилок $k$ покрыть без зазоров бесконечную полоску. Это также неизвестно;
4. В целом, это задача из класса задач на покрытие натурального ряда (или его конечного куска) арифметическими прогрессиями. Такие задачи в общем случае очень сложные, изучаются в теории чисел.

Что касается игры, а как Вы себе это видите? Сколько игроков, два? И, типа, один играет на полное прокалывание полоски данной длины, а другой против?

[anahronizm]

waxtep в сообщении #1717073 писал(а):

Попробую внести ясность:

Большое спасибо - данные пояснения были своевременны (для меня лично). Знаю, что в математике важно уметь улавливать тонкости.
По поводу "игры": гипотетическое представление, что есть два игрока (очень умных). Один из них задаёт длину полоски (в задаче я использовал некое постепенное увеличение длины, но можно ведь использовать полоски любой длины), потом первый игрок (или противник) делает два прохода первой вилкой. Потом другой игрок делает два прохода второй вилкой, потом первый два прохода третьей вилкой и т.д. Для победы в игре можно поставить одну из задач:
- первым проткнуть последнюю дырку
- вынудить противника проткнуть последнюю дырку
- проткнуть большее количество дырок при наименьшем наложение дырок друг на друга и т.д.
Честно, не представляю, какие должны быть мозги, чтобы играть в такую игру. Может, на такое способны гении, но уж точно не я.

[waxtep]

anahronizm в сообщении #1717126 писал(а):

По поводу "игры"

Ага, спасибо, в целом понятно. Мне кажется, это еще дополнительный уровень сложности, а разобраться бы с тем, что уже есть!
Мне удалось посчитать пять вилок, ими можно проколоть $71$ клетку. Гарантии, что нельзя еще больше, - нету: использовал предположение из пары сообщений выше, что исходный "островок" из четырех проколотых клеток нужно наращивать чередуясь, то слева, то справа. Вот оно:

(71 прокол пятью вилками)

1, 4, 1, 7, 9, 1, 3, 1, 8, 2, 1, 7, 1, 5, 2, 1, 2, 1, 4, 5, 1, 2, 1, 2, 3, 1, 7, 1, 2, 6, 1, 4, 1, 8, 7, 1, 5, 1, 10, 3, 1, 8, 1, 9, 2, 1, 3, 1, 6, 2, 1, 2, 1, 5, 6, 1, 2, 1, 2, 10, 1, 3, 1, 2, 5, 1, 4, 1, 3, 10, 1

Это у меня считалось 45 минут на довольно приличном нотике; значит, шесть вилок на тех же мощностях - пара недель, эх.
Может быть можно что-то оптимизировать, как в идейном плане, так и в плане приемов программирования? Код немного так себе, но в принципе простой:

1. fforkisl(k)={ 
2. sb=4*(k^2+k+1);\\band size, hopefully enough 
3. B=vectorsmall(sb,i,0); 
4. bL=2*k^2+2*k+1; bR=bL+3; 
5. B[bL]=1; B[bL+2]=1; 
6. B[bR]=2; B[bR-2]=2; 
7. bL++; bR--; 
8.  
9. \\build initial 4-cell island 
10. i=1; s=1; lr=-1; d=6*i+2*s-3; 
11. B=vectorsmall(sb,x,if((x>bR||x<bL) & (B[x]==0) & (x%d==(bL-1)%d||x%d==(bL-1-lr*2*i)%d),1,B[x])); 
12.  
13. i=1; s=2; lr=1; d=6*i+2*s-3; 
14. B=vectorsmall(sb,x,if((x>bR||x<bL) & (B[x]==0) & (x%d==(bR+1)%d||x%d==(bR+1-lr*2*i)%d),2,B[x])); 
15.  
16. for(x=bR+1,sb,if(B[x]==0,bR=x-1;break)); 
17. forstep(x=bL-1,1,-1,if(B[x]==0,bL=x+1;break)); 
18.  
19. B0=B; bL0=bL; bR0=bR; mmax=0; Bmax=B; 
20.  
21. \\search through all combinations of forks and their tines 
22. for(lrc=0,2^(2*k-2)-1, 
23. lri=vectorsmall(2*k-2,i,2*(iferr(binary(lrc)[i],EE,0)-1/2)); 
24.  
25. forperm(2*k-2,gi, 
26. B=B0; bL=bL0; bR=bR0; 
27. for(j=1,2*k-2, 
28. g=gi[j]+2; lr=lri[j]; 
29. i=(g+1)\2; s=(g+1)%2+1; d=6*i+2*s-3; 
30.  
31. if(j%2==1, \\one shot left and one shot right of the island; strong assumption for the optimum strategy, valid for k=2,3,4 
32. B=vectorsmall(sb,x,if((x>bR||x<bL) & (B[x]==0) & (x%d==(bL-1)%d||x%d==(bL-1-lr*2*i)%d),g,B[x])) 
33. , 
34. B=vectorsmall(sb,x,if((x>bR||x<bL) & (B[x]==0) & (x%d==(bR+1)%d||x%d==(bR+1-lr*2*i)%d),g,B[x])) 
35. ); \\if j 
36.  
37. \\calcualte new island bounds 
38. for(x=bR+1,sb,if(B[x]==0,bR=x-1;break)); 
39. forstep(x=bL-1,1,-1,if(B[x]==0,bL=x+1;break)); 
40.  
41. ); \\for j 
42.  
43. \\store the best result 
44. mcurr=bR-bL+1; 
45. if(mcurr>mmax,mmax=mcurr;Bmax=B); 
46.  
47. ); \\forperm 
48. ); \\for lrc 
49.  
50. print(mmax); 
51. print(Bmax); 
52. return([]); 
53. }; 

Работа все время вроде с небольшими объектами, просто это полный перебор довольно большого числа вариантов, а именно $2^{2k-2}\times(2k-2)!$.
Ну и я каждый раз немного вздрагиваю, пиша конструкцию вида B=vectorsmall(sb,x,if(...,g,B[x])), но вроде бы тормозить это не должно. Ее, видимо, стоило бы заменить на всякие apply и ->, но я все никак не выучу этот пугающий синтаксис...

[anahronizm]

waxtep в сообщении #1717187 писал(а):

разобраться бы с тем, что уже есть!

Думаю, всё это безобразие можно выразить формулами, но я их не знаю.
А вот что знаю: если взять бесконечную полоску, то рисунок забития вилками (любым количеством вилок) будет периодичным и обладать симметрией относительно центра периода. Если взять первую вилку с её двумя проходами, то период будет равен 35. Если взять отдельно вторую вилку с её двумя проходами, то период будет равен 143. Если взять первые две вилки с двумя проходами каждой, то период будет равен 5005.
И т.д.

[wrest]

anahronizm в сообщении #1717195 писал(а):

Если взять первую вилку с её двумя проходами, то период будет равен 35.

Да, это наименьшее общее кратное (НОК, lcm) периодов первого и второго проходов, поскольку они простые числа, то просто произведение $35=5\cdot 7$

anahronizm в сообщении #1717195 писал(а):

Если взять отдельно вторую вилку с её двумя проходами, то период будет равен 143

Да, т.к. у второй вилки периоды равны 11 и 13, а $lcm(11,13)=143$

anahronizm в сообщении #1717195 писал(а):

Если взять первые две вилки с двумя проходами каждой, то период будет равен 5005.

Да, т.к. $ lcm(5,7,11,13)=5005$

Для третьей вилки периоды 17 и 20, их НОК равен 340, но для трёх вилок уже не равен произведению их периодов, т.к. период второго прохода третьей вилки равен 20, и он не взаимно-прост с периодом первого прохода первой вилки который равен 5. Произведение периодов $5\cdot 7 \cdot 11 \cdot 13\ \cdot 17 \cdot 20=1701700$ , но общий период $lcm(5,7,11,13,17,20)=340340$

-- 04.02.2026, 10:28 --

anahronizm в сообщении #1717195 писал(а):

то рисунок забития вилками (любым количеством вилок) будет периодичным и обладать симметрией относительно центра периода.

Периодичным - да, но "центр периода" это штука неясная, так лучше не говорить.

[anahronizm]

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

это штука неясная, так лучше не говорить.

Для первой вилки с её двумя проходами "центрами" симметрии можно обозвать все точки 17.5+35х, где х принимает целые значения.

[waxtep]

anahronizm, wrest, да, это верные соображения, но так (построением на полоске общего периода), кажется, долговато считать. Я пробовал что-то подобное в районе третьей страницы, получалось, что пять вилок понадобится считать пару дней, а шесть - пару лет (на мощностях моего нотика). Сейчас, благодаря помощи Dmitriy40 и Вашей, wrest, пять вилок считаются за шесть минут, а для шести оценка в двое суток. Ну и если смотреть на промежуточные результаты, то для шести вилок в первые минуты уже видно, что можно покрыть полоску в $109$ клеток. Впрочем, результаты для 5-6 вилок, - это не строгий максимум, а его эвристическая прикидка; на текущий момент зависимость длины максимальной покрываемой полосы $M(k)$ от количества вилок $k$ выглядит так:

$$\begin{tabular}{c|c|c|c|c|c|c}k & 1 & 2 & 3 & 4 & 5 & 6\\ \hline M(k) & 4 & 10 & 24 & 41 & \geqslant71 & \geqslant109\end{tabular}$$