<strong>Rubik Küpünü qarışdırmaq nə qədər çətindir?</strong>

Zongzheng Zhou, Avstraliya Tədqiqat Şurası Riyaziyyat və Statistik Sərhədlər Mükəmməllik Mərkəzində (ACEMS) bir tədqiqatçıdır.

Peaker Guo, bu məqalədən faydalana biləcək hər hansı bir şirkət və ya təşkilat üçün işləmir, məsləhətləşmir, səhmlərə sahib deyil və ya maliyyələşdirmə almır və akademik randevusundan kənar heç bir əlaqəsini açıqlamamışdır.

Tərəfdaşlar

Monash Universiteti, Conversation AU-nun qurucu tərəfdaşı olaraq maliyyə təmin edir.

Conversation UK bu təşkilatlardan maliyyə alır

  • Elektron poçt
  • Twitter
  • Facebook
  • LinkedIn
  • WhatsApp
  • Elçi

Rubik's Cube 40 ildir dünyanın ən sevimli bulmacalarından biridir. Saysız kitablarda izah edildiyi kimi, bunun həlli üçün bir neçə fərqli üsullar hazırlanmışdır. Mütəxəssis “sürət kubları” bunu bir neçə saniyə ərzində həll edə bilər.

Bu cür heyrətləndirici çeviklik bacarıqlarına əlavə olaraq, Rubik Küpü ilə əlaqəli çox maraqlı riyazi suallar var. Küpün hərəkəti altı üzdən birini 90, 180 və ya 270 dərəcə döndürməkdən ibarətdir. Mükəmməl bir 43,252,003,274,489,856,000 vəziyyət, həll halına hərəkət ardıcıllığı tətbiq etməklə əldə edilə bilər.

Bu mürəkkəbliyə baxmayaraq, 2010-cu ildə göstərildi ki, Rubik Küpü ilkin vəziyyətindən asılı olmayaraq hər zaman 20 hərəkətdə və ya daha az həll edilə bilər. İnsanlar tərəfindən istifadə olunan bilinən bütün həll üsulları ümumiyyətlə bu optimal dəyərdən xeyli çox hərəkət istifadə etdiyi üçün bu rəqəmə "Tanrı sayı" deyilir.

Bəs əks suala nə var: həll edilmiş bir küpü qarışdırmaq üçün neçə hərəkət tələb olunur? İlk baxışdan bu, Allahın sayını hesablamaqdan daha asan bir sual kimi səslənir. Axı, bir küpü həll etməkdən fərqli olaraq, bir-birinə qarışmaq heç bir bacarıq tələb etmir.

Oxşar suallar kart qarışdırmaq üçün uğurla cavablandırıldı. Məşhur bir nümunə, riyaziyyatçılar Dave Bayer və Perci Diaconis tərəfindən 1990-cı ildə edilən "səs-küylü qarışıqlıq" araşdırmasıdır. Kartların göyərtəsi, sırası təsadüfi olarsa, mümkün olan hər sifarişin eyni görünmə ehtimalı olduğu halda “qarışıq” olaraq təyin olunur. Bayer və Diaconis, standart bir oyun kartını qarışdırmaq üçün yeddi səs-küylü qarışdırmanın lazım olduğunu və yetərli olduğunu göstərdi.

Keçən il riyaziyyatçılar, 15 sürüşmə çini və bir boşluqla doldurulmuş 4x4 kvadratdan ibarət olan 15 tapmacaya bənzər bir araşdırma yayımladılar.

Bir kubun pişmiş olması nə deməkdir?

Bir Rubik Küpünü qarışdırmağa çalışan tipik bir adam, üzərində dəfələrlə təsadüfi hərəkətlər edərdi. Yaranan təsadüfi vəziyyət ardıcıllığı riyaziyyatçıların Markov zənciri adlandırdıqları xüsusi bir haldır. Əsas xüsusiyyət, mövcud vəziyyəti nəzərə alaraq, növbəti vəziyyətin olma ehtimalı əvvəlki vəziyyətlərin heç birindən asılı olmamasıdır.

Markov zəncirləri nəzəriyyəsini küp dırmaşmasına tətbiq etdikdə, təsadüfi hərəkətlərin sayı artdıqca, mümkün vəziyyətlərdən hər hansı birində olma ehtimalının 1 / 43,252,003,274,489,856,000-ə yaxınlaşdığı ortaya çıxır. Riyaziyyatçılar buna "vahid ehtimal paylanması" deyirlər, çünki hər mümkün vəziyyət eyni ehtimalla baş verir.

Verilən istənilən təsadüfi hərəkətdən sonra kubun vəziyyəti təsadüfi olacaq, lakin ehtimal bölgüsü tam bərabər olmayacaq; bəzi ştatlar başqalarına nisbətən daha çox meydana gələcək.

D (t) t təsadüfi hərəkətlərdən sonra ehtimal paylanmasının vahid ehtimal paylanmasından nə qədər fərqləndiyini təsvir edək . Təsadüfi hərəkət sayı ( t ) artdıqca d (t) dəyəri azalacaq. Pişmiş kub d (t) kiçik olmasına cavab verir .

Markov zənciri Monte Carlo

Markov zəncirləri nəzəriyyəsində d (t) dəki bu azalmaya “qarışdırma” deyilir. Markov zəncirvari qarışdırma nəzəriyyəsi kart qarışdırmaq və tapmacalarla qarışdırmaqdan əlavə çox ciddi praktik tətbiqlərə də malikdir. Müasir elm və mühəndisliyin ən vacib hesablama vasitələrindən biri Monte Carlo metodudur. Bu üsul, adını aldığı məşhur kazino kimi, əsas etibarilə şansa əsaslanır. Əslində, çoxsaylı təsadüfi təxminlərdən istifadə edərək çətin riyazi problemləri həll etməyə çalışır.

Praktikada Markov zəncirləri bu təsadüfi vəziyyətləri istehsal etmək üçün tez-tez istifadə olunur. Bu Markov zənciri Monte Carlo metodlarının düzgünlüyünü anlamaq üçün əsas vəzifə t artdıqca d (t) -nin nə qədər tez azaldığını qiymətləndirməkdir .

Cib kubu

Standart 3x3x3 Rubik Küpü üçün çəkişmə problemini öyrənmək hal-hazırda maraqlı və həll olunmamış bir problemdir. Bununla birlikdə, diqqətimizi cib küpü adlanan daha kiçik bir 2x2x2 versiyasına yönəltsək, kifayət qədər idarə edilə bilər.

Bu kubda kənar və orta hissələr yoxdur və yalnız künc parçaları qalır. Cib kubunun yalnız 3.674.160 mümkün vəziyyəti var və Tanrı sayı yalnız 11-dir.

Aşağıdakı qrafikdə cib kubu üçün d (t) şəkli çəkirik. 11 hərəkətdən sonra d (t) 0.695-də hələ də çox böyükdür. 0,25-dən aşağı bir d (t) dəyəri verən t- nin ilk dəyəri ( Markov zəncir nəzəriyyəsində tez-tez “qarışma vaxtı” adlanır) 19. 25 hərəkətdən sonra d (t) 0.092; 50 hərəkətdən sonra 0,0012; və 100 hərəkətdən sonra 0.00000017 olur.

T hərəkətindən sonra cib kubunun paylanmasının üniformadan məsafəsi. Eric Zhou

Yaxşı bir cib kubunu tam dartmaq üçün neçə hərəkət istifadə etməlisən? Cavab d (t) olmasını nə qədər istəməyinizə bağlıdır . Ancaq, şübhəsiz ki, Allahın hərəkət sayının yetərli olmadığı. Minimum dərəcədə, 19 hərəkətdən az istifadə edilməməlidir. D (t) hesablamaq üçün kod daxil olmaqla daha ətraflı məlumat burada mövcuddur.

Əlbətdə, kubunuzu bir yerə yığdıqdan sonra təkrar həll etmək qalır.