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

[waxtep]

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

А покажите координаты первого прокола.
$k$ - это число вилок (соответствено у последней прогрессии шаг $445$)

Хорошо, вечером, - сейчас аппаратура не с собой. Да, $k$ - количество вилок, т.е. шаг последней прогрессии $445$ при $k=74$.
Координаты проколов (по идее, не могу сейчас запустить), должны быть:
- первая вилка (с одним зубцом), первый проход: $1,6,11,16,\ldots$
- первая вилка, второй проход: $2,9,16,23,\ldots$
- вторая вилка, первый проход: $3,14,25,36,\ldots$
- вторая вилка, второй проход: $4,17,30,43,\ldots$
и т.д.

-- 27.01.2026, 14:55 --

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

[wrest]

waxtep
Ну и, пока видно, что начиная с полоски длиной 76, все следующие полоски будут полностью проколоты.

Настаёт стадия обощения. Куда будем обощать?

[waxtep]

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

Ну и, пока видно, что начиная с полоски длиной 76, все следующие полоски будут полностью проколоты.

Настаёт стадия обощения. Куда будем обощать?

Доказать бы еще этот частный случай... интересно, пройдет ли доказательство по индукции? Пока не пробовал вникнуть.
А обобщение, наверное, что-то в духе статьи по ссылке от уважаемого mihaild, - какими свойствами должны обладать наборы прогрессий, чтобы покрывать то или иное множество. Я только очень поверхностно пролистал, пока не было времени. Кажущееся (скорее всего) противоречие с утверждением статьи, вот, можно покрыть прогрессиями с шагом $6i\pm1,1\leqslant i\leqslant k$ последовательные натуральные числа от $1$ до $8k+4$, при $k=74$ (и, видимо, при всех бОльших $k$). Для $k=74$ последовательность выкалываемых точек выглядит так:

(Оффтоп)

