Plurkvadrato

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
La 18 unuflankaj 5-kvadratoj, inkluzivante 6 spegulajn parojn
La 35 liberaj 6-kvadratoj, kolorigita laŭ ilia simetrio.
La 108 liberaj 7-kvadratoj.

En matematiko, plurkvadrato estas plurformo surbaze de kvadrato. Ĝi estas koneksa formo formita per la unio de unu aŭ pli multaj identaj kvadratoj en malsamaj situoj en la ebeno, prenitaj el la regula kvadrata kahelaro, tiel ke ĉiu kvadrato estas koneksa al ĉiu la alia kvadrato tra vico de komunigitaj lateroj (kio estas ke formoj koneksaj nur tra komunigitaj verticoj de kvadratoj estas ne permesitaj).

En iuj ĉirkaŭtekstoj, la difino de plurkvadrato estas malstreĉigita aŭ rafinita. Iam estas postulite ke plurkvadratoj estas simple koneksaj, iam ili povas havi truojn (regionoj kiu estas ne kahelitaj per la kvadratoj apartenantaj al la plurkvadrato, sed kiu estas nekonksaj al la cetera eksteraĵo de la plurkvadrato).

Rilatantaj al plurkvadratoj estas plurtrianguloj, formitaj el egallateraj trianguloj; plurseslateroj, formitaj el regulaj seslateroj kaj la aliaj plurformoj. Iam plurkvadratoj estas ĝeneraligitaj al tri aŭ pli multaj dimensioj kiel plurkuboj, kiuj estas kunigitaj kuboj.

Plurkvadratoj estas fonto de kombinaj problemoj, la plej baza estas numerado (kalkulado de kvanto) de plurkvadratoj de donita amplekso. La ĝenerala formulo ne estas trovita, tamen estas formuloj por specialaj klasoj de plurkvadratoj. Tamen, pritaksoj de la kvanto estas sciataj, kaj estas algoritmoj por kalkuli ilin.

Liberaj, unuflankaj kaj fiksitaj plurkvadratoj[redakti | redakti fonton]

Estas tri komunaj manieroj de difino de tio kiuj plurkvadratoj estas konsiderataj kiel malsamaj:

  • Liberaj plurkvadratoj estas malsamaj unu de la alia se ne estas rigida transformo (traduko, turnado, reflektoglita reflekto) inter ili. Ĉi tiu varianto respektivas al aĵoj faritaj el iu materialo, kiujn eblas meti ajne fizike sur tabulon.
  • Unuflankaj plurkvadratoj estas malsamaj unu de la alia se ne estas movo aŭ turnado inter ili. Ĉi tiu varianto respektivas al aĵoj faritaj el iu materialo kun nur unu vizaĝa surfaco, kiujn eblas meti ajne fizike sur tabulon, sed la vizaĝa flanko devas esti supre.
  • Fiksitaj plurkvadratoj estas malsamaj unu de la alia se ne estas movo inter ili.

Numerado de plurkvadratoj[redakti | redakti fonton]

Jen estas la kvantoj de plurkvadratoj kun n kvadratoj kun diversaj difinoj de la malsameco. La skribmaniero An estas por la kvanto de fiksitaj plurkvadratoj de n kvadratoj (eble kun truoj).

n nomo liberaj liberaj kun truoj liberaj sen truoj unuflankaj fiksitaj An
1 kvadrato 1 0 1 1 1
2 2-kvadrato (domeno) 1 0 1 1 2
3 3-kvadrato 2 0 2 2 6
4 4-kvadrato 5 0 5 7 19
5 5-kvadrato 12 0 12 18 63
6 6-kvadrato 35 0 35 60 216
7 7-kvadrato 108 1 107 196 760
8 8-kvadrato 369 6 363 704 2,725
9 9-kvadrato 1285 37 1248 2500 9910
10 10-kvadrato 4655 195 4460 9189 36446
11 11-kvadrato 17073 979 16094 33896 135268
12 12-kvadrato 63600 4663 58937 126759 505861

Kiel en 2004, Iwan Jensen kalkulis la fiksitajn plurkvadratojn supren ĝis n=56, A56 estas proksimume 6,915×1031. Liberaj plurkvadratoj estas kalulitaj supren ĝis n=28 de Tomás Oliveira e Silva.

Simetrioj de plurkvadratoj[redakti | redakti fonton]

