Pentru a putea publica, trebuie să vă înregistraţi.
Contul se valideaza de admin in cel mult 24 de ore.
Pune o întrebare

3.6k intrebari

6.8k raspunsuri

15.5k comentarii

2.5k utilizatori

3 plusuri 0 minusuri
224 vizualizari

Dintr-un cub 5x5x5 eliminăm câteva cubulețe astfel încât să obținem un tunel prin el, un traseu, cu o singură intrare și o singură ieșire. Am obținut astfel un cub găunos: (aici)

De asemenea traseul este astfel conceput încât nu există posibilitatea unei bucle (fiecare cubuleț gol este învecinat cu  cel mult două cubulețe goale).

Se observă că traseul din imagine înglobează 13 cubulețe goale.

Acum, trecând la un cub 8x8x8, am realizat un traseu prin el, respectând aceleași reguli ca mai sus. Iată ce a ieșit (tot un cub găunos): (aici) și (aici)

Se observă că de data aceasta traseul include 38 de cubulețe. Deci e un cub ceva mai găunos decât cel dinainte. În afară de aceasta, dacă am colorat unele dintre cubulețe cu culori diferite, a ieșit o siglă interesantă!

Problema care se pune are două întrebări:

1.  Cum arată cubul cel mai găunos în cazul 5x5x5, și cum demonstrăm aceasta, că are numărul maxim de cubulețe goale?

2.  Aceeași întrebare pentru cubul 8x8x8.

În cazul în care nu există un răspuns sigur la întrebarea a doua (mie nu mi-a venit nici o idee salvatoare), aș putea lansa o altă provocare: cine găsește cubul, 8x8x8, cel mai găunos?

În situația în care se rezolvă chestiunea pe computer (mie mi se pare o soluție valabilă), vă rog să o postați totuși cu întârziere pentru a da posibilitate și celor care gândesc „cu capul lor” să își încerce șansa.

Novice (297 puncte) in categoria Diverse
0 0

   Am omis să precizez, pentru provocarea lansată, numărul de goluri în cub de la care se face plecarea. Eu am reușit să identific un traseu care cuprinde 82 cubulețe goale. Deci propun plecarea de la această cifră. Să vedem cine dă mai mult!

   Pentru simplificarea comunicării am imaginat o modalitate, zic eu simplă, de figurare în plan a traseului imaginat, în spațiu, prin cub.

   Ideea e de a figura fiecare cubuleț dintr-o coloană printr-o cifră 0 sau 1 după cum este gol sau plin. Cifrele corespondente cubulețelor se scriu în pătratul ce reprezintă baza coloanei respective, pe diagonala acestui pătrat.

   Iată un exemplu grafic sugestiv pentru o formă geometrică simplă: (aici)

Culorile sunt doar pentru a spori sugestivitatea imaginii. Pe hârtie, în cazul reprezentării unui traseu, se poate folosi o singură culoare. Poziția unei cifre (într-un anumit pătrat, și locul în diagonală) și valoarea ei (1 sau 0) sunt suficiente pentru a definii consistența (plin sau gol) unui cubuleț.

Iată exemplificarea în cazul cubului 5x5x5, traseul cu 13 cubulețe goale: (aici)

Sau în cazul cubului 8x8x8, traseul cu 38 cubulețe goale: (aici)

Desigur, cubulețele se pot defini și prin coordonatele lor. Dar reprezentarea aceasta, propusă de mine, permite vizualizarea rapidă, în plan, a situației în care un cubuleț este învecinat (adică are câte o față comună) cu mai mult de două cubulețe goale și dă posibilitatea evitării acestor situații. Și asta fără a avea o viziune grozavă în spațiu.

1 0

Plusez la 90 pentru cubul 8x8x8. Fețele exterioare ale cubului pot să dispară din desen, ele fiind toate intacte cu excepția punctelor de intrare și ieșire. Obiectul de studiu ramâne cubul interior de 6x6x6. Cu roșu am marcat cubulețele goale. Se intră într-un strat, se înroșesc un număr de cubulețe respectând regula dată și se trece la nivelul superior fără a mai reveni ulterior la stratul părăsit. Din acest motiv nu sunt necesare săgeți de orientare. Coloana din stânga reprezintă planurile 1, 2, 3  (începând de jos), iar cea din dreapta planurile 3, 4, 5, 6.  Planul 3 l-am repetat pentru a verifica mai ușor validitatea traseului roșu în planul 4.

1 0

Traseu corect! Frumoasă cifră: 90. Felicitări.

Iată însă că de la comentariul anterior, parcă simțind că cineva „vine tare din urmă”, m-am mai jucat cu 8x8x8 și mă văd nevoit să plusez și eu puțin: 93. Un traseu ceva mai încâlcit, cu suișuri și coborâșuri, dar care, zic eu, respectă condițiile impuse.

