Магия или ... (Н. Белухов, P. Mebane)

[drago]

Нека $k$ е положително цяло число. Илюзионист изпълява следния номер. Дава на публиката $n=k!+k-1$ топки номерирани с числата от $1$ до $n$. Публиката ги подрежда в редица, така както иска. Асистентката на магьосника ги поглежда, избира $k$ последователни топки в тази редица и ги покрива с нейния дълъг шал. След това се появява илюзиониста, мисли известно време над тази частично покрита редица от числа, и отгатва точната последователност на топките под шала.
Открийте стратегия, която магьосникът и неговия асистент да следват, така че да осъществят номера.

Автори: Николай Белухов и Palmer Mebane. Задачата е A.760 от брой октомври 2019 на KöMaL.

[Davids]

Само да доизясним, произволна подредица от $k$ последователни топки ли покрива асистентката със своя необичайно дълъг шал? Щом не е уточнено каква е тази подредица де, би трябвало да се подразбира, че е произволна, ама все пак да си питам.

Или всъщност идеята на задачата е, че това, точно коя подредица асистентката покрива, е част от стратегията, която трябва да открием?

[drago]

Няма как редицата да е произволна, иначе няма как да се отгатнат. Илюзионистът и асистентката му имат предваритено изработена стратегия и работят в екип. Тя избира точно тези последователни топки, така че магьосника да познае, следвайки конвенцията.
Малко пипнах условието, за да е по-ясен този момент. Може да видиш и оригиналното условие в линка. Там няма решение, така че не се притеснявай.

[drago]

Задачата имаше още едно изискване, което аз нарочно изпуснах (може да го видите в линка към KoMaL) поради две причини. Прави я по-трудна и е от оптимизационен харектер, т.е. малко изкуствено налага допълнително ограничение към стратегията. Именно - времето за калкулации, които илюзиониста/асистенката прави, да бъде полиномиално спрямо $n$. Пак ще се върна към това изискване, а сега на въпроса как би следвало да изглежда една успешна стратегия.

Представете си един вертикален списък със всички възможни пермуртации на числата от $1$ до $n$. Отдясно срещу всяка пермутация записваме действието на асистентката, което е позицията, от която започва шала и (число между $1$ и $n-k+1$) и поредицата от числа, които остават като се махнат тези под шала. Т.е. отдясно записваме това, което вижда магьосника. Ако такава стратегия съществува тази таблица на съотвествието ще може да бъде попълнена. Да видим какви свойства трябва да има тази таблица. Ами, не може да има два еднакви записа в дясната колонка срещу две различни пермутации. Т.е. не може да има две различни пермутации, на които да съотвестват една и съща позиция на шала и като се сложи този шал на тази позиция в/у всяка от двете да се виждат едни и същи поредици от числа. Ако има такива редове илюзиониста няма как да разбере точно върху коя от двете пермутации е оперирала асистентката. На езика, като в дебелите книги, тази функция на съотвествието трябва да е инекция. Ако съществува исканата стратегия, така описаното съотвествие и инекция и обратно, ако има такава функция, то очевидно има и стратегия. Асистентката намира по таблицата пермутацията, която публиката е дала и вижда къде трябва да сложи шала. Магьосникът по таблицата намира отдясно конфигурацията, която вижда (позиция на шала + поредицата от видимите числа) и казва оригиналната пермутация, която и съотвества отляво в списъка.

И така, за да има стратегия е необходимо и достатъчно да докажем, че такава функция има. Доказателството на този факт може да намерите в блога ми (все пак, малко реклама ). Сега обратно на пропуснатото ограничение. За да избегнат тази brute force атака, авторите са наложили доп. ограничение, което някак да филтрира само "ефективни" стратегии. Т.е. асистентката вижда пермутацията, прави някакви калкулации, които да не са по порядък повече от $n^2$ или $n^3$ ... и слага шала. Същото и с магьосника. Стратегията описана по-горе не е такава. Най-малкото, за да построим такава функция, само ако знаем, че я има, трябва да почнем да изброяваме всички възможни ф-ии (само домейна им е с размер $n!$). Даже и да има ефективен начин за построяване на такава функция, (а такъв има, такива ф-ии има много и е посочен начин за построяването на всяка от тях) то за дефинирането и пак са необходими $n!$ стъпки - за всеки елемент от домейна и. Обаче $n!$ не е като полином, нарастването му е експоненциално.

Интересно е да се види тази тема в AoPS - там единия от авторите (Palmer Mebane) хвърля някаква светлина в/у алгоритъма, който е предложил. Това е и информация и за начина, по-който е създадена задачата. И още нещо. Аз мисля, че тази задача става за IMO. Нещо повече - тя е много по-добра от доста, които се дават там.