1. 1 1L 0 [1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56, 61, 66, 71, 76, 81, 86, 91, 96, 101, 106, 111, 116, 121, 126, 131, 136, 141, 146, 151, 156, 161, 166, 171, 176, 181, 186, 191, 196, 201, 206, 211, 216, 221, 226, 231, 236, 241, 246, 251, 256, 261, 266, 271, 276, 281, 286, 291, 296, 301, 306, 311, 316, 321, 326, 331, 336, 341, 346, 351, 356, 361, 366, 371, 376, 381, 386, 391, 396, 401, 406, 411, 416, 421, 426, 431, 436, 441, 446, 451, 456, 461, 466, 471, 476, 481, 486, 491, 496, 501, 506, 511, 516, 521, 526, 531, 536, 541, 546, 551, 556, 561, 566, 571, 576, 581, 586, 591, 596] 
2. 1 2L 1 [2, 9, 16, 23, 30, 37, 44, 51, 58, 65, 72, 79, 86, 93, 100, 107, 114, 121, 128, 135, 142, 149, 156, 163, 170, 177, 184, 191, 198, 205, 212, 219, 226, 233, 240, 247, 254, 261, 268, 275, 282, 289, 296, 303, 310, 317, 324, 331, 338, 345, 352, 359, 366, 373, 380, 387, 394, 401, 408, 415, 422, 429, 436, 443, 450, 457, 464, 471, 478, 485, 492, 499, 506, 513, 520, 527, 534, 541, 548, 555, 562, 569, 576, 583, 590] 
3. 2 1L 2 [3, 14, 25, 36, 47, 58, 69, 80, 91, 102, 113, 124, 135, 146, 157, 168, 179, 190, 201, 212, 223, 234, 245, 256, 267, 278, 289, 300, 311, 322, 333, 344, 355, 366, 377, 388, 399, 410, 421, 432, 443, 454, 465, 476, 487, 498, 509, 520, 531, 542, 553, 564, 575, 586] 
4. 2 2L 3 [4, 17, 30, 43, 56, 69, 82, 95, 108, 121, 134, 147, 160, 173, 186, 199, 212, 225, 238, 251, 264, 277, 290, 303, 316, 329, 342, 355, 368, 381, 394, 407, 420, 433, 446, 459, 472, 485, 498, 511, 524, 537, 550, 563, 576, 589] 
5. 3 1L 4 [5, 22, 39, 56, 73, 90, 107, 124, 141, 158, 175, 192, 209, 226, 243, 260, 277, 294, 311, 328, 345, 362, 379, 396, 413, 430, 447, 464, 481, 498, 515, 532, 549, 566, 583] 
6. 3 2L 6 [7, 26, 45, 64, 83, 102, 121, 140, 159, 178, 197, 216, 235, 254, 273, 292, 311, 330, 349, 368, 387, 406, 425, 444, 463, 482, 501, 520, 539, 558, 577, 596] 
7. 4 1L 7 [8, 31, 54, 77, 100, 123, 146, 169, 192, 215, 238, 261, 284, 307, 330, 353, 376, 399, 422, 445, 468, 491, 514, 537, 560, 583] 
8. 4 2L 9 [10, 35, 60, 85, 110, 135, 160, 185, 210, 235, 260, 285, 310, 335, 360, 385, 410, 435, 460, 485, 510, 535, 560, 585] 
9. 5 1L 11 [12, 41, 70, 99, 128, 157, 186, 215, 244, 273, 302, 331, 360, 389, 418, 447, 476, 505, 534, 563, 592] 
10. 5 2L 12 [13, 44, 75, 106, 137, 168, 199, 230, 261, 292, 323, 354, 385, 416, 447, 478, 509, 540, 571] 
11. 6 1L 14 [15, 50, 85, 120, 155, 190, 225, 260, 295, 330, 365, 400, 435, 470, 505, 540, 575] 
12. 6 2L 17 [18, 55, 92, 129, 166, 203, 240, 277, 314, 351, 388, 425, 462, 499, 536, 573] 
13. 7 1L 18 [19, 60, 101, 142, 183, 224, 265, 306, 347, 388, 429, 470, 511, 552, 593] 
14. 7 2L 19 [20, 63, 106, 149, 192, 235, 278, 321, 364, 407, 450, 493, 536, 579] 
15. 8 1L 23 [24, 71, 118, 165, 212, 259, 306, 353, 400, 447, 494, 541, 588] 
16. 8 2L 26 [27, 76, 125, 174, 223, 272, 321, 370, 419, 468, 517, 566] 
17. 9 1L 27 [28, 81, 134, 187, 240, 293, 346, 399, 452, 505, 558] 
18. 9 2L 28 [29, 84, 139, 194, 249, 304, 359, 414, 469, 524, 579] 
19. 10 1L 31 [32, 91, 150, 209, 268, 327, 386, 445, 504, 563] 
20. 10 2L 32 [33, 94, 155, 216, 277, 338, 399, 460, 521, 582] 
21. 11 1L 33 [34, 99, 164, 229, 294, 359, 424, 489, 554] 
22. 11 2L 37 [38, 105, 172, 239, 306, 373, 440, 507, 574] 
23. 12 1L 39 [40, 111, 182, 253, 324, 395, 466, 537] 
24. 12 2L 41 [42, 115, 188, 261, 334, 407, 480, 553] 
25. 13 1L 47 [48, 125, 202, 279, 356, 433, 510, 587] 
26. 13 2L 48 [49, 128, 207, 286, 365, 444, 523] 
27. 14 1L 51 [52, 135, 218, 301, 384, 467, 550] 
28. 14 2L 52 [53, 138, 223, 308, 393, 478, 563] 
29. 15 1L 56 [57, 146, 235, 324, 413, 502, 591] 
30. 15 2L 58 [59, 150, 241, 332, 423, 514] 
31. 16 1L 61 [62, 157, 252, 347, 442, 537] 
32. 16 2L 66 [67, 164, 261, 358, 455, 552] 
33. 17 1L 67 [68, 169, 270, 371, 472, 573] 
34. 17 2L 73 [74, 177, 280, 383, 486, 589] 
35. 18 1L 77 [78, 185, 292, 399, 506] 
36. 18 2L 86 [87, 196, 305, 414, 523] 
37. 19 1L 87 [88, 201, 314, 427, 540] 
38. 19 2L 88 [89, 204, 319, 434, 549] 
39. 20 1L 96 [97, 216, 335, 454, 573] 
40. 20 2L 97 [98, 219, 340, 461, 582] 
41. 21 1L 102 [103, 228, 353, 478] 
42. 21 2L 103 [104, 231, 358, 485] 
43. 22 1L 108 [109, 240, 371, 502] 
44. 22 2L 111 [112, 245, 378, 511] 
45. 23 1L 116 [117, 254, 391, 528] 
46. 23 2L 118 [119, 258, 397, 536] 
47. 24 1L 121 [122, 265, 408, 551] 
48. 24 2L 126 [127, 272, 417, 562] 
49. 25 1L 129 [130, 279, 428, 577] 
50. 25 2L 131 [132, 283, 434, 585] 
51. 26 1L 132 [133, 288, 443] 
52. 26 2L 142 [143, 300, 457] 
53. 27 1L 143 [144, 305, 466] 
54. 27 2L 144 [145, 308, 471] 
55. 28 1L 147 [148, 315, 482] 
56. 28 2L 151 [152, 321, 490] 
57. 29 1L 152 [153, 326, 499] 
58. 29 2L 153 [154, 329, 504] 
59. 30 1L 161 [162, 341, 520] 
60. 30 2L 166 [167, 348, 529] 
61. 31 1L 179 [180, 365, 550] 
62. 31 2L 188 [189, 376, 563] 
63. 32 1L 192 [193, 384, 575] 
64. 32 2L 194 [195, 388, 581] 
65. 33 1L 199 [200, 397, 594] 
66. 33 2L 207 [208, 407] 
67. 34 1L 212 [213, 416] 
68. 34 2L 213 [214, 419] 
69. 35 1L 216 [217, 426] 
70. 35 2L 219 [220, 431] 
71. 36 1L 221 [222, 437] 
72. 36 2L 226 [227, 444] 
73. 37 1L 231 [232, 453] 
74. 37 2L 236 [237, 460] 
75. 38 1L 241 [242, 469] 
76. 38 2L 247 [248, 477] 
77. 39 1L 249 [250, 483] 
78. 39 2L 254 [255, 490] 
79. 40 1L 256 [257, 496] 
80. 40 2L 261 [262, 503] 
81. 41 1L 262 [263, 508] 
82. 41 2L 268 [269, 516] 
83. 42 1L 273 [274, 525] 
84. 42 2L 286 [287, 540] 
85. 43 1L 296 [297, 554] 
86. 43 2L 297 [298, 557] 
87. 44 1L 298 [299, 562] 
88. 44 2L 308 [309, 574] 
89. 45 1L 311 [312, 581] 
90. 45 2L 312 [313, 584] 
91. 46 1L 317 [318, 593] 
92. 46 2L 319 [320] 
93. 47 1L 324 [325] 
94. 47 2L 336 [337] 
95. 48 1L 338 [339] 
96. 48 2L 342 [343] 
97. 49 1L 349 [350] 
98. 49 2L 356 [357] 
99. 50 1L 362 [363] 
100. 50 2L 366 [367] 
101. 51 1L 368 [369] 
102. 51 2L 371 [372] 
103. 52 1L 373 [374] 
104. 52 2L 374 [375] 
105. 53 1L 381 [382] 
106. 53 2L 389 [390] 
107. 54 1L 391 [392] 
108. 54 2L 397 [398] 
109. 55 1L 401 [402] 
110. 55 2L 402 [403] 
111. 56 1L 403 [404] 
112. 56 2L 404 [405] 
113. 57 1L 408 [409] 
114. 57 2L 411 [412] 
115. 58 1L 437 [438] 
116. 58 2L 438 [439] 
117. 59 1L 447 [448] 
118. 59 2L 448 [449] 
119. 60 1L 457 [458] 
120. 60 2L 472 [473] 
121. 61 1L 473 [474] 
122. 61 2L 474 [475] 
123. 62 1L 478 [479] 
124. 62 2L 483 [484] 
125. 63 1L 487 [488] 
126. 63 2L 494 [495] 
127. 64 1L 496 [497] 
128. 64 2L 499 [500] 
129. 65 1L 511 [512] 
130. 65 2L 517 [518] 
131. 66 1L 518 [519] 
132. 66 2L 521 [522] 
133. 67 1L 529 [530] 
134. 67 2L 532 [533] 
135. 68 1L 537 [538] 
136. 68 2L 542 [543] 
137. 69 1L 543 [544] 
138. 69 2L 544 [545] 
139. 70 1L 546 [547] 
140. 70 2L 558 [559] 
141. 71 1L 564 [565] 
142. 71 2L 566 [567] 
143. 72 1L 567 [568] 
144. 72 2L 569 [570] 
145. 73 1L 571 [572] 
146. 73 2L 577 [578] 
147. 74 1L 579 [580] 
148. 74 2L 594 [595] 

