Inspekcja w wypożyczalni
Minęły święta, pora zająć się japońskimi samochodami z zadania o wypożyczalni Jap Co.
Każde auto można określić trzema cyframi, z których każda odpowiada innej z trzech cech (marka, kolor, typ nadwozia) i może przybierać trzy wartości (0,1,2), oznaczające konkretne przykłady w ramach danej cechy (jedną z trzech marek, jeden z trzech kolorów lub jeden z trzech typów nadwozi). Ponieważ nie ma dwóch identycznych aut, więc wszystkich może być co najwyżej (pomijamy na razie ograniczenie wynikające z rozmowy z klientem) 3^3 = 27. Oto one (słupek A):
W takiej formie samochodom odpowiada 27 kolejnych liczb naturalnych zapisanych w układzie trójkowym, a zadanie (teraz uwzględniamy rozmowę z klientem) sprowadza się do tego, by wybrać spośród nich jak najwięcej takich, wśród których nie będzie trzech z wszystkimi jednakowymi lub wszystkimi różnymi cyframi na każdej z tych samych kolejnych pozycji, czyli nie spełniających warunku klienta.
Prawdopodobnie nie ma algebraicznego (wzór) lub prostego dedukcyjnego sposobu uporania się z tym zadaniem. Trzeba próbować.
Na wstępie warto zauważyć, że dowolną parę liczb można uzupełnić tylko jedną taką liczbą, by warunek klienta był spełniony. Na przykład, parę 020 i 210 dopełnia do „kompletu” tylko 100 – różne cyfry są na pierwszych pozycjach, różne na drugich, takie same na trzecich.
Zacznijmy od wybrania ze słupka A pary liczb, a z pozostałych usuńmy jedną liczbę – tę, która tworzy z wybranymi wspomniany „komplet”. Następnie dobieramy trzecią liczbę, czyli wśród wybranych pojawiają się dwie nowe pary, a więc z pozostałych usuwamy dwie liczby. Potem dobieramy czwartą liczbę, zatem wśród wybranych pojawiają się trzy nowe pary, więc z pozostałych musimy usunąć trzy liczby itd. W trakcie tego procesu będzie się czasem zdarzać tak, że niektóre pary do usunięcia na danym etapie okażą się usunięte wcześniej.
Gdy zaczniemy od góry słupka A, czyli w pierwszej parze będzie 000 i 001, a na początku każdego etapu będziemy dobierać, czyli „zazieleniać” zawsze pierwszą wolną liczbę, to na końcu pozostanie OSIEM wybranych liczb (zielone w słupku B).
Po rozpoczęciu od dołu i dobieraniu zawsze pierwszej wolnej liczby od końca – efekt będzie taki, jak w słupku C, czyli symetryczny względem B.
Zaczynając od przypadkowej pary (np. 000 i 012), ale dobierając zawsze kolejną wolną, czyli jak w słupku B, także zakończymy ÓSEMKĄ (słupek D).
W przypadkach B, C i D dowolna dziewiąta liczba dobrana spośród usuniętych (czerwonych) uzupełni jakąś zieloną parę do trójki spełniającej życzenie klienta wypożyczalni. Czyżby zatem wypożyczalnia dysponowała najwyżej 9 autami, w tym jednym niesprawnym?
Zróbmy drobną zmianę. Gdy stosując metodę, której efektem jest słupek D, zakończymy szósty etap dobierania i usuwania liczb, wolne pozostaną 4 liczby (słupek E). Wybierzmy teraz nie kolejną (111), tylko 121. Jeśli teraz usuniemy, czyli zaczerwienimy zbędne pary, to okaże się, że zielonych pozostanie… DZIEWIĘĆ (słupek F). Ot, niespodzianka. Skąd się wzięło przedtem nie ujawniające się dziewiąte auto – to dopiero zagadka. A czy nie udałoby się przeskoczyć także dziewięciu? Niestety, nie. Korzystając z komputera można udowodnić, że niezależnie od której pary zaczniemy i w jakiej kolejności będziemy dobierać dalsze liczby, zawsze dotrzemy najwyżej do DZIEWIĘCIU zielonych liczb-samochodów, a zatem wszystkich aut w wypożyczalni było DZIESIĘĆ. Komputerowy dowód, polegający na sprawdzeniu wszystkich możliwości, jest żmudny i nieelegancki. Niestety, prostego eleganckiego dowodu nie znam, a nieprosty jest tak skomplikowany, że nie odważę się go tutaj przytoczyć.
Wyobraźmy sobie teraz, że zadanie z autami uzupełniamy o kolejne cechy, czyli poza marką, kolorem i typem nadwozia pojawi się kolor tapicerki, rodzaj opon, typ hamulców itd. Każdej z nowych cech także przypiszemy trzy wartości, dajmy na to oponom Bridgestone – 0, Goodyear – 1, Michelin – 2. Przy pięciu cechach samochodom będą odpowiadać liczby pięciocyfrowe, np. 10403 10202. Analogicznie zmieni się życzenie klienta: w trzech wybranych samochodach wszystkie wartości każdej z pięciu cech powinny być różne lub jednakowe. Końcowe pytanie pozostaje bez zmian: iloma co najwyżej różnymi autami dysponuje wypożyczalnia, jeśli przy jednym niesprawnym takie życzenie NIE może być spełnione?
Okazuje się, iż stopień trudności zadania rośnie tak szybko, że współczesne komputery już dla sześciu cech w rozsądnym czasie z zadaniem sobie nie radzą. Dla pięciu cech ustalono i udowodniono dopiero w roku 2002, że rozwiązaniem jest 45 (46 po dodaniu naprawionego samochodu), a w dowodzie pojawiają się „straszne” pojęcia, np. transformacja Fouriera…
Dalej już nie będę Państwa straszył. Obawiam się, że i tak słupkami wymęczyłem tych, którzy przebrnęli przez ten wpis.
Nagroda za rozwiązanie zadania o wypożyczalni Jap Co. przypadła w wyniku losowania szachowi. Uwzględniłem uwagę zawartą w komentarzu Enzo, czyli 9 także uznawałem za poprawną odpowiedź, jeśli oznaczała liczbę aut bez jednego znajdującego się w naprawie.
Laureata proszę o kontakt pod adresem m.penszko@polityka.com.pl w celu ustalenia sposobu przekazania nagrody ufundowanej przez hurtownię gier Rost. Jest nią, jak słusznie zauważyli Robert_C i najata, gra SET! Jej strona matematyczna jest bliźniaczo podobna do struktury cech i wartości w zadaniu o autach. Nieco dokładniej o tej grze – w następnym wpisie.
Komentarze
Widząc po opisie jakie trudności sprawia znalezienie maksymalnej liczby samochodów o pięciu i więcej cechach spełniających wymagania klienta, to szkoda, że obok zadania o trzech cechach nie pojawiło się zadanie dla pięciu cech. Wówczas ciekawie mogłoby wyglądać porównanie wyników uzyskanych przez główkołamaczy do komputerowego maksimum.
Podany przykład liczby pięciocyfrowej (10403) jest chyba nie najlepszy, bo sugeruje przypisanie niektórym cechom pięciu wartości.
Pozdrawiam
Dziękuję Panie Andrzeju – także za łagodne określenie „nienajlepszy”. Poprawiłem.
mp