Algorytm znajdowania łańcucha:
1. Niech białe ogniwo oznacza +1, czerwone ogniwo oznacza -1.
2. Rozpoczynając w dowolnym miejscu (nazywanym odtąd miejscem nr1) przypisujemy kolejnym miejscom wartości na zasadzie:
2a) miejsce nr1 jeśli białe to +1, jeśli czerwone to -1
2b) kolejne miejsce bierze wartość poprzedniego i jeśli samo jest białe, to zwiększa tę wartość o +1, jeśli jest czerwone to zmniejsza o -1. Np. miejsce nr5 ma wartość 3, a na miejscu nr6 mamy czerwone ogniwo to wartość miejsca nr6=3-1=2.
3. Dostajemy w ten sposób macierz o wymiarach 2xN, z której budujemy nasze rozwiązanie, które ma postać macierzy 2x(N/2)
3a) od wartości miejsca nr1 odejmujemy wartość miejsca nr[(N/2)+1], od wartości miejsca nr"k" odejmujemy wartość miejsca nr[(N/2)+"k"], aż "k" będzie równe N/2. Wyniki wpisujemy odpowiednio do macierzy.
3b) jeśli wynik wynosi 0, to mamy miejsce cięcia. Może być więcej niż jedno miejsce cięcia.

Pozdrawiam

---

Grądy, łęgi, olsy, bory i buczyny.

Sposób wygląda na trochę skomplikowany.
Poza tym -
>.. jeśli wynik wynosi 0, to mamy miejsce cięcia.
- zdaje się polegać na żmudnym sprawdzaniu kolejnych miejsc do cięcia, a to przy długim łańcuchu może potrwać..

> Może być więcej niż jedno miejsce cięcia.
Np. dla łańcucha naprzemiennego.

Pozdrawiam

Nie ma prostszego - potrzebujesz wszystkich informacji by wyznaczyć cięcie.

Edit:Znam dowód na to, że podział na dwa łańcuchy zawsze występuje, ale nie chcę psuć zabawy potencjalnym uczestnikom.

Pozdrawiam

---

Grądy, łęgi, olsy, bory i buczyny.

>Nie ma prostszego - potrzebujesz wszystkich informacji by wyznaczyć cięcie.
>Edit:Znam dowód na to, że podział na dwa łańcuchy zawsze występuje, ale nie chcę psuć zabawy potencjalnym uczestnikom.
Psuj. Zżera mnie ciekawość. Nie wymyślę nic więcej ponad to co wymyśliłam, a i to za bardzo nie nadaje się do przedstawienia.

Dowód przez sprowadzenie do absurdu.
Teza: istnieją łańcuchy dwukolorowe (o składzie 2n czerwonych i 2n białych), które nie dają się podzielić na podłańcuchy (o składzie n czerwonych i n białych).
1. Niech czerwony będzie -1, biały +1, jak w moim algorytmie wyszukiwania.
2. Wybierzmy dowolny podział dużego łańcucha na dwa mniejsze o równej długości. Jeden z mniejszych łańcuchów będzie miał łączną sumę elementów ="w", drugi ="-w", gdzie "w" należy do całkowitych, jest większe od 0 (to z tezy wynika) i mniejsze bądź równe 2n (to z ilości kolorowych ogniw wynika).
3. Zróbmy podział sąsiedzki:
Wyobrazić to sobie można tak, że ogniwa łańcucha są ustawione w okrąg lub jak cyfry na tarczy zegara i przesuwamy linię cięcia o jeden element. Powoduje to utratę jednego elementu "z tyłu" i dołączenie jednego elementu "z przodu".
4. Podział sąsiedzki ma swoją własną sumę. Może ona wynosić tyle samo, co w pierwotnym podziale (straciliśmy ogniwo danego koloru i doszło nam ogniwo dokładnie tego samego koloru), być mniejsza o -2 (odpadł nam biały element, przyszedł nowy czerwony), być większa o +2 (odpadł czerwony element, doszedł nowy biały).
5. Robimy kolejne podziały sąsiedzkie według podanego schematu, aż uzyskamy "sytuację odwróconą": pokonaliśmy 180 stopni. Nasza suma z "w" zmnieniła się na tej drodze w "-w". Czy przeszła przez zero?
5a. Jeśli "w" była parzysta to TAK.
5b. Jeśli "w" była nieparzysta, to NIE. Ale ponieważ ogniw danego koloru jest 2n, to "w" zawsze jest parzyste, więc ta sytuacja odpada. Podpunkt 5a załatwia dowód.

Pozdrawiam

---

Grądy, łęgi, olsy, bory i buczyny.

