|
Перекладывание камешков | ☑ | ||
---|---|---|---|---|
0
1Страх
05.10.12
✎
11:17
|
Есть некое количество камешков, произвольно распределенных по нескольким кучкам. Из каждой кучки берется по одному камешку и из них формируется новая кучка. Операция повторяется неограниченное количество раз.
Может ли в пределе получится устойчивое разложение камешков по кучкам? |
|||
1
Нуф-Нуф
05.10.12
✎
11:19
|
зачем?
|
|||
2
Mykola
05.10.12
✎
11:19
|
Что делается в итерации с кучкой из 1 камня? Он берется и кладется в новую кучку?
|
|||
3
1Страх
05.10.12
✎
11:19
|
(1) ты темой ошибся, айпадов и айфонов тут нет
|
|||
4
1Страх
05.10.12
✎
11:20
|
(2) да
|
|||
5
1Страх
05.10.12
✎
11:20
|
(2) да так, старая кучка исчезает
|
|||
6
Жан Пердежон
05.10.12
✎
11:20
|
2 кучи по 2 камешка?
|
|||
7
1Страх
05.10.12
✎
11:22
|
(6) вот ее цикл:
2,2 - 2 кучки 2,1,1 - 3 кучки 3,1 - 2 кучки 2,2 - 2 кучки состояние цикличное, но не постоянное под устойчивым я подразумевал одинаковое количество кучек на каждом ходу начиная с некоторого |
|||
8
1Страх
05.10.12
✎
11:23
|
+(7) а лучше даже и количество камешков в кучках устойчивое
|
|||
9
Нуф-Нуф
05.10.12
✎
11:23
|
предлагаю перекладывать кучки с айфонами
|
|||
10
1Страх
05.10.12
✎
11:24
|
(9) давай так
|
|||
11
Mykola
05.10.12
✎
11:24
|
Создадутся кучки от 1 камня до максимального размера кучки с разницей в количестве в 1 камень.
|
|||
12
1Страх
05.10.12
✎
11:25
|
(11) молодец, других вариантов нет?
кстати любое ли расположение, например, 6 камней в пределе приходит к устойчивому? |
|||
13
Хоменко Валерий
05.10.12
✎
11:36
|
Не обязательно к устойчивому, возможно к устойчивому циклу:
3,1 -> 2,2 -> 2,1,1 -> 3,1 Блин, теорию групп надо вспоминать :) |
|||
14
1Страх
05.10.12
✎
12:07
|
(13) к циклу это и дураку ясно, ведь число комбинаций конечно
необходимо именно к устойчивому положению |
|||
15
1Страх
05.10.12
✎
12:53
|
чей то всех не прет
|
|||
16
y88
05.10.12
✎
13:02
|
(14) Устойчивое, например
3 2 1 |
|||
17
1Страх
05.10.12
✎
13:04
|
(16) самое крутое, что если есть устойчивая комбинация с N камешками, то любая комбинация с N камешками устойчива
|
|||
18
rrunover
05.10.12
✎
13:04
|
из 3 переложи в 1, получишь 2 2 2 , а надо, чтобы после очередного переклада получилось бы снова 3 2 1. всегда. нет разве?
|
|||
19
1Страх
05.10.12
✎
13:06
|
(18) да, именно так и получается
|
|||
20
NS
05.10.12
✎
13:09
|
(7) Каждым ходом ты создаешь новую кучку, и при этом хочешь чтоб количество кучек осталось таким-же.
Но понятно что это возможно только если ровно в одной из кучек ровно один камень. А в каждой следующей кучке ровно на один камень больше чем в предыдущей. То есть все варианты решений. 1 1 2 1 2 3 И .т.д |
|||
21
1Страх
05.10.12
✎
13:09
|
(20) все верно, осталось доказать (17)
|
|||
22
NS
05.10.12
✎
13:10
|
(19) что? Сам не можешь понять свое же условие?
Из каждой кучки по одному камню и в новую кучку. |
|||
23
1Страх
05.10.12
✎
13:11
|
(22) ничего, я имел ввиду, что из 1,2,3 получается 1,2,3
|
|||
24
NS
05.10.12
✎
13:11
|
(21) в (17) чушь и неправда. Комбинация с шестью камешками устойчива, 1 2 3
Но комбинация с тем же числом камней 2 2 2 - не устойчива. |
|||
25
y88
05.10.12
✎
13:12
|
(17) круто!
(24) из 2 2 2 через несколько ходов получается 1 2 3 |
|||
26
1Страх
05.10.12
✎
13:12
|
(24) в пределе (то бишь через несколько ходов) - станет устойчивой 1,2,3
|
|||
27
NS
05.10.12
✎
13:16
|
Да, действительно станет.
|
|||
28
y88
05.10.12
✎
13:18
|
А есть другое N кроме N = СУММА(1,2,3...) ?
|
|||
29
NS
05.10.12
✎
13:21
|
(28) Конечно нет.
|
|||
30
1Страх
05.10.12
✎
13:21
|
(28) очевидно же из (20), что нет
только N = n*(n+1)/2 |
|||
31
Нуф-Нуф
05.10.12
✎
13:22
|
сколько айфонов уже успели переложить?
|
|||
32
Прохожий
05.10.12
✎
13:22
|
Количество кучек будет ограничено первоначальным максимальным количеством камней Z в одной из кучек. Дальше по исчерпанию этой кучки будут образовываться новые кучки с максимумом не более Z. Поскольку количество камней в каждой кучке при таком условии конечно (0-Z), то и количество комбинаций всех количеств конечно. При этом при достижении идентичного сочетания количеств в кучках гарантировано начинается новый цикл ибо все кучки взаимозаменяемы. кучки 3-5-6 тождественны кучкам 5-3-6 и т. д. При конечном количестве возможных комбинаций очень скоро процесс зациклится во всех случаях.
|
|||
33
NS
05.10.12
✎
13:23
|
(28) Повторю - чтоб получилось такое-же количество кучек как и боло ровно в одной кучке должен быть один камень.
Так как ровно в одной кучке до этого был один камень. И после перекладывания ровно в одной кучке остался один камень. Это либо сам переложенный камень (всего у нас одна кучка из одного камня), либо ровно в одной кучке до перекладывания было два камня. И т.д. |
|||
34
Прохожий
05.10.12
✎
13:26
|
+(32) Z=(КоличествоГрупп,МаксимальнаяГруппа) А в остальном все правильно. Сочетаний возможных не много, группы взаимозаменяемы. Чтобы было нециклично нужно на каждом ходу получать УНИКАЛЬНОЕ сочетание. Это долго не продлится.
|
|||
35
Прохожий
05.10.12
✎
13:27
|
Z=max(КоличествоГрупп,МаксимальнаяГруппа)
|
|||
36
NS
05.10.12
✎
13:32
|
(34) Ежу понятно что будет циклично. Просят доказать что сведется к устойчивому положению.
|
|||
37
Прохожий
05.10.12
✎
13:36
|
N кучек не может породить новую кучку размером более N. Дальше кучка начинает тратиться и проживет не более N ходов, за которые все группы гарантировано исчезнут и элементы полностью перекомбинируются. Поэтому Если кучек N, а в каждой количество а,в,с..... , то есть максимум Z= max(N,max(а,в,с)). каждое из значений при этом N<=Z,а<=Z,в<=Z,с<=Z... При этом комбинаций будет конечное число. Как только их исчерпаем - гарантировано выйдем на неуникальную комбинацию (кучки-штучки). С неё опять начинаем ту же последовательность.
(36) Сочетание количеств должно выпадать уникальным каждый раз, кучки никак не отличаются друг от друга. Перекладывают бесконечное число раз. |
|||
38
1Страх
05.10.12
✎
13:37
|
(37) хватит писать очевидные вещи
|
|||
39
Прохожий
05.10.12
✎
13:38
|
Для любого начального количества кучек можно расписать все возможные состояния. Это же целые величины. Их всегда конечно. А ходов бесконечно.
|
|||
40
Прохожий
05.10.12
✎
13:39
|
Когда количество ходов превысит количество возможных сочетаний гарантировано начнется уже второй цикл. Не позже.
|
|||
41
Прохожий
05.10.12
✎
13:42
|
Пусть есть 36 элементов 6 кучками 9-5-3-2-7-10.
Такая система не разложится при любом количестве ходов более чем в 10 кучек, ни одна кучка никогда не будет более 10 элементов. Дальше распишите таблицу всех возможных сочетаний и узнаете максимальный теоретический размер цикла. |
|||
42
Прохожий
05.10.12
✎
13:46
|
При этом вы не вернетесь гарантировано на комбинацию 9-5-3-2-7-10, но зациклитесь вы наверняка...
|
|||
43
Адимр
05.10.12
✎
14:46
|
(0) Так вот жизнь на земле и появилась. Мне по секрету один БОЛЬШОЙ ЧЕЛОВЕК сказал, что Intel таким же способом свои процессоры разрабатывает!
|
|||
44
Прохожий
05.10.12
✎
15:39
|
(43) Так китайцы разрабатывают: миллиард китайцев получают по печатной машинке и все надеются что один из них напишет "Войну и мир".
У них прошивка на каждый сотовый меняется 6 раз в месяц. |
|||
45
Надсмотрщик
05.10.12
✎
15:49
|
(9) В результате получишь 0!
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |