Empaquetat de quadrats

El empaquetat de quadrats és un problema d'empaquetat a on l'objectiu és determinar quànts quadrats congruents es poden empaquetar en una forma més gran, a sovint un quadrat o un círcul.

Empaquetat de quadrats en un quadrat

Empaquetar quadrats en un quadrat és el problema de determinar el número màxim de quadrats unitat (quadrats de llongitut de costat un) que es poden empaquetar dins d'un quadrat més gran de llongitut de costat $a$. Si $a$ és un número entero, la resposta és $a^2,$, pero la cantitat precisa (o inclús asintòtica) de l'espai que queda sense cobrir per a un $a$ arbitrari no sancer és una pregunta oberta.

El valor més chicotet de $a$ que permet empaquetar quadrats unitaris $n$ es coneix quan $n$ és un quadrat perfecte (en el cas del qual és $\sqrt{n}$), aixina com para $n=$2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47 i 48. Per a la majoria d'estos números (en l'única excepció de 5 i 10), el empaquetamiento és el natural en quadrats alineats en els eixos horisontal i vertical, i $a$ és $\lceil \sqrt{n}\rceil$, a on $\lceil \rceil$ a on ceiling és la funció redonege cap a dalt. La figura mostra els empaquetamientos òptims per a 5 i 10 quadrats, els dos números més menuts de quadrats per als quals el empaquetamiento òptim involucra dispondre quadrats inclinats.

El cas més chicotet sense resoldre implica empaquetar 11 quadrats unitaris en un quadrat més gran. No es poden empaquetar 11 unitats de quadrats en un quadrat de llongitut de costat menor que $2+2\sqrt{4/5}\approx 3.789$. Pel contrari, el empaquetamiento més apretat conegut d'11 quadrats està dins d'un quadrat de llongitut de costat d'aproximadament 3,877084; solució trobada per Walter Trump.

Resultats asintòtics

Per a valors majors de la llongitut del costat $a$, es desconeix el número exacte de quadrats unitaris que poden empaquetar-se en un quadrat de costat $a\times a$. Sempre és possible empaquetar una cuadrícula $\lfloor a\rfloor \times \lfloor a\rfloor$ de quadrats unitaris alineats en l'eix, pero açò pot deixar un àrea gran, aproximadament $2a(a-\lfloor a\rfloor )$, descoberta i desperdiciada. En canvi, Paul Erdős i Ronald Graham varen demostrar que per a un empaquetat diferent per mig de quadrats unitaris inclinats, l'espai desperdiciat podria reduir-se significativament a $o(a^{7/11})$ (ací escrit com cota superior asintòtica). Posteriorment, Graham i Fan Chung varen reduir encara més l'espai desperdiciat a $O(a^{3/5})$. No obstant, com Klaus Roth i Bob Vaughan varen demostrar, totes les solucions deuen desperdiciar a lo manco un espai de $\Omega (a^{1/2}(a-\lfloor a\rfloor ))$. En particular, quan $a$ és un número semientero, l'espai desperdiciat és a lo manco proporcional al seu raïl quadrada. La taxa de creiximent asintòtica precisa de l'espai desperdiciat, inclús per a llongituts de costats semienteros, seguix sent un problema no resolt.

Alguns números de quadrats unitaris mai són el número òptim en un empaquetamiento. En particular, si un quadrat de tamany $a\times a$ permet empaquetar $n^2-2$ quadrats unitaris, llavors deu donar-se el cas de que $a\ge n$, i que també és possible un empaquetamiento de quadrats unitaris $n^2$.

Empaquetat de quadrats en un círcul

Empaquetar quadrats en un círcul és un problema relacionat en empaquetar n quadrats unitaris en un círcul en un radi lo més chicotet possible. Per a este problema, es coneixen bones solucions per a n fins a 35. A continuació es mostren les solucions mínimes per a n fins a 12:

Número de quadrats	Ràdio del círcul
1	0.707...
2	1.118...
3	1.288...
4	1.414...
5	1.581...
6	1.688...
7	1.802...
8	1.978...
9	2.077...
10	2.121...
11	2.214...
12	2.236...

Vore també

• Empaquetat de círculs en un quadrat
• Quadratura del quadrat
• Empaquetat de rectànguls
• Problema del sofà