[mihaild]

waxtep
А 599 какая из ваших прогрессий покрывает?

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

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

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

[waxtep]

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

А 599 какая из ваших прогрессий покрывает?

(голосом Шарапова, репетирующего визит в малину) А никакая! В самом деле, $2\times74$ прогрессии как выше покрывают все натуральные числа от $1$ до $596$, но не дают покрытия натурального ряда, числа $599, 607, 609, 623,\ldots$ - не покрыты

-- 28.01.2026, 02:43 --

Да, и даже если вернуть вилкам их правые зубцы, при $k=74$ не будет покрытия всего натурального ряда, дырки начнутся с $3302,3310,3317,3344\ldots$. То есть, кажется, то, что прогрессий с данным шагом по две штуки, - не спасает в плане покрытия всего $\mathbb{N}$

[waxtep]

Еще можно посмотреть на $M(k)$ - размер максимального сплошного покрытого куска натурального ряда (максимальную длину полоски, что можно полностью проткнуть $k$ вилками). Прямо скажем, на заданное автором $L(k)=8k+4$ оно не похоже, а больше похоже на квадратичную параболу, но как будто чуть до параболы не дотягивает. Для малых $k$ это $M(k)$ ведет себя безобразно, то скачет, то практически застывает, а, например, при $100\leqslant k \leqslant 300$ вполне похоже на такое:

$$M(k)=\frac{89}{40}\, k^{69/40}(1+\varepsilon(k)),|\varepsilon(k)|<0.03$$

Ну это конечно чисто гадание на кофейной гуще уже (впрочем, увлекательное)

[anahronizm]

Извиняюсь, что влезаю в ваш интереснейший диалог, в котором я мало понимаю, но если будет возможность, объясните мне простыми словами, как правильно ответить на первоначальные вопросы в задаче:
"..какие из утверждений будут верны:
1. невозможно проколоть все клетки на любой полоске
2. начиная с некоторой полоски все последующие могут быть проколоты полностью
3. при любом увеличении полоски, среди полностью проколотых, найдётся такая, которую невозможно проколоть полностью..."
И можно ли ответить на них вообще.
Существует ли строгое доказательство?
Извините, я не знаю, поэтому спрашиваю.
Вообще, когда мы занимались такими раскрасками(да, каюсь, мы не тыкали вилками, а заштриховывали квадратики), я думал, что верный ответ третий: "...при любом увеличении полоски, среди полностью проколотых(полосок), (всегда)найдётся такая, которую невозможно проколоть полностью..."
И ещё была такая мысль, как сделать так, чтобы всегда иметь гарантию того, что будет такая не проколотая (не закрашенная) полоска.
Увеличить изменение длины полоски? Тогда какой длины должна быть начальная полоска и приращение её длины ?
Честно-четно, я думал, что задача проще (господин админ, я никого не хочу обидеть).

[wrest]

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

1. невозможно проколоть все клетки на любой полоске

Возможно проколоть все клетки, начиная с полоски длиной 76

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

2. начиная с некоторой полоски все последующие могут быть проколоты полностью

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

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

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

Формулировка вопроса непонятна.

-- 28.01.2026, 10:19 --

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

Увеличить изменение длины полоски?

Ну вот пока не обобщали.

[anahronizm]

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

Формулировка вопроса непонятна.

Была такая мысль, что полоски по длине увеличиваются бесконечно, а при использовании вилок с данными условиями всегда будут появляться наложения проколов друг на друга. Поэтому и было подозрение, что даже если некоторую полоску можно полностью забить дырками (даже множество последовательных полосок), то потом может появиться такая, которую невозможно заполнить дырками. И такие полоски буду появляться до бесконечности, пусть всё реже и реже.
Ну, это только мысль такая была, не более.
Когда рисовашками занимались, была ещё какая-то интересная мысля, если вспомню - напишу.
Спасибо за ответ.

[waxtep]

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

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

Ага, строго говоря, не доказали. Но очень похоже, что $k$ вилок хватит, чтоб полностью проколоть полоску длины $M(k)$, растущей сильно быстрее, чем линейная функция от $k$, например исходно данная $L(k)=8k+4$. Тоже не доказано, конечно; задача строгого доказательства какой-то осмысленной оценки длины полоски снизу, видимо, трудна (по крайней мере для меня, не математика, имеющего крайне отдалённые представления о возможностях теории чисел)

[mihaild]

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

Да, и даже если вернуть вилкам их правые зубцы, при $k=74$ не будет покрытия всего натурального ряда, дырки начнутся с $3302,3310,3317,3344\ldots$

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

[wrest]

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

например, при $100\leqslant k \leqslant 300$ вполне похоже на такое:

$$M(k)=\frac{89}{40}\, k^{69/40}(1+\varepsilon(k)),|\varepsilon(k)|<0.03$$

То есть степень похожа на 7/4 - вот она как-то наверное должна обобщиться из параметров.
А дальше (при k, скажем $10^4,10^5,10^6$)?

[waxtep]

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

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

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

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

То есть степень похожа на 7/4 - вот она как-то наверное должна обобщиться из параметров.
А дальше (при k, скажем $10^4,10^5,10^6$)?

Не считал пока, график вообще негладкий; хотелось хотя бы на микромасштабе получить осциллирующую вокруг нуля поправку. Честно говоря, не думаю, что легко получить красивую оценку снизу, и тем более её доказательство. Но пытаться же не грех

[wrest]

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

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

Так эта стратегия как бы наивно-очевидная: если туда не тыкнуть, то клетка останется непроколотой.

[waxtep]

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

Так эта стратегия как бы наивно-очевидная: если туда не тыкнуть, то клетка останется непроколотой.

Тоже так подумал, но можно ведь не каждой вилкой так тыкать это ещё отдельный вопрос, видимо: является ли такая наивная стратегия оптимальной