Преглед за печат
http://internetka.net/images/flash/frogs.swf
7 камъка, 3 жаби-момичета и 3 жабока-момчета. Трябва да си сменят местата.
Правилата:
Всяка жабка може или да се премести с едно камъче напред (ако е свободно), или да прескочи друга жаба.
Въпросите:
- Колко е минималният брой ходове за решаване на задачата с <b>2Х</b> жаби
и <b>2Х+1</b> камъчета?
- А колко е минималният брой ходове при <b>2Х+У</b> камъка?
За 7 камъка - 15 хода. [;)] За останалото ще му мисля...
//Едит:
Ето и как става:
111_222 - начало
11_1222 - 1
1121_22 - 2
11212_2 - 3
112_212 - 4
1_21212 - 5
_121212 - 6
21_1212 - 7
2121_12 - 8
212121_ - 9
21212_1 - 10
212_211 - 11
2_21211 - 12
22_1211 - 13
2221_11 - 14
222_111 - 15
//Едит 2:
За 2х2 жаби е с 8 хода.
//Едит 3:
Изобщо - за 2N жаби и 2N+1 камъчета - N*(N+2) хода.
За 2N+Y камъчета ще го мисля....
Тези са толкова наистина.
Всяка жаба, за да стигне до новото си място без прескачане трябва да направи Х+1 хода. Като се умножи по броя на жабите става общо 2Х(Х+1). При прескок обаче се пести по един ход. Броят на прескоците при само едно свободно камъче е равен на броя на разминаванията мъжка-женска, защото едноцветни жаби не бива да се прескачат - задръства се движението и не може да стане размяната.
Разминаванията са Х^2. Вадим ги и получаваме оптималния брой ходове Х(Х+2).
За 2X+Y камъчета, задачката я докарваме предварително до 2X+1 камъчета, местейки самоединия комплект жаби, като за целта се самопрескачат. Така за Y камъчета правим допълнително (Y-1)(X-1) хода или глобално:
(Y-1)(X-1) + X(X+2)
<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">За 2X+Y камъчета, задачката я докарваме предварително до 2X+1 камъчета</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">
и според мен това е идеята. Значи за 2Х+Y предвижваме едните жаби до положение 2X+1, за целта те изминават Y-1 камъчета. Разминаваме ги (това са Х(Х+2) хода както е известно вече). След което другите жаби изминават разстоянието до края т.е. Y-1 камъчета. Следователно задачата се свежда до това за колко хода X жаби изминават разстоянието Y-1 камъчета. Както kamenf е забелязал най добре е да се прескачат. Задачата има 2 случая:
1сл. Х е четно число => (Y-1)*X/2 броя ходове.
2 сл. X e нечетен брой => (Y-1)*(X/2+1) броя ходове.
Oкончателно:
ако X e четно => (Y-1)*X + Х(Х+2)=X(X+Y+1) хода
ако X e нечетно => 2* (Y-1)*(X/2+1) + Х(Х+2)=(X+2)(X+Y-1) хода
При 2X+1 камъчета задачата има точно две инвариантни решения, така че минималният и максималният брой ходове са еднакви. При Y>1 задачата се свежда до предишната по различни начини (също с огледален вариант), но пак броят на ходовете е постоянен.
@xyzt2,
прав си. Отговорите за четно и нечетно Х са различни.
При нечетните имаш малка грешка (защото Х/2 хода не става...)
Ако X = 2s+1, имаме (s+1)(Y-1) за да сведем задачата към предната, или общо:
2(s+1)(Y-1) + X(X+2) = (X+1)(Y-1) + X(X+2) = (X+Y)(X+1) - 1.
@Avis,
къде се изгуби? И ти си прав!
Ако имаш нещо като доказателство, че има единствено решение (с точност до симетрия) на първото условие, напиши го.
@xyzt2,
Ще дадеш ли нова задача?
@Bibi
Аз съм си перманентно изгубен...
Задачата беше публикувана навремето в едно компютърно списание (май Computer, ще проверя), та там имаше и доказателство, което ще потърся, за да не се мъча да го възстановявам сега.
Добавено:
Списанието е Computer, бр.10/97; като автор на задачата посочват Едуард Люка (1842-1891), но няма прецизно доказателство. Разликата в условията е само възможността да се прескачат еднополови жабоци, на което не обърнах внимание в началото (явно подсъзнанието ми е отхвърлило подобно извращение [:I]), а това естествено променя броя на ходовете при Y>1.
Победителят е доста ангажиран и няма да може да ни предложи нова задача, но предлагам да изчакаме да се решат текущите, че се посъбраха и тогава да сложим нова.
Междувременно, ако някой има готово условие, да си каже, без бой. [}:)]
Ясене, онази с многото науки до къде е?
До час, час и половина ще я зглобя.