Dwójkowo troiście
Zadań binarnych (dwójkowych, zero-jedynkowych), a ściślej – ich rodzajów, jest albo bardzo dużo, albo bardzo mało. Zależy jak rozumieć w tym przypadku binarność.
Miejscem „akcji” większości łamigłówek jest pokratkowany diagram. Jeżeli rozwiązanie polega na przypisaniu każdej kratce jednego z dwóch możliwych stanów, a więc np. na ustaleniu, jak w nurikabe, czy pole będzie czarne, czy białe, to łamigłówkę możemy określić jako binarną. Takich rodzajów zadań jest bardzo dużo, zwłaszcza że zaliczenie do tej grupy nie musi wiązać się z diagramem w kratkę.
Bardzo mało jest natomiast rodzajów zadań, które można by nazwać dwójkowymi, ponieważ występują w nich liczby binarne. Jeden przykład był w poprzednim wpisie. W następnym zapewne jeszcze coś się pojawi.
Wyróżniłbym także trzeci typ zadań zero-jedynkowych – taki, w którym pojawiają się liczby binarne, ale dopiero na etapie rozwiązywania. Inaczej mówiąc, można zmagać się z takimi zadaniami, „tłumacząc” liczby z układu dziesiętnego na dwójkowy. Zwykle nie jest to konieczne, ale bywa prostsze, wygodne lub eleganckie.
Oto przykład.
W niektórych konkurencjach sportowych kobiety są równouprawnione w tym sensie, że startują i klasyfikowane są razem z mężczyznami. Napisałem „niektórych”, choć ad hoc przychodzi mi do głowy tylko jeździectwo. Załóżmy zatem, że w konkursie jeździeckim startowało 100 osób, z czego połowę stanowiły amazonki. Po zakończeniu pojawiły się trzy listy. Pierwsza obejmowała całą setkę startujących, druga i trzecia (nieoficjalne) – oddzielnie jeźdźców i amazonki.
Czy jest możliwe, że zarówno na liście pań, jak i panów żadna osoba nie znalazła się na miejscu oznaczonym liczbą dwukrotnie większą, niż miejsce innej osoby na tej samej liście?
I drugie pytanie: jak rozwiązać to zadanie korzystając z liczb binarnych?
Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3-4 dni.
Komentarze
Dla każdej liczby nieparzystej t rozważmy ciąg t,2t,4t,… dla xt <= 100. Z założenia żadne 2 kolejne liczby z jednego z takich ciągów nie mogą być wynikami osób tej samej płci. Dlatego „rozdzielamy” takie ciągi po równo między kobiety i mężczyzn. Jeśli wielkość ciągu jest parzysta to super, jeśli nie, to musimy faworyzować jedną z płci. Pytanie, czy uda się faworyzować obie tę samą liczbę razy. Da się, bo liczba ciągów nieparzystej wielkości = 34, także po 17 razy będą faworyzowane kobiety (dostaną z danego ciągu więcej pozycji), a 17x mężczyźni.
Oczywiście żadne 2 tak zdefiniowane ciągi nie mają wspólnych elementów, bo każdą liczbę da się zapisać jako x*2^y, gdzie x – nieparzyste, jednoznacznie wyznaczone.
Witam Pana, panie Marku!
Przepraszam, ale chciałem informować wszystkich miłośników gier, że dziś zamknęła się edycja 2010 Mistrzostwa Europy w szachy chińskie. Zapraszam na mój mały blog http://szachychinskie.bloog.pl/
Dziękuję za cierpliwość
Pozdrawiam
Wydaje się, że to jest możliwe – i to nawet w ponad 26!*2^12 możliwościach.
Liczby binarne widzę tutaj w conajmniej paru miejscach – np. w fakcie, że dane miejsce znajduje się wyłącznie na liście pań lub panów (tj. jeśli nie ma go tu, to na pewno jest tam). Albo, że liczba binarna Y będąca podwojeniem liczby X to liczba X z dodanym zerem na końcu (może to do czegoś służy). Przy czym na mój umysł to cudowanie post factum i pewnie chodzi o coś innego ;].
Myślę, że jest 2^(17) * (34 po 17) takich ustawień.
I owszem, da się. Miejsce pierwsze dajemy np. paniom, mnozymy x2=4, wynik dajemy panom, x2=8 paniom, x2=16 panom, itd. aż do 64. Potem miejsce trzecie rozdajemy dowolnie i mnożymy x2 i oddajemy drugiej stronie, itd., potem siódme, dziewiąte i tak dalej aż dojdziemy do 50, miejsca powyżej 50-tki rozdzielamy dowolnie byle ilość dla każdej płci się zgodziła.
…poprawka – ok. 2^40 możliwości, i tak galancie.
Zadanie jest trochę niejasno sformułowane, ale domyślam się, że chodzi o to, by zbiór liczb od 1 do 100 podzielić na dwa podzbiory po 50 sztuk
Otóż to
mp
Odpowiedź na pierwsze pytanie brzmi tak