Особено неприятна комбинаторика

[adrian]

Дадена е последователност от А нули и B единици.Върху
тази последователност може да се извършва следния ход:
Избират се точно К на брой елементи от последователността и техните
стойности си сменят стойността(т.е. нулите стават на единици,
а единиците на нули). При ход може да се избират които и да са К елемента
на последователността, без значение от техните стойности или
дали стойностите им са били вече променяни. Целта на задачата е да
се намери минималния брой ходове, след които последователността
да се превърне в последователност, в която всички елементи са единици.
Целта е да се намери минималния брой ходове, а не самите ходове.
Ако не е възможно последователността да се преобразува в последователност
само от единици, да се покаже защо не може.А,B и K са дадени числа,като K<=100 000,
A<=100 000, B<=100 000.
Един пример,ако е дадена последователност от 4 нули и 0 единици и
К = 3, отговора е 4,защото:
0. 0000 (начална последователност)

1. 1110 (първите три елемента се променят след ход)

2. 1001 (последните три елемента се променят след ход)

3. 0100 (първи, втори и четвърти елементи се променят след ход)

4. 1111 (първи,трети и четвърти елементи се променят след ход)

Това е задачата, сега пускам и нейното решение,което
е толкова решение,колкото само да напишем изречението 'няма решение в естествени
числа >2' е решение на голямата теорема на Ферма :

Решение:
Решението е да се пробва дали отговора е 1 ход, дали отговора е
2 хода, дали е 3 хода,..., дали отговора е A+B хода просто
чрез проверка дали тези числа (1,2,3,...,А+B) са отговора.
Т.е. проверяваме дали отговора е 1.Ако не е 1, след това проверяваме дали
отговора е 2, ако не е 2, после с 3, и т.н. до A+B.
Как се прави проверката:
1) Броя на най-малкия брой ходове, които преобразуват
последователността в такава съдържаща само единци е
по-малък или равен на A+B. Д-во:
Нека [а_0,а_1,...,а_n] (а_0 = А, a_n = 0), е поредицата
от броя нули в поредицата от най-малък брой ходове ,които дават
последователност само от единици.Тъй като 0<=а_i<=A+B,то
ако (n+1) > (A+B+1), тогава от принципа на Дирихле следва, че
има число, което се среща повече от веднъж в поредицата и тогава
тази поредица не е с най-малък брой ходове,което противоречи
на допускането. Така отговора на задачата е по-малък или равен на A+B.

За да проверим дали X на брой хода са достатъчни, за да превърнем
дадената последователност в такава само от единици,трябва
да направим A смени на елементите с начална стойност нула,
плюс определен брой двойни смени върху произволен елемент.
Общият брой смени тогава е K*X, а броят на двойните смени е
rest=(K*x-A)/2 . По този начин първото условие(обозначаваме го с *) е
(K*X-A) да е четно, а K*X-A трябва да е >=0.
След това, ако елемент ,върху който правим двойна смяна е такъв,който
има начална стойност нула,тогава максималният брой от двойни смени
върху този елемент е най-голямото цяло число, не надвишаващо
(X-1)/2, ще го обозначим с floor,т.е. floor((X-1)/2).Това е така,защото
при един от ходовете трябва да направим единична смяна(а не двойна)
върху този елемент.
За останлите елементи максималният брой от двойни смени е
floor(X/2). Така максималният брой от двойни смени,които можем да направим
е max_double_flips = A*floor((X-1)/2) + B*floor(X/2) ,така че
второто условие(обозначваме го с **) е: rest <= max_double_flips .
Ако тези две условия са изпълнени,тогава X e валиден брой
от ходове, които позволяват дадената в условието последователност да се
преобразува до последователност само от единици, иначе X не е
валиден брой ходове.

Това е задачата и нейното решение, което твърди, че ако (*) и (**)
са изпълнени, то това е достатъчно,за да се заключи, че с
X брой хода дадената последователност се преобразува в такава съдържаща само единици.
Въпросът ми е защо това е така,т.е. защо ако са изпълнени
(*) и (**) ,то това е ДОСТАТЪЧНО да се твърди, че с X хода
може да се стигне до последователност само от единици.