Am postat „imaginea” traseului în două variante. Una în stilul prezentat de mine în comentariul anterior, iar cealaltă în stilul prezentat de dvs. :

(aici)

  (aici)

Aș insista și pe prima întrebare, cea în legătură cu cubul 5x5x5.

0 0


Am mai câștigat 5 cubulețe menținând aceeași strategie. Acum totalul este de 95 > 93 > 90 > 83.
Cred ca știu rezultatul pentru cubul 3x3x3 dar nu pot să-l demonstrez. Poate soluția este prea simpla și eu m-am complicat sau poate am mintea încețoșată, habar n-am.

0 0

    Mă așteptam la așa ceva! Pentru că așa mi s-a întâmplat și mie cu saltul de la 82 la 93. Chiar mi-a venit ideea, la un moment dat, să încerc o optimizare a traseului prezentat de dvs. Dar m-am gândit că nu-i frumos să iei jucăria altuia și să te dai mare cu ea. Și, iată, bine am făcut.

    Acum să așteptăm, poate dă cineva mai mult.

    În ce privește prima întrebare, și eu am intuit întâi maximul și abia apoi am reușit o demonstrație. De fapt, în sens matematic, e o demonstrație doar în cazul în care metoda este acceptată ca fiind valabilă. E vorba de o trecere prin toate posibilitățile posibile și reținerea la sfârșit a variantei maxime (ca la întrebarea: care e traseul cel mai scurt prin labirint?). E o metodă, cum se spune, pompierească, dar cu răbdare se ajunge la rezultat.

    Am ajuns astfel la concluzia că 18 este răspunsul corect.

    Bineînțeles că lucrurile s-au simplificat considerabil având în vedere simplitatea și simetria, destul de generoasă, a unui cub 3x3x3, în care se concentrează toate sforțările.

    Totuși mi-e aproape imposibil să o prezint aici având în vedere că are zeci de ramificații, pornind doar de la cele trei intrări posibile în cub.

    Dacă aveți în minte același număr, aștept o prezentare grafică a traseului (dacă nu cer prea mult).

1 0

Am găsit două variante cu 18 cubulețe.

Lăsând deoparte punctele de intrare și de ieșire sunt 16 cubulețe împărțite la 3 planuri. Un strat poate avea maxim 7 cubulețe care respectă condiția vecinătății în plan, maxim care se obține prin traversarea nivelului o singură dată, fără reveniri la el. Presupunând că ar exista un traseu de 17 cubulețe, acestea ar trebui distribuite 7 - 3 - 7 sau 6 - 6 - 5, nu neapărat în această ordine. Se arată rapid că nu pot exista  două straturi de 7 și unul de 3, un pic mai greu se arată că nu pot fi două straturi consecutive de 6 și mai rămâne cazul 6 - 5 - 6, și în care căsuțele roșii din oricare plan nu formează un traseu continuu, adică exista intrări în el din celelalte planuri. Aici m-am poticnit și am început să număr cubulețele din 8x8x8. Nu mai încerc să găsesc un traseu mai lung, dar ca să-mi satisfac curiozitatea e cazul să apelez la artileria grea (programare).

0 0

    De acord cu artileria grea. Pentru că acum sunt și eu în ceață totală. Prin metoda prezentată în comentariul anterior am identificat doar un singur traseu de 18 cubulețe (cel din stânga). Deci mi-a scăpat cel din dreapta, probabil că am supraevaluat simetria figurii și am abandonat variante valabile, nu știu exact. Cert e că la fel de bine mi-ar fi putut scăpa și o eventuală variantă cu 19 (sau mai mult).

    Poate mai vine cineva cu vreo idee salvatoare. Altfel, programarea e ultima șansă.

    Nu mă pot abține, dacă tot am făcut-o, să nu postez imaginea traseului din stânga (în varianta reprezentării în plan).

0 0
Scuze dacă mai este cineva care caută o soluție mai bună. Nu există un traseu de 19 cubulețe (...sau mai multe). Programul încropit, bazat pe un algoritm backtracking, a stabilit că cel mai lung traseu este cel de 18 cubulețe găsind 12 soluții care de fapt sunt simetrii ale celor două variante arătate un pic mai sus ( ele se obțin plecând din două puncte de intrare nu și din cel din mijlocul unei fețe). Pentru 5x5x5 a fost nevoie de 1 minut, pentru 6x6x6 de cateva minute. De la 7x7x7 gluma se ingroașă, după câteva ore nu dădea niciun semn de oboseală. Probabil pentru 8x8x8 e nevoie de un supercomputer. Oricum, după ce l-am lăsat să ruleze ceva timp, tot am găsit soluții un pic mai bune decât cea găsită manual. Programul este mare consumator de timp, backtrackingul nu este remarcabil prin rapiditate dar totusi este mai iute decât o abordare tip brute force și se potrivește ca o mănușă la o astfel de problemă.
0 0

Trebuie să recunosc că de data asta nu mă așteptam să treceți la artileria grea (adică la programare). Deși cuvântul "curiozitate" ar fi trebuit să-mi dea de gândit. Oricum vă rămân dator cu o cinste, pentru că eu tocmai căutam pe cineva să realizeze programul, și în lipsa unui prieten cu pregătire în domeniu, cu siguranță că m-ar fi costat ceva.

Interesat aspectul creșterii complexității așa de rapide. Mă gândeam la o asemenea posibilitate, dar nu pentru cubul 8x8x8, și în nici un caz pentru 7x7x7.

Aș fi curios în două direcții (iată curiozitatea din nou în acțiune). Care este numărul maxim în cazul 6x6x6 (pentru că eu am găsit o cifră: 32, fără însă a avea pretenția unui maxim). Și de asemenea cu cât a îmbunătățit recordul în cazul 8x8x8 (eventual dacă e posibil și imaginea traseului).

1 0

O variantă de traseu maxim de dimensiune 38 pentru cubul 6x6x6:

Și una de 103 cubulețe pentru 8x8x8 ((cu siguranță nu este tunelul cel mai lung, dar foarte aproape de a fi):

Pentru cazul în care am greșit colorarea desenului dau și configurațiile celor 6 planuri orizontale obținute (începând cu cel de jos) si cum a construit programul traseul. Punctul de pornire în acest exemplu este cubulețul din stânga jos, iar X+ sau X- înseamnă urcarea sau coborârea pe axa X:

 1 0 1 0 1 1
 0 0 1 1 0 1
 0 0 0 0 1 0
 0 0 1 0 0 1
 1 0 1 0 0 1
 1 1 1 0 0 1
 1 0 1 0 1 0
 0 1 0 1 0 1
 1 1 0 0 1 0
 0 0 1 0 0 1
 1 1 0 1 1 0
 0 0 0 1 0 1
 1 0 1 0 1 0
 0 1 0 1 0 1
 1 0 0 0 1 0
 1 0 1 0 0 1
 0 1 0 0 1 0
 1 1 0 1 0 1
 1 0 1 0 1 0
 0 1 0 1 0 1
 0 1 0 1 1 0
 1 0 1 0 0 1
 1 0 1 0 1 0
 1 0 1 1 0 1
 1 0 1 0 1 0
 0 0 1 0 0 1
 0 1 1 0 0 0
 0 0 0 1 0 1
 0 0 0 1 1 0
 0 0 0 0 0 1
 1 0 0 1 1 0
 1 0 0 1 0 1
 1 0 0 1 0 1
 1 0 0 1 0 1
 1 0 0 0 0 0
 1 1 1 1 1 1

Calea urmată:
X+X+X+X+X+Y+Y+Y+Y+Y+Z+Z+Z+Z+Z+X-X-X-X-X-Y-Y-X+X+X+X+X+Y-Y-X-X-X-X-X-Y-Z-X+X+X+X+X+Z-Y+Y+Y+X-Y+Z+X-X-X-Z-Y+X+X+Z-Y-Y-X-X-X-Y+Y+Z-Z-Y-X+Z+X+Y+Z-X+Y-Y-X-Y-X-Z+Y-X+X+Y+X+Z+Y-Y-X-X-X-X-Y+Z+X+X+X+Y+Z+X-X-X-
Total =  101 + 2

Un traseu extrem de complicat!

0 0

Da, mulțumesc! Păcat că nu ați postat ca răspuns.

Traseele sunt corecte, le-am verificat personal (de parcă ar avea calculatorul nevoie de verificarea mea!). Oricum se poate trage deocamdată o concluzie: nu totdeauna soluția unei probleme e și cea mai simplă, cea mai elegantă (asta, cel puțin, după criteriile pe care le avem noi, ca ființe umane, despre eleganță).

Mă gândesc că poate acum, după ce am intrat pe tărâmul soluțiilor pe calculator (mai bine zis: în calculator), vor intra și alții în joc, dintre cei care se pricep la programare. Ca să parafrazez un dicton latin: „Sperare humanum est”. De asemenea dacă are cineva acces la un supercalculator aș fi dispus să pun la bătaie pentru soluția maximă la cubul 8x8x8 până la „jumătate de împărăție”!!

Te rugam sa te autentifici sau sa te inregistrezi pentru a raspunde la aceasta intrebare.

...