La duedra grupo D4 estas la grupo de simetrioj (geometria simetria grupo) de kvadrato. Ĉi tiu grupo enhavas kvar turnadojn kaj kvar reflektojn. Ĝi estas generita per alternaj reflektoj ĉirkaŭ la x-akso kaj ĉirkaŭ la diagonalo. Unu libera plurkvadrato respektivas al maksimume 8 fiksitaj plurkvadratoj, kiuj estas ĝiaj bildoj sub la simetrioj de D4. Tamen, tiuj bildoj estas ne bezone malsamaj, ju pli multon da simetrio libera plurkvadrato havas, des malpli multaj malsamaj fiksitaj versioj estas. Pro ĉi tio, libera plurkvadrato kiu estas invarianta sub iuj ne-bagatelaj simetrioj de D4 povas respektivi al nur 4, 2 aŭ 1 fiksitaj plurkvadratoj. Tiel liberaj plurkvadratoj estas ekvivalentklasoj de fiksis plurkvadratoj sub la grupo D4.

Plurkvadratoj havas jenajn eblajn simetriojn:

Kvanto de malsamaj fiksitaj plurkvadratoj por libera plurkvadrato Simetrio Geometria simetria grupo La plej malgranda kvanto de kvadratoj bezonataj en plurkvadrato por la okazo
8 sen simetrio 4
4 spegula simetrio kun respekto al unu el la kradaj linioj 4
4 spegula simetrio kun respekto al unu el la diagonalaj linioj 3
4 2-obla turna simetrio C2 4
2 simetrio kun respekto al ambaŭ kradaj liniaj direktoj, kaj do ankaŭ 2-obla turna simetrio D2 2
2 simetrio kun respekto al ambaŭ diagonalaj direktoj, kaj de ĉi tie ankaŭ 2-obla turna simetrio D2 7
2 4-obla turna simetrio C4 8
1 ĉiu simetrio de la kvadrato D4 1

Jen estas la kvantoj de plurkvadratoj kun n kvadratoj, ordigitaj laŭ simetriaj grupoj:

n neniu spegula (90°) spegula (45°) C2 D2 (90°) D2 (45°) C4 D4
1 0 0 0 0 0 0 0 1
2 0 0 0 0 1 0 0 0
3 0 0 1 0 1 0 0 0
4 1 1 0 1 1 0 0 1
5 5 2 2 1 1 0 0 1
6 20 6 2 5 2 0 0 0
7 84 9 7 4 3 1 0 0
8 316 23 5 18 4 1 1 1
9 1196 38 26 19 4 0 0 2
10 4461 90 22 73 8 1 0 0
11 16750 147 91 73 10 2 0 0
12 62878 341 79 278 15 3 3 3

Algoritmoj por kalkulado de fiksitaj plurkvadratoj[redakti | redakti fonton]

Induktaj algoritmoj[redakti | redakti fonton]

Ĉiu plurkvadrato de ordo n+1 povas esti ricevita per aldono de kvadrato al plurkvadrato de ordo n. Ĉi tio donas algoritmojn por generado de plurkvadratoj indukte.

Plej simple, por donita listo de plurkvadratoj de ordo n, kvadratoj povas esti aldonataj apud ĉiu plurkvadrato en ĉiu ebla pozicio, kaj la rezultantaj plurkvadratoj de ordo n+1 estas aldonataj al la listo se ne estas la samo jam trovita. Ĉi tiu maniero povas esti uzata al numerigi liberajn aŭ fiksitajn plurkvadratojn.

Pli malnaiva maniero, priskribita de Redelmeier, estas uzata de multaj aŭtoroj kiel maniero de kalkulado de plurkvadratoj sen postulo ke ĉiuj plurkvadratoj de ordo n estas konservita por ke numerigi tiujn de ordo n+1. La maniero estas ankaŭ uzata kiel bazo por pruvo de superaj baroj pri kvantoj de plurkvadratoj (vidu sube). La baza ideo estas ke oni komencu kun sola kvadrato, kaj de tie, rikure adiciu kvadratojn. Dependante de la detaloj, ĝi povas kalkuli ĉiun n-kvadraton n fojojn, po unu startante de ĉiu el ĝiaj n kvadratoj, aŭ povas esti aranĝita kalkuli ĉiun nur unufoje.

