Роене

[Bibi]

Имам една задача, която не мога да реша, дори не знам отговора. Ще ми се да опитаме да я разгадаем.

Имаме целочислена равнина и в (0,0) една точка, която започва да се размножава.
Правилата за живот в тая равнина са такива: на всеки такт всяка съществуваща точка се пръска на 4 нови в 4-те съседни възела - север, изток, юг, запад. При това, ако в някой възел попаднат повече от 1 деца, те взаимно се анихилират.

Така че в първия следващ такт ще има 4 точки в позиции (0,1) (1,0) (0,-1) (-1,0).

Пита се колко точки има в n-тия такт.
Значи търсим нещо като формула, зависеща от n.
Доколкото знам отговорът не е функция, а по-скоро зависимост. Примерно "броят единички в представянето на n в 4-ична бр. система".
Мисля, че в началото редицата започва така:
(1), 4, 4, 16, 4, 16, 16, 64, 4,...

[ql^2/8]

Според мен в n-тият такт има толкова точки, колкото е
4 на степен броя на единиците в двоичния запис на n.

[Bibi]

Нищо чудно да е толкова.
А имаш ли идея можем ли да го докажем?

[ql^2/8]

Ами в началото, както сама забеляза е
1 -> 4
2-3 -> 4 + 16
4-5-6-7 -> 4-16 + 16-64
8-9-10-11-12-13-14-15 -> 4-16-16-64 + 16-64-64-256
. . .
Роенето започва при 2^n винаги от 4 точки - майки на в позиции (-n,0);(n,0);(0,-n);(0,n).


Всеки цикъл между степените на двойката става двойно по-дълъг от предишния, като първо повтаря
предишния, а след това още веднъж, умножен по 4. Това най ми прилича на двоичен запис...
Повтаря се, защото това са 4 независими семейства, които се разпадат на 16 независими... При
достигане на 2^(n+1)-1 се запълва шахматно целия ромб (завъртян квадрат) с (n-1).(n-1) точки,
които се "пукват" на 4 независими майки...

Не съм сигурен че разбрах, какво написах...

[Bibi]

Извинявам се, че изчезнах, но една мега-градушка ми уби интернета вчера. Сега ползвам някаква съмнителна флашка за достъп и нищо чудно пак да имам проблеми.

Аз май разбрах какво казваш. Но не се сещам как може да се тръгне към строго доказателство.
Индукция може би, но самият отговор не изглежда подходящ за индукция.
Може би трябва да съобразим как броят на единиците зависи от n. Или пък показател за какво свойство е.

Друга идея: първо да решаваме задачата по права, а не в равнина. Може там да видим зависимостта по-лесно.

[ql^2/8]

На мен най-ми прилича на рекурсия. Всеки такт започващ от 2^n
повтаря предишния, веднъж за 1 група от 4 майки, след това
за 4 групи по 4 майки, докато достигне максималното роене.
Така например всяко n-цифрено число повтаря (n-1)-цифрените числа
толкова пъти, колкото основата на бройната система.

[dedis]

Прилича донякъде на задачата за къртиците. Но там полето е ограничено.

[Yasen6275_]

Имам чувтвото че пак нещо не съм разбрал условието (както обикновено). Имамме точка(стара) и върху нея от роенето се получава една или повече нови. Какво става на този възел? Остава празен?

Ако това е вярно редицата изглежда малко по-различно.
1,5,8,12,16...

Замомента расте само по периферията и не се връща назад, но не съм 100% сигурен че постоянно е така.

Или точката след размножаването си не остава нищо на изходна позиция?

[Bibi]

Не остава нищо. Все едно се пръска на 4 деца. А тези от тях, които се сбият за една и съща позиция, взаимно се пречукват.

[Wise]

мисля, че ще останат точно 4 дечица, независимо от "n"
всички четни / вътрешни се анхилират - остава само по едно външно на всеки такт =4

//май съм писал глупости пак...

[Yasen6275]

Бе не са точно глупости. на определен брой цикли се случва точно това.