Podpunkt 5a załatwia dowód.
O dziwo całość zrozumiałam. Dziękuję.

>Nie ma prostszego

A może zadanie da się sprowadzić/uogólnić do podziału bułki z masłem (tu z keczupem)) jednym cięciem na dwie 'sprawiedliwe' części?

>>Nie ma prostszego
>A może zadanie da się sprowadzić/uogólnić do podziału bułki z masłem (tu z keczupem)) jednym cięciem na dwie 'sprawiedliwe' części?
Nie znam tego z bułką zadania.
Napisałem, że nie ma prostszego, bo wymyślając algorytm miałem przykładowy łańcuch:
b-b-b-c-c-c-c-b-c-c-b-c-b-b-b-c. Ma on jedno rozwiązanie (jeden możliwy podział). Gdy zakryjemy najmniejszy możliwy kawałek informacji w kluczowym miejscu (dla odpowiednich, ustalonych dla przypadku, miejsc "k" i N/2+"k") :
b-b-b-c-c-c-c-X-c-c-b-c-b-b-b-X, to nie jest możliwe rozstrzygnięcie, gdzie będzie rozwiązanie (jest więcej niż 1 możliwość rozwiązania). Wynika to z tego, że powyższe "blokuje" wszystkie komplementarne podłańcuchy o długości N/2.

Tyle na szybko mogę powiedzieć.

Pozdrawiam

---

Grądy, łęgi, olsy, bory i buczyny.

>Nie znam tego z bułką zadania.
Pokazuje się w nim, że kromkę z masłem da się podzielić na 'równe-równe' części jednym prostopadłym cięciem. Jeśli zaś dopuścić cięcia ukośne, to nawet bułkę z masłem i serem można podzielić na 'równe-równe-równe' połowy jedną płaszczyzną. Znany mi sposób wykorzystuje pojęcie środka masy poszczególnych składników kanapki i jej całej.

> Gdy zakryjemy najmniejszy możliwy kawałek informacji (..), to nie jest możliwe rozstrzygnięcie, gdzie będzie rozwiązanie
Też mi się zdaje, że nie ma rozwiązań przez redukuję długości łańcucha, lecz tylko 'globalne'.

>>Nie znam tego z bułką zadania.
>Pokazuje się w nim, że kromkę z masłem da się podzielić na 'równe-równe' części jednym prostopadłym cięciem. Jeśli zaś dopuścić cięcia ukośne, to nawet bułkę z masłem i serem można podzielić na 'równe-równe-równe' połowy jedną płaszczyzną. Znany mi sposób wykorzystuje pojęcie środka masy poszczególnych składników kanapki i jej całej.
No to spróbujmy. Weźmy układ:
b-b-b-b-c-c-c-c-b-b-c-c-b-b-c-c,
Możliwe jest pięć cięć dobrych (i trzy złe cięcia). Dość łatwo ustalić środek ciężkości (czy nawet dwa dla kolorów). I co dalej?

Edit: wcale nie tak łatwo ustalić środek ciężkości, jeśli nie robi się tego w dwóch wymiarach.

Pozdrawiam

---

Grądy, łęgi, olsy, bory i buczyny.

>.. nie tak łatwo ustalić środek ciężkości, jeśli nie robi się tego w dwóch wymiarach.
Zgadza się. Łańcuch można co prawda rozłożyć na stole w kształt kwadratu, ale nadal łatwo nie jest..
Gdyby jednak znaleźć środki mas bieli i czerwieni, to linia przez nie przechodząca powinna dzielić dobrze.

>>.. nie tak łatwo ustalić środek ciężkości, jeśli nie robi się tego w dwóch wymiarach.
>Zgadza się. Łańcuch można co prawda rozłożyć na stole w kształt kwadratu, ale nadal łatwo nie jest..
>Gdyby jednak znaleźć środki mas bieli i czerwieni, to linia przez nie przechodząca powinna dzielić dobrze.
Nie. W moim przykładzie linia przechodząca przez te środki dzieli źle.
Dlatego zresztą zacząłem szukać czegoś, co by odpowiadało pojęciu środka ciężkości, ale możnaby to przypisać jako punkt w łańcuchu.

Pozdrawiam

---

Grądy, łęgi, olsy, bory i buczyny.

b b b b c
c . . . c
c . . . c
b . . . c
b c c b b

Jeśli teraz przyjąć początek układu współrzędnych w środku, to po analitycznym wyliczeniu powinno wyjść dobrze.
Według moich rachunków środek masy białych to (-3/8, 1/8), stąd prosta dzieląca: y = -1/3 x.

