Я елате, пиленцааа, при батко!

[Гост]

Както вече се досетихте, в тази задача става дума за пиленца. Не мога да я реша.
Задача. В един селски плевник x на брой пиленца стоят спокойно в кръг. Внезапно всяко пиле клъвва непосредствено съседното си вляво или вдясно, избирайки по случаен начин. След това останали неклъвнати y на брой пиленца. За всяко цяло x (x≥2) да се намерят всички цели числа, които са възможни стойности на y.
Коментар. Решение на задачата нямам. Не знам и отговорът какъв е. Само един частичен резултат. Което съм установил досега:
За x=2, y=0;
За x=3, y=0 или 1;

За x≥4:
Ако x≡0(mod4), то y може да е всяко цяло, 0≤y≤x/2 и не е възможно y>x/2.
Ако x≡1(mod4), то y може да е всяко цяло, 0≤y≤[x/2] и не е възможно y>[x/2]+1.
Ако x≡2(mod4), то y може да е всяко цяло, 0≤y≤[x/2] и не е възможно y>[x/2]+2.
Ако x≡3(mod4), то y може да е всяко цяло, 0≤y≤[x/2]+1 и не е възможно y>[x/2]+2.
Интересни са въпросите (на които не мога да отговоря):
Ако x≡1(mod4), то може ли y=[x/2]+1? (Само за x=5 съм намерил, че не е възможно y=3.)
Ако x≡2(mod4), то може ли y=[x/2]+1 и може ли y=[x/2]+?
Ако x≡3(mod4), то може ли y=[x/2]+2?

Ще съм благодарен, ако някой даде някакви идеи.

[peyo]

Много интересна задача!

Да изследваме случая при който ще имаме най-много възможни неклъвнати пилета. Като се замислим, трябват ни минимум 3 пилета за да получим едно неклъвнато при единствената възможна комбинация:
>><
(или нейната симетрична ><< но като изберем една посока само нея използваме)

Така максимално ше подреждаме такива тройки една до друга 2 от 6:
>><>><
3 от 9:
>><>><>><
4 от 12:
>><>><>><>><
Така в най-добрия случай 1/3 неклъвнати може да имаме, когато броя им е кратен на 3. Ако броят им не е кратен на 3 може да имаме 1/3 неклъвнати до най-близкото чилсо надолу кратно на 3, Например при 8:
>><>><>>
Имаме 2 неклъвнати, като при 6.
Остава да отговорим на въпроса кои числа от 0 до x/3 са възможни?
Да видим дали y=1 е възможно?

При 2 не е >> или <> не стават.
При 3:
>>< y = 1 e възможно.
При 4:
>>>< y = 1 e възможно.
При 5:
>>>>< y = 1 e възможно.
Използвайки тази комбинация виждаме че y = 1 e възможно за всяко x>2.

Да видим кога y=2 е възможно
За 2 знаем, че ни трябва комбинация от 6 най-малко:
>><>><
Значи всичко под 6 не става, а всичко над 6 става използвайки подобно решение като при 1. Например за 8:
>>>><>><

И така намерихме следната формула:

y = k e възможно когато $3k \le x$

С което мисля задачата "За всяко цяло x (x≥2) да се намерят всички цели числа, които са възможни стойности на y." е решена.

[Гост]

------------------------------------------------------------------------------------------------
Благодаря Ви за отговора, peyo.
Първо, поправка на печатни грешки. В постинга си горе, в оценките за y съм объркал. Там, където съм писал следното:

За x≥4:
Ако x≡0(mod4), то y може да е всяко цяло, 0≤y≤x/2 и не е възможно y>x/2.
Ако x≡1(mod4), то y може да е всяко цяло, 0≤y≤[x/2] и не е възможно y>[x/2]+1.
Ако x≡2(mod4), то y може да е всяко цяло, 0≤y≤[x/2] и не е възможно y>[x/2]+2.
Ако x≡3(mod4), то y може да е всяко цяло, 0≤y≤[x/2]+1 и не е възможно y>[x/2]+2.
Интересни са въпросите (на които не мога да отговоря):
Ако x≡1(mod4), то може ли y=[x/2]+1? (Само за x=5 съм намерил, че не е възможно y=3.)
Ако x≡2(mod4), то може ли y=[x/2]+1 и може ли y=[x/2]+?
Ако x≡3(mod4), то може ли y=[x/2]+2?

y = k e възможно когато  3k [tex]\le[/tex] x.
С което мисля задачата "За всяко цяло x (x≥2) да се намерят всички цели числа, които са възможни стойности на y." е решена.