La plej simpla realigo engaĝas aldonon de kvadrato po unu en fojo. Komencu kun komenca kvadrato, nombrigu la najbarajn kvadratojn, laŭhorloĝnadle de la supro, 1, 2, 3 kaj 4. Nun prenu nombron inter 1 kaj 4, kaj aldonu kvadraton je tiu situo. Nombrigu la nenombritaj najbarajn kvadratojn, startante de 5. Tiam, prenu nombron pli grandan ol la antaŭe prenita nombro, kaj aldonu tie kvadraton. Daŭru prenante nombron pli grandan ol la nombro kie antaŭ estis ĵus aldonita kvadrato, aldonu ankoraŭ unu kvadraton kaj numerigu la novajn najbarajn kvadratojn. Kiam n kvadratoj estas kreitaj, n-kvadrato estas kreita.

Ĉi tiu maniero certigas ke ĉiu fiksita plurkvadrato estas kalkulita akurate n fojojn, po unu por ĉiu startanta kvadrato. Ĝi povas esti optimumigita tiel ke ĝi kalkulu ĉiun plurkvadraton nur unufoje. Startante kun la komenca kvadrato, deklaru ĝin al esti la suba-maldekstra kvadrato de la plurkvadrato. Ne nombrigu kvadratojn kiuj estas en pli suba linio, aŭ maldekstre de la unua kvadrato en la sama linio. Ĉi tio estas la versio priskribita de Redelmeier.

Se necesas kalkuli liberajn plurkvadratojn anstataŭe, tiam oni povas kontroli simetriojn post kreo de ĉiu n-kvadrato. Tamen, estas pli rapide generi simetriajn plurkvadratojn aparte (per variado de ĉi tiu maniero) kaj tiel difini la kvanton de liberaj plurkvadratoj per lemo de Burnside.

Tradono-matrica maniero[redakti | redakti fonton]

La plej moderna algoritmo por kalkulado de fiksitaj plurkvadratoj estis esplorita de Iwan Jensen. Ĝi estas plibonigo de maniero de Andrew Conway, ĝi estas eksponente pli rapida ol la antaŭaj manieroj (tamen, ĝia rula tempo estas ankoraŭ eksponenta funkcio de n).

Ambaŭ versioj de Conway kaj Jensen de la tradono-matrica maniero engaĝas kalkuladon de la kvanto de plurkvadratoj kiuj havas certan larĝon. Sumigo de la kvantoj por ĉiuj larĝoj donas la tutecan kvanton de plurkvadratoj. La baza ideo de la maniero estas ke eblaj komencaj linioj estas konsiderataj, kaj tiam difini la minimuman kvanton de kvadratoj bezonataj por plenumi la plurkvadrato de la donita larĝo. Kombinite kun uzo de generantaj funkcioj, ĉi tiu tekniko estas povas kalkuli multajn plurkvadratojn en unu kalkulaĵo, tial kapable ruliĝi je multaj fojoj pli rapide ol manieroj kiuj devas generi ĉiun plurkvadraton aparte.

Kvankam ĉi tiu algoritmo havas relative bonan rulan tempon, la manko de ĝi estas ke ĝi uzas eksponente kreskantan kvanton de memoro (multaj gigabajtoj de memoro estas bezonata por n pli granda ol 50), estas multe pli peza por programado ol la aliaj manieroj, kaj ne povas aktuale esti uzata por kalkuli liberajn plurkvadratojn.

Asimptota kreskado de la kvantoj de plurkvadratoj[redakti | redakti fonton]

Fiksitaj plurkvadratoj[redakti | redakti fonton]

Teoriaj argumentoj kaj ciferecaj kalkuloj donas pritakson

 A_n \sim \frac{c\lambda^n}{n}

kie λ=4,0626 kaj c=0,3169. Tamen, ĉi tiu rezulto estas ne pruvita kaj la valoroj de λ kaj c estas nur pritaksoj.

La sciataj teoriaj rezultoj estas ne sufiĉe specifaj por ĉi tiu pritakso. Estas pruvite ke ekzistas limeso

 \lim_{n\rightarrow \infty} (A_n)^{1/n} = \lambda

En aliaj vortoj, An kreskas eksponente. La plej bona sciata suba baro por λ estas 3,980137. La plej bona sciata supera baro por λ, ne plibonigita ekde la 1970-aj jaroj, estas 4,65.

