Задача 276 (жабоци)

**Bibi** · 19-07-05, 00:29

http://internetka.net/images/flash/frogs.swf

7 камъка, 3 жаби-момичета и 3 жабока-момчета. Трябва да си сменят местата.

Правилата:

Всяка жабка може или да се премести с едно камъче напред (ако е свободно), или да прескочи друга жаба.

Въпросите:

- Колко е минималният брой ходове за решаване на задачата с 2Х жаби

и 2Х+1 камъчета?

- А колко е минималният брой ходове при 2Х+У камъка?

**kamenf** · 19-07-05, 00:38

За 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 камъчета ще го мисля....

**Bibi** · 19-07-05, 01:12

Тези са толкова наистина.

Всяка жаба, за да стигне до новото си място без прескачане трябва да направи Х+1 хода. Като се умножи по броя на жабите става общо 2Х(Х+1). При прескок обаче се пести по един ход. Броят на прескоците при само едно свободно камъче е равен на броя на разминаванията мъжка-женска, защото едноцветни жаби не бива да се прескачат - задръства се движението и не може да стане размяната.

Разминаванията са Х^2. Вадим ги и получаваме оптималния брой ходове Х(Х+2).

**kamenf** · 19-07-05, 01:21

За 2X+Y камъчета, задачката я докарваме предварително до 2X+1 камъчета, местейки самоединия комплект жаби, като за целта се самопрескачат. Така за Y камъчета правим допълнително (Y-1)(X-1) хода или глобално:

(Y-1)(X-1) + X(X+2)

**xyzt2** · 20-07-05, 12:50

<blockquote id="quote">quote:<table border="0" id="quote"><tr id="quote"><td class="quote" id="quote">За 2X+Y камъчета, задачката я докарваме предварително до 2X+1 камъчета</td id="quote"></tr id="quote"></table id="quote"></blockquote 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) хода

**Avis** · 20-07-05, 13:12

При 2X+1 камъчета задачата има точно две инвариантни решения, така че минималният и максималният брой ходове са еднакви. При Y>1 задачата се свежда до предишната по различни начини (също с огледален вариант), но пак броят на ходовете е постоянен.

**Bibi** · 20-07-05, 14:37

@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,

Ще дадеш ли нова задача?

**Avis** · 20-07-05, 15:04

@Bibi

Аз съм си перманентно изгубен...

Задачата беше публикувана навремето в едно компютърно списание (май Computer, ще проверя), та там имаше и доказателство, което ще потърся, за да не се мъча да го възстановявам сега.

Добавено:

Списанието е Computer, бр.10/97; като автор на задачата посочват Едуард Люка (1842-1891), но няма прецизно доказателство. Разликата в условията е само възможността да се прескачат еднополови жабоци, на което не обърнах внимание в началото (явно подсъзнанието ми е отхвърлило подобно извращение [:I]), а това естествено променя броя на ходовете при Y>1.

**Bibi** · 20-07-05, 19:13

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

Междувременно, ако някой има готово условие, да си каже, без бой. [}

]

Ясене, онази с многото науки до къде е?

**Yasen6275** · 21-07-05, 14:27

До час, час и половина ще я зглобя.

Задача 276 (жабоци)

Инструменти на темите