Zobaczmy wi\u0119c, w jaki spos\u00f3b powstaj\u0105 karty do tych gier i sk\u0105d si\u0119 wzi\u0105\u0142 tak ogromny czas ich tworzenia. Oczywi\u015bcie nie chodzi mi o fizyczne powstawanie kart w drukarni, tylko o algorytm tworzenia ich matematycznej struktury.<\/p>\n
Zacznijmy od najprostszego, wr\u0119cz trywialnego przypadku n=2. Oznaczaj\u0105c symbole na kartach kolejnymi literami alfabetu, mo\u017cemy przedstawi\u0107 jedyny mo\u017cliwy uk\u0142ad w postaci: AB, AC i BC. Wszystkie trzy warunki s\u0105 jak wida\u0107 spe\u0142nione. \u0141atwo zauwa\u017cy\u0107, \u017ce nie mo\u017cna doda\u0107 ani kolejnego czwartego symbolu, ani kolejnej karty.<\/p>\n
Rozpatrzmy teraz przypadek n=3, czyli trzy symbole na karcie. Pierwsza karta b\u0119dzie mia\u0142a np. posta\u0107 ABC, a druga ADE. Je\u017celi na trzeciej karcie ma by\u0107 symbol B, to nie mo\u017ce by\u0107 na niej ani A, ani C i mo\u017ce by\u0107 tylko jeden symbol z pary DE. \u017beby na tej karcie by\u0142y tak\u017ce trzy symbole, musimy wprowadzi\u0107 sz\u00f3sty symbol F. Trzecia karta b\u0119dzie mia\u0142a zatem posta\u0107 BDF, a czwarta CEF. Otrzymali\u015bmy w rezultacie nast\u0119puj\u0105cy uk\u0142ad czterech kart z sze\u015bcioma symbolami: ABC, ADE, BDF i CEF. Du\u017co \u0142adniej wygl\u0105da to na obrazku, pochodz\u0105cym z artyku\u0142u “Dobble et la \u00a0g\u00e9om\u00e9trie finie”<\/a>, kt\u00f3rego autorem jest francuski matematyk Maksym Bourrigan.<\/p>\n Cztery karty<\/p><\/div>\n Zamiast liter, wyst\u0119puj\u0105 tu kolorowe symbole, a ka\u017cdej karcie odpowiada k\u00f3\u0142ko z trzema symbolami. Kolorowymi paskami po\u0142\u0105czone zosta\u0142y karty, zawieraj\u0105ce symbole w kolorze pask\u00f3w.<\/p>\n Dla n=3, czyli trzech symboli na karcie, mamy 6 r\u00f3\u017cnych symboli i 4 karty. Dla dowolnego n<\/em> wz\u00f3r na liczb\u0119 r\u00f3\u017cnych symboli b\u0119dzie mia\u0142 posta\u0107 n(n+1)\/2, a liczba kart b\u0119dzie opisana wzorem k=n+1. Dla 4 symboli na karcie b\u0119dzie zatem 10 r\u00f3\u017cnych symboli i 5 kart, dla 5 symboli \u2013\u00a015 r\u00f3\u017cnych symboli i 6 kart, a dla n=8 (tak, jak w grze Dobble) \u2013 36 symboli i 9 kart. Talia kart do gry Dobble z\u0142o\u017cona z 9 kart? Troch\u0119 ma\u0142o. Przecie\u017c powinno by\u0107 ich ponad 50. Sk\u0105d ta r\u00f3\u017cnica? Wszystko przez to, \u017ce drugi postulat (ka\u017cdy symbol wyst\u0119puje na co najmniej dw\u00f3ch kartach) zosta\u0142 zrealizowany w granicznej postaci tzn. ka\u017cdy symbol wyst\u0105pi\u0142 na dok\u0142adnie dw\u00f3ch kartach.<\/p>\n Przyjrzyjmy si\u0119 dok\u0142adnie obrazkowi powy\u017cej. Mo\u017cna zauwa\u017cy\u0107, \u017ce na \u017cadnej karcie nie wyst\u0119puje jednocze\u015bnie niebieski i zielony symbol, czarny symbol nie wyst\u0119puje razem z \u017c\u00f3\u0142tym, a czerwony z bia\u0142ym. Podobna sytuacja jest w zapisie literowym \u2013 na \u017cadnej karcie nie ma jednocze\u015bnie A i F, B i E ani C i D. Do\u0142\u0105czaj\u0105c si\u00f3dmy symbol G, mo\u017cemy utworzy\u0107 trzy nowe karty: AFG, BEG i CDG. Wraz z czterema poprzednimi tworz\u0105 one idealnie symetryczny uk\u0142ad, w kt\u00f3rym ka\u017cda para symboli wyst\u0119puje na jakiej\u015b karcie. Graficznie (za tym samym \u017ar\u00f3d\u0142em co poprzednio) mo\u017cna to przedstawi\u0107 tak:<\/p>\n <\/p>\n Siedem kart<\/p><\/div>\n <\/p>\n Jak wida\u0107, mamy teraz 7 kart i 7 r\u00f3\u017cnych symboli (doszed\u0142 fioletowy znak \u221e), a ka\u017cdy symbol wyst\u0119puje na trzech kartach, po\u0142\u0105czonych kolorowym paskiem. Jako ciekawostk\u0119 dodam, \u017ce matematycy nazywaj\u0105 taki obiekt p\u0142aszczyzn\u0105 Fano<\/a>.<\/p>\n Po dodaniu warunku \u201eka\u017cda para symboli wyst\u0119puje raz na jakiej\u015b karcie\u201d, kt\u00f3ry jak mo\u017cna zaobserwowa\u0107, zosta\u0142 zrealizowany na drugim rysunku, wz\u00f3r na liczb\u0119 r\u00f3\u017cnych symboli oraz na liczb\u0119 kart (bo te dwie wielko\u015bci s\u0105 teraz r\u00f3wne) ma posta\u0107 k=n^2-n+1. Dla n=8 daje to 57 r\u00f3\u017cnych symboli i 57 kart. W talii Dobble kart jest 55, wi\u0119c jak kto\u015b ma ochot\u0119, mo\u017ce sprawdzi\u0107, jakich dw\u00f3ch zestaw\u00f3w symboli brakuje.<\/p>\n Wci\u0105\u017c jednak nie wida\u0107 jakich\u015b przera\u017caj\u0105co wielkich liczb, a zale\u017cno\u015b\u0107 kwadratowa we wzorze na liczb\u0119 kart, to wr\u0119cz marzenie tw\u00f3rc\u00f3w algorytm\u00f3w. Niestety, tak dobrze to wygl\u0105da tylko dlatego, \u017ce z g\u00f3ry za\u0142o\u017cyli\u015bmy, jak maj\u0105 wygl\u0105da\u0107 karty. Dla ma\u0142ej liczby symboli na kartach (w naszym przypadku trzech) da si\u0119 to zrobi\u0107 bez trudu \u201er\u0119cznie\u201d. Ale przy wi\u0119kszej liczbie ju\u017c to takie proste nie jest.<\/p>\n Pozosta\u0144my jeszcze przez chwil\u0119 przy trzech symbolach na kartach. Wiemy ju\u017c, \u017ce wszystkich symboli jest wtedy 7. Ile r\u00f3\u017cnych kart mo\u017cna stworzy\u0107 z tych siedmiu symboli, je\u017celi na ka\u017cdej karcie maj\u0105 by\u0107 trzy r\u00f3\u017cne? Jest to kombinacja bez powt\u00f3rze\u0144 trzech element\u00f3w ze zbioru siedmiu i takich kombinacji mo\u017ce by\u0107 35, czyli mamy 35 r\u00f3\u017cnych kart. Wiemy, \u017ce kart ma by\u0107 w zestawie 7. Na ile sposob\u00f3w mo\u017cna z talii 35 kart wybra\u0107 7? Okazuje si\u0119, \u017ce jest to 6.724.520 czyli ju\u017c liczba ca\u0142kiem spora. A tylko 30 sposob\u00f3w prowadzi do w\u0142a\u015bciwego rozwi\u0105zania, czyli takiego, w kt\u00f3rym ka\u017cda para kart ma dok\u0142adnie jeden wsp\u00f3lny symbol.<\/p>\n Jak to wygl\u0105da dla kolejnych liczb symboli na kartach, a\u017c do 8, czyli tylu, ile jest w grze Dobble, pokazuje poni\u017csza tabelka:<\/p>\n <\/p>\n <\/p>\n Uwaga: Nie wiem, czy da si\u0119 skonstruowa\u0107 uk\u0142ad 43 kart z 7 r\u00f3\u017cnymi symbolami na ka\u017cdej. Dla innych liczb symboli z tabelki jest to na pewno mo\u017cliwe. Og\u00f3lnie da si\u0119 to zrobi\u0107 dla ka\u017cdej takiej liczby n<\/em>, dla kt\u00f3rej n-1 jest liczb\u0105 pierwsz\u0105 i dla niekt\u00f3rych innych, np. dla 5.<\/p>\n A jak to wygl\u0105da dla gry Znaj Znak, w kt\u00f3rej na ka\u017cdej karcie jest 12 symboli? Okazuje si\u0119, \u017ce musimy wtedy u\u017cy\u0107 133 r\u00f3\u017cnych symboli. Z tych 133 symboli mo\u017cna utworzy\u0107 przesz\u0142o 3,8×10^16 r\u00f3\u017cnych kart (dok\u0142adnie 38.359.579.905.883.600). Liczby sposob\u00f3w, na jakie spo\u015br\u00f3d tych kart mo\u017cna wybra\u0107 133 nie b\u0119d\u0119 dok\u0142adnie podawa\u0142, bo liczy ona blisko 2000 cyfr. Nic wi\u0119c dziwnego, \u017ce pr\u00f3ba rozwi\u0105zania tego zagadnienia metod\u0105 \u201ebrute force\u201d musia\u0142aby trwa\u0107 nie tyle latami, co wr\u0119cz milionami lat.<\/p>\n Na szcz\u0119\u015bcie istnieje algorytm, kt\u00f3ry pozwala zautomatyzowa\u0107 proces tworzenia kart, dzia\u0142aj\u0105cy dla ka\u017cdej liczby symboli na karcie, kt\u00f3ra jest wi\u0119ksza o 1 od liczby pierwszej.\u00a0 Zar\u00f3wno Dobble (8 symboli), jak i Znaj znak (12 symboli) warunek ten spe\u0142niaj\u0105, a algorytm jest na tyle szybki, \u017ce stworzenie zestawu kart do gry Znaj znak trwa\u0142o poni\u017cej jednej sekundy.<\/p>\n","protected":false},"excerpt":{"rendered":" Metody matematyczne mog\u0105 by\u0107 wykorzystywane nie tylko do analizowania przebiegu rozgrywki, ale tak\u017ce do stworzenia odpowiedniego zestawu rekwizyt\u00f3w.\u00a0 Czasami jednak s\u0105 z tym pewne problemy, bo zagadnienia kombinatoryczne maj\u0105 tendencje do niesamowicie szybkiego wzrostu. Jakie to mo\u017ce wywo\u0142a\u0107 efekty, pokazuje wypowied\u017a, kt\u00f3ra pojawi\u0142a si\u0119 w kwietniu 2012 na forum grupy Monsoon, podczas prac nad gr\u0105 …<\/p>\n","protected":false},"author":101,"featured_media":57677,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"cybocfi_hide_featured_image":"","footnotes":""},"categories":[],"tags":[],"post_folder":[],"class_list":["post-57652","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry"],"_links":{"self":[{"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/posts\/57652","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/users\/101"}],"replies":[{"embeddable":true,"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/comments?post=57652"}],"version-history":[{"count":0,"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/posts\/57652\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/media\/57677"}],"wp:attachment":[{"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/media?parent=57652"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/categories?post=57652"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/tags?post=57652"},{"taxonomy":"post_folder","embeddable":true,"href":"https:\/\/wp4wpuw.pedagog.uw.edu.pl\/test\/wp-json\/wp\/v2\/post_folder?post=57652"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"Cztery](\"\/wp-content\/uploads\/2015\/06\/minidobble2-5fc98-200x187.png\")
<\/a>![\"Siedem](\"\/wp-content\/uploads\/2015\/06\/minidobble_p2f2-9a128-200x198.png\")
<\/a>\n\n
\n Liczba symboli na karcie<\/td>\n Liczba r\u00f3\u017cnych symboli<\/td>\n Liczba mo\u017cliwych kart<\/td>\n Liczba sposob\u00f3w wyboru kart<\/td>\n<\/tr>\n \n 2<\/td>\n 3<\/td>\n 3<\/td>\n 1<\/td>\n<\/tr>\n \n 3<\/td>\n 7<\/td>\n 35<\/td>\n 6.724.520<\/td>\n<\/tr>\n \n 4<\/td>\n 13<\/td>\n 715<\/td>\n 1,8 x 10^27<\/td>\n<\/tr>\n \n 5<\/td>\n 21<\/td>\n 20.349<\/td>\n 6 x 10^70<\/td>\n<\/tr>\n \n 6<\/td>\n 31<\/td>\n 736.281<\/td>\n 9 x 10^147<\/td>\n<\/tr>\n \n 7<\/td>\n 43<\/td>\n 32.224.114<\/td>\n 1 x 10^270<\/td>\n<\/tr>\n \n 8<\/td>\n 57<\/td>\n 1.652.411.475<\/td>\n 7 x 10^448<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n