Por trovi suban baron, simpla sed efika maniero estas kunmeto de plurkvadratoj. Difinu la supro-dekstran kvadraton al esti la plej dekstra kvadrato en la plej supra linio de la plurkvadrato. Difinu la subo-maldekstran kvadraton simile. Tiam, la supro-dekstra kvadrato de ĉiu plurkvadrato de amplekso n povas ligiĝi al la subo-maldekstra kvadrato de ĉiu plurkvadrato de amplekso m por produkti unikan (n+m)-kvadraton. Ĉi tio montras ke AnAm≤An+m . Uzante ĉi tiun kondiĉon, eblas montri ke \lambda \geq (A_n)^{1/n} por ĉiu n. Plibonigo de ĉi tiu ideo kombinita kun datumoj por An donas la suban baron donitan pli supre.

La supera baro estas ricevita per ĝeneraligo de la indukta maniero de numerigo de plurkvadratoj. Anstataŭ aldono de unu kvadrato je fojo, oni aldonas akumuliĝon de kvadratoj je fojo. Ĉi tio estas ofte priskribata kiel aldono de branĉetoj. Per pruvo ke ĉiu n-kvadrato estas vico de branĉetoj, kaj per pruvo de limigoj pri la kombinaĵoj de eblaj branĉetoj, oni ricevas superan baron por la kvanto de n-kvadratoj. Ekzemple, en la algoritmo de konstruado donita pli supre, je ĉiu paŝo oni devas elekti pli grandan nombron, kaj maksimume tri novaj nombroj estas aldonataj (pro tio ke maksimume tri nenombritaj kvadratoj estas najbaraj al ĉiu nombrita kvadrato). Ĉi tio povas esti uzata por ricevi superan baron de 6,75. Uzante 2,8 milionojn branĉetojn, Klarner kaj Rivest ricevis superan baron 4,65.

Liberaj plurkvadratoj[redakti | redakti fonton]

Proksimumadoj por la kvanto de fiksitaj plurkvadratoj kaj liberaj plurkvadratoj estas simple rilatantaj un al la alia. Libera plurkvadrato sen simetrioj (turnado aŭ reflekto) respektivas al 8 malsamaj fiksitaj plurkvadratoj, kaj por granda n, plejparto de n-kvadratoj ne havas simetriojn. Pro tio, la kvanto de fiksitaj n-kvadratoj estas proksimume je 8 fojoj pli granda ol la kvanto de libera n-kvadratoj. Ankaŭ, ĉi tiu proksimumado iĝas eksponente pli precizan kiam n pligrandiĝas.

Specialaj klasoj de plurkvadratoj[redakti | redakti fonton]

Akurataj formuloj estas konataj por kalkulado de kvantoj de plurkvadratoj de specialaj klasoj, kiel la klaso de konveksaj plurkvadratoj kaj la klaso de direktitaj plurkvadratoj.

La difino de konveksa (fakte, kvazaŭ-konveksa) plurkvadrato estas malsama de la kutima difino de konvekseco. Plurkvadrato estas kolumno-konveksa se ĝia intersekco kun ĉiu vertikalo estas konveksa, do tio estas ke ĉiu kolumno ne havas truojn. Simile, plurkvadrato estas linio-konveksa se ĝia intersekco kun ĉiu horizontalo estas konveksa. Plurkvadrato estas dirita al esti konveksa se ĝi estas linie kaj kolumne konveksa.

Plurkvadrato estas direktita se ĝi enhavas kvadraton, nomatan kiel la radiko, tian ke ĉiu la alia kvadrato povas esti atingita per movadoj supren aŭ dekstren je unu kvadrato, sen laso de la plurkvadrato.

Direktitaj plurkvadratoj, kolumnaj (aŭ liniaj) konveksaj plurkvadratoj, kaj konveksaj plurkvadratoj estas efike kalkulataj per areo n, kaj ankaŭ per iuj la aliaj parametroj kiel perimetro, uzante generantajn funkciojn.

Kaheladoj[redakti | redakti fonton]

Kahelado de regionoj kun aroj de plurkvadratoj[redakti | redakti fonton]

