{"id":184,"date":"2008-03-25T13:36:53","date_gmt":"2008-03-25T12:36:53","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=184"},"modified":"2008-03-27T18:17:27","modified_gmt":"2008-03-27T17:17:27","slug":"inspekcja-w-wypozyczalni","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2008\/03\/25\/inspekcja-w-wypozyczalni\/","title":{"rendered":"Inspekcja w wypo\u017cyczalni"},"content":{"rendered":"

Min\u0119\u0142y \u015bwi\u0119ta, pora zaj\u0105\u0107 si\u0119 japo\u0144skimi samochodami z zadania o wypo\u017cyczalni Jap Co<\/a>.
\nKa\u017cde auto mo\u017cna okre\u015bli\u0107 trzema cyframi, z kt\u00f3rych ka\u017cda odpowiada innej z trzech cech (marka, kolor, typ nadwozia) i mo\u017ce przybiera\u0107 trzy warto\u015bci (0,1,2), oznaczaj\u0105ce konkretne przyk\u0142ady w ramach danej cechy (jedn\u0105 z trzech marek, jeden z trzech kolor\u00f3w lub jeden z trzech typ\u00f3w nadwozi). Poniewa\u017c nie ma dw\u00f3ch identycznych aut, wi\u0119c wszystkich mo\u017ce by\u0107 co najwy\u017cej (pomijamy na razie ograniczenie wynikaj\u0105ce z rozmowy z klientem) 3^3 = 27. Oto one (s\u0142upek A):<\/p>\n

\"Sam_2.jpg\"\u00a0<\/p>\n

W takiej formie samochodom odpowiada 27 kolejnych liczb naturalnych zapisanych w uk\u0142adzie tr\u00f3jkowym, a zadanie (teraz uwzgl\u0119dniamy rozmow\u0119 z klientem) sprowadza si\u0119 do tego, by wybra\u0107 spo\u015br\u00f3d nich jak najwi\u0119cej takich, w\u015br\u00f3d kt\u00f3rych nie b\u0119dzie trzech z wszystkimi jednakowymi lub wszystkimi r\u00f3\u017cnymi cyframi na ka\u017cdej z tych samych kolejnych pozycji, czyli nie spe\u0142niaj\u0105cych warunku klienta.
\nPrawdopodobnie nie ma algebraicznego (wz\u00f3r)\u00a0lub prostego dedukcyjnego sposobu uporania si\u0119 z tym zadaniem. Trzeba pr\u00f3bowa\u0107.<\/p>\n

Na wst\u0119pie warto zauwa\u017cy\u0107, \u017ce dowoln\u0105 par\u0119 liczb mo\u017cna uzupe\u0142ni\u0107 tylko jedn\u0105 tak\u0105 liczb\u0105, by warunek klienta by\u0142 spe\u0142niony. Na przyk\u0142ad, par\u0119 020 i 210 dope\u0142nia do „kompletu” tylko 100\u00a0– r\u00f3\u017cne cyfry s\u0105 na pierwszych pozycjach, r\u00f3\u017cne na drugich, takie same na trzecich.
\nZacznijmy od wybrania ze s\u0142upka A pary liczb, a z pozosta\u0142ych usu\u0144my jedn\u0105 liczb\u0119\u00a0– t\u0119, kt\u00f3ra tworzy z wybranymi wspomniany „komplet”. Nast\u0119pnie dobieramy trzeci\u0105 liczb\u0119, czyli w\u015br\u00f3d wybranych pojawiaj\u0105 si\u0119 dwie nowe pary, a wi\u0119c z pozosta\u0142ych usuwamy dwie liczby. Potem dobieramy czwart\u0105 liczb\u0119, zatem w\u015br\u00f3d wybranych pojawiaj\u0105 si\u0119 trzy nowe pary, wi\u0119c z pozosta\u0142ych musimy usun\u0105\u0107 trzy liczby itd. W trakcie tego procesu b\u0119dzie si\u0119 czasem zdarza\u0107 tak, \u017ce niekt\u00f3re pary do usuni\u0119cia na danym etapie oka\u017c\u0105 si\u0119 usuni\u0119te wcze\u015bniej.
\nGdy zaczniemy od g\u00f3ry s\u0142upka A, czyli w pierwszej parze b\u0119dzie 000 i 001, a na pocz\u0105tku ka\u017cdego etapu b\u0119dziemy dobiera\u0107, czyli „zazielenia\u0107” zawsze pierwsz\u0105 woln\u0105 liczb\u0119, to na ko\u0144cu pozostanie OSIEM wybranych liczb (zielone w s\u0142upku B).
\nPo rozpocz\u0119ciu od do\u0142u i dobieraniu zawsze pierwszej wolnej liczby od ko\u0144ca\u00a0– efekt b\u0119dzie taki, jak w s\u0142upku C, czyli symetryczny wzgl\u0119dem B.
\nZaczynaj\u0105c od przypadkowej pary (np. 000 i 012), ale dobieraj\u0105c zawsze kolejn\u0105 woln\u0105, czyli jak w s\u0142upku B, tak\u017ce zako\u0144czymy \u00d3SEMK\u0104 (s\u0142upek D).
\nW przypadkach B, C i D dowolna dziewi\u0105ta liczba dobrana spo\u015br\u00f3d usuni\u0119tych (czerwonych) uzupe\u0142ni jak\u0105\u015b zielon\u0105 par\u0119 do tr\u00f3jki spe\u0142niaj\u0105cej \u017cyczenie klienta wypo\u017cyczalni. Czy\u017cby zatem wypo\u017cyczalnia dysponowa\u0142a najwy\u017cej 9 autami, w tym jednym niesprawnym?<\/p>\n

Zr\u00f3bmy drobn\u0105 zmian\u0119. Gdy stosuj\u0105c metod\u0119, kt\u00f3rej efektem jest s\u0142upek D, zako\u0144czymy sz\u00f3sty etap dobierania i usuwania liczb, wolne pozostan\u0105 4 liczby (s\u0142upek E). Wybierzmy teraz nie kolejn\u0105 (111), tylko 121. Je\u015bli teraz usuniemy, czyli zaczerwienimy zb\u0119dne pary, to oka\u017ce si\u0119, \u017ce zielonych pozostanie… DZIEWI\u0118\u0106 (s\u0142upek F). Ot, niespodzianka. Sk\u0105d si\u0119 wzi\u0119\u0142o przedtem nie ujawniaj\u0105ce si\u0119 dziewi\u0105te auto\u00a0– to dopiero zagadka. A czy nie uda\u0142oby si\u0119 przeskoczy\u0107 tak\u017ce dziewi\u0119ciu? Niestety, nie. Korzystaj\u0105c z komputera mo\u017cna udowodni\u0107, \u017ce niezale\u017cnie od kt\u00f3rej pary zaczniemy i w jakiej kolejno\u015bci b\u0119dziemy dobiera\u0107 dalsze liczby, zawsze dotrzemy najwy\u017cej do DZIEWI\u0118CIU zielonych liczb-samochod\u00f3w, a zatem wszystkich aut w wypo\u017cyczalni by\u0142o DZIESI\u0118\u0106. Komputerowy dow\u00f3d, polegaj\u0105cy na sprawdzeniu wszystkich mo\u017cliwo\u015bci, jest \u017cmudny i nieelegancki. Niestety, prostego eleganckiego dowodu nie znam, a nieprosty jest tak skomplikowany, \u017ce nie odwa\u017c\u0119 si\u0119 go tutaj przytoczy\u0107.<\/p>\n

Wyobra\u017amy sobie teraz, \u017ce zadanie z autami uzupe\u0142niamy o kolejne cechy, czyli poza mark\u0105, kolorem i typem nadwozia pojawi si\u0119 kolor tapicerki, rodzaj opon, typ hamulc\u00f3w itd. Ka\u017cdej z nowych cech tak\u017ce przypiszemy trzy warto\u015bci, dajmy na to oponom Bridgestone\u00a0– 0, Goodyear\u00a0– 1, Michelin\u00a0– 2. Przy pi\u0119ciu cechach samochodom b\u0119d\u0105 odpowiada\u0107 liczby pi\u0119ciocyfrowe, np. 10403<\/strike>\u00a010202. Analogicznie zmieni si\u0119 \u017cyczenie klienta: w trzech wybranych samochodach wszystkie warto\u015bci ka\u017cdej z pi\u0119ciu cech powinny by\u0107 r\u00f3\u017cne lub jednakowe. Ko\u0144cowe pytanie pozostaje bez zmian: iloma co najwy\u017cej r\u00f3\u017cnymi autami dysponuje wypo\u017cyczalnia, je\u015bli przy jednym niesprawnym takie \u017cyczenie NIE mo\u017ce by\u0107 spe\u0142nione?<\/p>\n

Okazuje si\u0119, i\u017c stopie\u0144 trudno\u015bci zadania ro\u015bnie tak szybko, \u017ce wsp\u00f3\u0142czesne komputery ju\u017c dla sze\u015bciu cech w rozs\u0105dnym czasie\u00a0z zadaniem sobie nie radz\u0105. Dla pi\u0119ciu cech ustalono i udowodniono dopiero w roku 2002, \u017ce rozwi\u0105zaniem jest 45 (46 po dodaniu naprawionego samochodu), a w dowodzie pojawiaj\u0105 si\u0119 „straszne” poj\u0119cia, np. transformacja Fouriera…<\/p>\n

Dalej ju\u017c nie b\u0119d\u0119 Pa\u0144stwa straszy\u0142. Obawiam si\u0119, \u017ce i tak s\u0142upkami wym\u0119czy\u0142em tych, kt\u00f3rzy przebrn\u0119li przez ten wpis.
\nNagroda za rozwi\u0105zanie zadania o wypo\u017cyczalni Jap Co. przypad\u0142a w wyniku losowania szachowi<\/strong>. Uwzgl\u0119dni\u0142em uwag\u0119 zawart\u0105 w komentarzu Enzo<\/strong>, czyli 9 tak\u017ce uznawa\u0142em za poprawn\u0105 odpowied\u017a, je\u015bli oznacza\u0142a liczb\u0119 aut bez jednego znajduj\u0105cego si\u0119 w naprawie.
\nLaureata prosz\u0119 o kontakt pod adresem m.penszko@polityka.com.pl<\/a> w celu ustalenia sposobu przekazania nagrody ufundowanej przez\u00a0hurtowni\u0119 gier\u00a0Rost. Jest ni\u0105, jak s\u0142usznie zauwa\u017cyli Robert_C<\/strong> i najata<\/strong>, gra SET! Jej strona matematyczna jest bli\u017aniaczo podobna do struktury cech i warto\u015bci w zadaniu o autach. Nieco dok\u0142adniej o tej grze\u00a0– w nast\u0119pnym wpisie.<\/p>\n","protected":false},"excerpt":{"rendered":"

Min\u0119\u0142y \u015bwi\u0119ta, pora zaj\u0105\u0107 si\u0119 japo\u0144skimi samochodami z zadania o wypo\u017cyczalni Jap Co. Ka\u017cde auto mo\u017cna okre\u015bli\u0107 trzema cyframi, z kt\u00f3rych ka\u017cda odpowiada innej z trzech cech (marka, kolor, typ nadwozia) i mo\u017ce przybiera\u0107 trzy warto\u015bci (0,1,2), oznaczaj\u0105ce konkretne przyk\u0142ady w ramach danej cechy (jedn\u0105 z trzech marek, jeden z trzech kolor\u00f3w lub jeden z […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/184"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=184"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/184\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=184"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=184"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=184"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}