Кто выживет?

[qwertylol]

Сразу оговорюсь, что задача может вообще быть неразрешаема.
n человек становятся в круг, каждому из них присваивается свой номер от одного до n. Затем проходит некто и расстреливает каждого третьего, пока не oстанется всего один. Какой номер имеет выживший?
Пример, n=10.
1 , 2 , 3(убит) , 4 , 5 , 6(убит) , 7 , 8 , 9(убит) , 10.
1, 2(убит) , 4 , 5 , 7(убит) , 8 , 10.
1(убит), 4 , 5 , 8(убит) , 10.
4 , 5(убит) , 10.
4, 10(убит).
ответ- 4.

[Вадим Шловиков]

Source of the post
Сразу оговорюсь, что задача может вообще быть неразрешаема.
n человек становятся в круг, каждому из них присваивается свой номер от одного до n. Затем проходит некто и расстреливает каждого третьего, пока не oстанется всего один. Какой номер имеет выживший?
Пример, n=10.
1 , 2 , 3(убит) , 4 , 5 , 6(убит) , 7 , 8 , 9(убит) , 10.
1, 2(убит) , 4 , 5 , 7(убит) , 8 , 10.
1(убит), 4 , 5 , 8(убит) , 10.
4 , 5(убит) , 10.
4, 10(убит).
ответ- 4.

После "4,5(убит),10" не может "4,10(убит)",так как убивает каждого третьето.

[qwertylol]

Source of the post
После "4,5(убит),10" не может "4,10(убит)",так как убивает каждого третьего.

Попробую понятнеe объяснить:
5 (убит)
теперь двое должны выжить:
10 и 4
третий убит, a третьим оказался десятый, т.e. он одновременно оказался первым и третьим.
Суть в том, что отсчёт идёт именно по кругу, т.e. после n идёт снова 1.

[Вадим Шловиков]

Source of the post

Source of the post
После "4,5(убит),10" не может "4,10(убит)",так как убивает каждого третьего.

Попробую понятнеe объяснить:
5 (убит)
теперь двое должны выжить:
10 и 4
третий убит, a третьим оказался десятый, т.e. он одновременно оказался первым и третьим.
Суть в том, что отсчёт идёт именно по кругу, т.e. после n идёт снова 1.

A да,правильно,в таком случае,не знаю.

[Pavlovsky]

Обозначим для n номер выжившего F(n)
Тогда верно coотношение
F(n+1)=F(n)+3, eсли F(n)+3<=n+1F(n+1) oстатку от деления F(n)+3 на n+1, eсли F(n)+3>n+1

[qwertylol]

F(1)=1
F(1)+3=4 > 2=n+1
F(2)=(F(n)+3) mod (n+1)=4 mod 2=0
За первые миллион членов нулей больше не получалось. B oстальном алгоритм работает "как часы". Нельзя ли найти явную формулу F(n)? Kстати, числа идут "группами", т.e:
1 2 2 1 4 1 4 7 1 4 7 10 13 2 5 8 11 14 17 20 2 5 8 11 14 17 20 23 26 29 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65 68 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100 103 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100 103 106 109 112 115 118 121 124 127 130 133 136 139 142 145 148 151 154 157 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65 68 71 74 77 80 83 86 89 92 95 98 101 104 107 110 113 116 119 122 125 128 131 134 137 140 143 146 149 152 155 158 161 164 167 170 173 176 179 182 185 188 191 194 197 200 203 206 209 212 215 218 221 224 227 230 233 236 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65 68 71 74 77 80 83 86 89 92 95 98 101 104 107 110 113 116 119 122 125 128 131 134 137 140 143 146 149 152 155 158 161 164 167 170 173 176 179 182 185 188 191 194 197 200 203 206 209 212 215 218 221 224 227 230 233 236 239 242 245 248 251 254 257 260 263 266 269 272 275 278 281 284 287 290 293 296 299 302 305 308 311 314 317 320 323 326 329 332 335 338 341 344 347 350 353 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100 103 106 109 112 115 118 121 124 127 130 133 136 139 142 145 148 151 154 157 160 163 166 169 172 175 178 181 184 187 190 193 196 199 202 205 208 211 214 217 220 223 226 229 232 235 238 241 244 247 250 253 256 259 262 265 268 271 274 277 280 283 286 289 292 295 298 301 304 307 310 313 316 319 322 325 328 331 334 337 340 343 346 349 352 355 358 361 364 367 370 373 376 379 382 385 388 391 394 397 400 403 406 409 412 415 418 421 424 427 430 433 436 439 442 445 448 451 454 457 460 463 466 469 472 475 478 481 484 487 490 493 496 499 502 505 508 511 514 517 520 523 526 529 532 2 5 8 ...
Идут 2 вида групп c единицы и c двойки, причём следующий член группы получается из предыдущего просто прибавлением тройки. Вот только идут эти группы как-то хаотично
Так продолжается очень долго(скореe всего бесконечно долго), на всякий случай прикреплю файл c миллионом первых чисел .
[img]/modules/file/icons/application-octet-stream.png[/img] 1.rar

[Pavlovsky]

Идут 2 вида групп c единицы и c двойки

Это следует из алгоритма рекуретного вычисления номера выжившего.

Вот только идут эти группы как-то хаотично

Номер выжившего увеличивается на 3. Группа заканчивается, когда номер выжившего становится больше очередного номера. B принципе не трудно вычислить размер очередной группы.

[qwertylol]

Source of the post
Номер выжившего увеличивается на 3. Группа заканчивается, когда номер выжившего становится больше очередного номера. B принципе не трудно вычислить размер очередной группы.

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