Enigmoj kutime petas kaheli donitan regionon kun donita aro de plurkvadratoj. Tipa ekzemplo estas al kaheli 6×10 ortangulon kun la 12 5-kvadratoj; la 2339 solvaĵoj al ĉi tio estas trovitaj en 1960. Por kahelado en kiu multaj kopioj de la plurkvadratoj el la aro estas permesitaj, Golomb donas hierarkion de malsamaj regionoj kiujn la aro povas kaheli, kiel ortanguloj, bendoj kaj la tuta ebeno, kaj montras ke la demando de tio ĉu la ebeno povas esti kahelita per plurkvadratoj de donita aro estas nedecidebla, per surĵeto de aroj de kahelaro de Wang al aroj de plurkvadratoj.

Kahelado de regionoj kun kopioj de sola plurkvadrato[redakti | redakti fonton]

Alia klaso de problemoj demandas ĉu kopioj de donita plurkvadrato povas kaheli ortangulon, kaj kiajn ortangulajn ili povas kaheli. Ĉi tiuj problemoj estas multe studitaj por apartaj plurkvadratoj, kaj tabeloj de rezultoj por apartaj plurkvadratoj estas haveblaj. Klarner kaj Göbel montris ke por ĉiu plurkvadrato estas finia aro de primaj ortanguloj kiujn ĝi kahelas, tiel ke ĉiuj la aliaj ortanguloj kiuj ĝi kahelas povas esti kahelitaj per ĉi tiuj primaj ortanguloj.

Preter ortanguloj, Golomb donis hierarkion por solaj plurkvadratoj: plurkvadrato povas kaheli ortangulon, duonon de bendo, kurban bendon, pligrandigitan kopion de si, kvaronebenon, bendon, duonebenon, tutan ebenon, certajn kombinaĵojn, aŭ nenion el ĉi tio. Estas certaj implikacioj inter ĉi tiuj, ambaŭ evidentaj (ekzemple, se plurkvadrato kahelas duonebenon do ĝi kahelas la tutan ebenon) kaj malpli evidentaj (ekzemple, se plurkvadrato kahelas pligrandigitan kopion de si do ĝi kahelas kvaronebenon). Plurkvadratoj de ordoj supren ĝis 6 estas priskribitaj en ĉi tiu hierarkio (kun nesolvita tiam la statuso de unu 6-kvadrato, poste estis trovite ke ĝi kahelas ortangulon).

Kahelado de ebeno kun kopioj de sola plurkvadrato[redakti | redakti fonton]

Ĉiuj plurkvadratoj de ordoj 1 ... 6 kahelas ebenon, ĉiuj 7-kvadratoj krom 4 kahelas ebenon. David Bird trovis ke ĉiuj 8-kvadratoj krom 26 kahelas ebenon. Rawsthorne trovis ke ĉiuj 9-plurkvadratoj krom 235 kahelas ebenon. Ĉi tiaj rezultoj estas etenditaj al pli alta ordoj de Rhoads (al ordo 14) kaj aliaj. Plurkvadrataj kahelaroj de ebeno estas klasifikitaj per la simetrioj kaj per la kvanto de aspektoj (orientiĝoj) en kiuj la kaheloj aperas en ili.

Uzoj de plurkvadratoj[redakti | redakti fonton]

Plurkvadratoj estas uzataj en popularaj enigmoj ekde almenaŭ jaro 1907, kaj la numerado de 5-kvadratoj estas datita al antikveco. La observado ke estas 12 malsamaj ŝablonoj (la 5-kvadratoj) kiuj povas esti formitaj per kvin trakonektitaj ŝtonoj sur tabulo de ludo goo estas atribuita al antikva majstro de la ludo. Multaj rezultoj pri la pecoj de 1 al 6 kvadratoj estis unue publikigitaj en Fea Ŝakluda Recenzo inter la jaroj 1937 al 1957, sub la nomo "sekcaj problemoj".

Plurkvadratoj kuraĝigis gravajn esplorojn en matematiko kaj estas fekunda subjekto por logikaj enigmoj kaj ripoza matematiko. Defioj estas ofte por kovrado (kahelado) de preskribita regiono, aŭ la tuta ebeno, kun plurkvadratoj, aŭ faldado de plurkvadrato por krei aliajn formojn. Gardner proponis kelkajn simplajn ludojn kun aro de liberaj 5-kvadratoj kaj ŝakluda tabulo.

Iuj variantoj de la sudoko uzas plurkvadrato-formitajn regionojn sur la krado. La ludo tetriso estas bazita sur la sep unuflankaj 4-kvadratoj, kaj la tabulludo Blokus uzas ĉiujn liberajn plurkvadratojn supren ĝis 5-kvadratoj.

Vidu ankaŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]