Задачата не е решена.
"...когато 3k[tex]\le[/tex]x." Но не само.
Проблемът е в точното установяване на горната граница за y, т.е. някакво число, зависещо от x, такова, че броят некълвани пилета да не може да го надвиши, по какъвто и начин да става кълването. Т.е. за да се реши напълно, е нужно и да се докаже, че не може y да бъде по-голямо от определена стойност. Точно това е, което не съм успял досега да установя, и за това беше питането ми. Моята идея, благодарение на която достигнах до частичните резултати, за които писах по-горе, е да се разгледа x по модул различни числа. Вие сте получил, че y = k e възможно когато  3k[tex]\le[/tex]x, но това не отговаря на въпроса за горната граница. Защото y може и да е по-голямо.
И сега поправката на моите грешки. Всъщност резултатите, които съм получил (сега вече вярно!), са следните.
За k[tex]\ge[/tex]1:
За x=4k, то y може да е всяко цяло, 0≤y≤2k и не е възможно y[tex]\ge[/tex]2k+1.
За x=4k+1, то y може да е всяко цяло, 0≤y≤2k и не е възможно y[tex]\ge[/tex]2k+1.
За x=4k+2, то y може да е всяко цяло, 0≤y≤2k и не е възможно y[tex]\ge[/tex]2k+2.
За x=4k+3, то y може да е всяко цяло, 0≤y≤2k+1 и не е възможно y[tex]\ge[/tex]2k+2.

И остава неизяснен въпросът може ли ако x=4k+2, то y да е y=2k+1 ?

[peyo]

y = k e възможно когато  3k [tex]\le[/tex] x.
С което мисля задачата "За всяко цяло x (x≥2) да се намерят всички цели числа, които са възможни стойности на y." е решена.

Задачата не е решена.
"...когато 3k[tex]\le[/tex]x." Но не само.
Проблемът е в точното установяване на горната граница за y, т.е. някакво число, зависещо от x, такова, че броят некълвани пилета да не може да го надвиши, по какъвто и начин да става кълването.

Хм. Ок, имам грешка. Твърдението ми, че "в най-добрия случай най-много 1/3 неклъвнати може да имаме" не е вярно, защото при 4 пилета и комбинация >><< имаме 2 неклъвнати, което е 1/2. При 5:
>><<< 2 неклъвнати, значи 2/5.

Да помислим малко дали може да въведем по удобен език с който да работим.
Аз използвам символите <> където показва в каква посока е човката. Например при горния пример
>><<< неклъвнитете са в първата и последните позиции. Но това не е лесно да се види. Като се замислим неклъвнатите пилета винаги са на двойки и те изглеждат така при 4 пилета:
<<>>

Тогава ако повторим тази комбинация:
<<>><<>>

Ще имаме начин да генерираме y=x/2 максимални решение за всички x които се делят на 4. Предполагам, че и ти това казваш с x≡0(mod4) означенията. ( аз лично винаги съм смятал mod синтаксиса за изключително объркващ)

Може ли да имаме резултат по-добър от 1/2? Най-добрата комбинация от 4 дава максимално 1/2. Ако имаме по-голямо от 4, нашата комбинация от 4 ще даде 1/2, останалите максимул 3 символа
<<>><<>
<<>><<<
<<>><<
<<>><>
<<>><
<<>>>
Не дават допълнителни неклъвнати пилета. А преди пова показахме, че всяка двойка неклъвнати пилета е част от <<>> комбинация. С което мисля обхванахме всички случаи и почти убедително доказахме, че горната граница е x/2.

[pal702004]

И остава неизяснен въпросът може ли ако x=4k+2, то y да е y=2k+1 ?

Не може. Нека $x$ е броя на неклъвнатите пилетата, y-клъвнати веднъж, z-клъвнати два пъти.
Броят на пилетата е n, както и броят на клъвванията. Имаме:

$\begin{cases} x+y+z=n\\x\cdot 0+y\cdot 1 +z\cdot 2=n \end{cases}$

Откъдето $z=x$ или броят на неклъвнатите пилета е равен на клъвнатите два пъти. И имаме

$2x+y=n$. За да максимизираме $x$ трябва да минимизираме $y$. Но възможно ли е при $n=4k+2,\;y=0$. Да номерираме пилетата по часовниковата стрелка. Пилетата на четна позиция кълват тези на нечетна и обатно. Така че пилетата на нечетна позиция ще получат общо $2k+1$ клъввания. И няма как всички те получат или 0, или 2 клъввания. Ще има поне едно, клъвнато веднъж. Същото се отнася и за тези на четна позиция. Така че максимума в този случай е $2k$ неклъвнати. В идеалния вариант, при $n$ кратно на 4 разпределението е

ккннккнн....ккнн

като клъвнатите са по два пъти.