Pionki na okręgu

mol_ksiazkowy · Post autor: **mol_ksiazkowy** » 5 lip 2008, o 15:18

Na okręgu rozłozone są po pietnascie czarnych i białych pionków. (tak ze razem jest ich n=30). Ruchem nazwiemy dowolna zamiane miejscami pewnych dwóch z nich. Jaka jest najmniejsza liczba ruchów, dzieki której mozna z dowolnego poczatkowego ustawienia doprowadzic do takiego ze zadne dwa piony tego samego koloru nie beda lezec obok siebie...?!?

kuch2r · Post autor: **kuch2r** » 5 lip 2008, o 15:29

M Ciesielski · Post autor: **M Ciesielski** » 5 lip 2008, o 16:03

najmniejsza to chyba 0, bo początkowo mogą być poustawiane na zmianę..

kuch2r · Post autor: **kuch2r** » 5 lip 2008, o 16:07

ale to ma zachodzic dla dowolnego ustawienia, a nie tylko dla szczegolnego przypadku gdzie wszystkie sa juz poustawiane

M Ciesielski · Post autor: **M Ciesielski** » 5 lip 2008, o 23:56

więc jeden, bo tylko jedna para pionków może wymagać przestawienia. poza tym DOWOLNY przypadek w moim mniemaniu zawiera w sobie odpowiedź 0 jak również 1, 2 ...

Qń · Post autor: Qń » 6 lip 2008, o 00:10

kuch2r pisze:7 ?

Aha.

Żeby pokazać, że to wystarczy, można postąpić tak: numerujemy miejsca na okręgu liczbami od 1 do 30 i patrzymy czy więcej czarnych pionków jest na miejscach parzystych czy nieparzystych. Załóżmy bez straty ogólności, że na parzystych - wtedy na nieparzystych jest ich \(\displaystyle{ k q 7}\) i w \(\displaystyle{ k}\) ruchach zamieniamy je z pionkami białymi stojącymi na miejscach parzystych (ich też oczywiście musi być \(\displaystyle{ k}\)).

To rozumowanie wskazuje też, że mniej niż siedem będzie już za mało - kontrprzykładem jest sytuacja, kiedy mamy osiem pionków na miejscach nieparzystych i siedem na nieparzystych.

Q.

PS. baQs - przeanalizuj jeszcze raz treść zadania

M Ciesielski · Post autor: **M Ciesielski** » 13 lip 2008, o 14:04

Qń, ok, przyznaję rację