[Rysunek miał być kwadratowy.]

Jeśli zalożysz, że "b" i "c" to masy punktowe, to wyjdzie dobrze. Jak założysz, że to ogniwa styczne ze sobą, to już nie wyjdzie dobrze. W każdym razie, jak przesuniesz na tym kwadracie łańcuch o jeden krok w koło, czy o ile tam, to w końcu trafisz na takie układy, dla których nie będzie pasować.
Kolejnym problemem jest, że jest 5 rozwiązań dla tego układu, a Twój sposób jest w stanie pokazać najwyżej jedno (chyba, że po ułożeniu łańcucha w inny sposób wyjdą inne, ale tego nie wiem).
Tak czy inaczej, jeśli Twój sposób działa, to powinien być możliwy dowód wykazujący ten fakt. Zastanowię się nad tym.

Pozdrawiam

---

Grądy, łęgi, olsy, bory i buczyny.

> Jak założysz, że to ogniwa styczne ze sobą, to już nie wyjdzie dobrze.
Słusznie. Lepszym modelem niż łańcuch byłby chyba sznur nie-za-gęsto rozmieszczonych koralików.
>.. trafisz na takie układy, dla których nie będzie pasować.
Raczej zawsze będzie pasować, bo skoro środki mas da się jednoznacznie wskazać, to biel, czerwień i cały łańcuch będą względem wyznaczonej prostej dobrze wyważone.
>.. chyba, że po ułożeniu łańcucha w inny sposób wyjdą inne rozwiązania
Najpewniej tak właśnie.

edit:
Właściwie nie ma potrzeby wyznaczać osi wyważenia - wystarczy jej punkt przecięcia z którymś z boków kwadratu, a ten powinien jakoś wprost wynikać ze współrzędnych środka masy jednego z kolorów..

>Raczej zawsze będzie pasować, bo skoro środki mas da się jednoznacznie wskazać, to biel, czerwień i cały łańcuch będą względem wyznaczonej prostej dobrze wyważone.
Tylko dla okręgu tak jest.

>Właściwie nie ma potrzeby wyznaczać osi wyważenia - wystarczy jej punkt przecięcia z którymś z boków kwadratu, a ten powinien jakoś wprost wynikać ze współrzędnych środka masy jednego z kolorów..
A jak skomentujesz to, że w ten sposób mamy tylko jedno rozwiązanie.

Pozdrawiam

---

Grądy, łęgi, olsy, bory i buczyny.

> Sposób wygląda na trochę skomplikowany.

Wersja uproszczona:
- rozkładamy sobie łańcuch w kółeczko, żeby dało się wyróżnić kierunek
- dla każdego ogniwa definiujemy "półłańcuch" jako N kolejnych ogniw, licząc (zgodnie ze wskazówkami zegara) od tegoż ogniwa włącznie
- definiujemy funkcję, która dla danego ogniwa bierze jego półłańcuch i zlicza w nim ilość czerwonych ogniw (białe olewamy, informacja o nich jest redundantna)

Dziedzina funkcji to wszystkie 2N ogniw, wartości może przyjmować od 0 do N.
Podziału należy dokonać odcinając półłańcuch, dla którego wartość funkcji wynosi N/2.
Dla łańcucha naprzemiennego mamy funkcję stałą (=N/2), więc tniemy gdziekolwiek.

Zauważamy, że wartości naszej funkcji dla sąsiednich ogniw mogą się różnić o {-1, 0, +1}.
Stąd prosty wniosek, że miejsce podziału musi istnieć, bo albo mamy funkcję stałą (=N/2), albo "schodkową", ciągłą od miejsca w którym jest mniej niż N/2 do miejsca w którym jest więcej niż N/2 - a zatem przechodzącą (co najmniej raz) przez N/2.
Czyli analogicznie jak u sceptymuchy, z tym że On miał wyższe schodki (i szukaną wartość =0).

> (...) zdaje się polegać na żmudnym sprawdzaniu kolejnych miejsc do cięcia

Można sobie ułatwić obliczenia, bo różnicę wartości dla sąsiednich półłańcuchów da się wyznaczyć sprawdzając tylko kolory dwóch skrajnych ogniw, którymi te półańcuchy się różnią. Można też rozpocząć liczenie w "najbardziej prawdopodobnym miejscu", czyli (mniej więcej) w środku największego czerwonego klastra. Jeżeli są dwa duże klastry - zaczynamy w środku pomiędzy nimi, itd. Potem przesuwamy się troszkę w jedną, troszkę w drugą stronę - w kierunku, w którym wartość funkcji zbliża się do pożądanego N/2.