Čtvercové balení ve čtverci - Square packing in a square
Nevyřešený problém v matematice: Jaká je rychlost asymptotického růstu promarněného prostoru pro balení čtverců na půlčíselný čtverec? (více nevyřešených úloh z matematiky) |
Čtvercové balení ve čtverci je problém s balením kde cílem je určit kolik čtverce první strany (jednotkové čtverce) lze zabalit do čtvercového boku . Li je celé číslo, odpověď je , ale přesné, nebo dokonce asymptotické, množství promarněného prostoru pro jiné než celé číslo je otevřená otázka.[1]
Malý počet čtverců
Nejmenší hodnota který umožňuje balení jednotkové čtverce jsou známy, když je dokonalý čtverec (v takovém případě je ), stejně jako pro 2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47 a 48. U většiny z těchto čísel (s výjimkou pouze 5 a 10) se balení je přirozené s čtverci zarovnanými do osy a je .[2][3]Obrázek ukazuje optimální ucpávky pro 5 a 10 čtverců, dva nejmenší počty čtverců, u nichž optimální balení zahrnuje nakloněné čtverce.[4][5]
Nejmenší nevyřešený případ zahrnuje balení 11 čtverců jednotek do většího čtverce. 11 čtverců jednotek nelze zabalit do čtverce strany menší než . Naproti tomu nejužší známé balení 11 čtverců je uvnitř čtverce o délce strany přibližně 3,877084, což mírně vylepšuje podobné balení nalezené dříve Walter Trump.[6]
Asymptotické výsledky
Pro větší hodnoty délky strany , přesný počet jednotkových čtverců, které mohou zabalit čtverec zůstává neznámý. Vždy je možné zabalit a mřížka osově zarovnaných čtverců jednotek, ale to může zanechat přibližně velkou plochu , nepokryté a zbytečné.[4]Namísto, Paul Erdős a Ronald Graham ukázal, že u jiného balení pomocí nakloněných jednotkových čtverců by se zbytečný prostor mohl výrazně snížit na (zde napsáno v malý o zápis ).[7]V nepublikovaném rukopisu Graham a Fan Chung dále omezil zbytečný prostor na .[8]Nicméně, jak Klaus Roth a Bob Vaughan všechna řešení musí přinejmenším plýtvat prostorem . Zejména když je napůl celé číslo, promarněný prostor je alespoň úměrný druhé odmocnině.[9] Přesné rychlost asymptotického růstu promarněného prostoru, i pro poloviční délky stran, zůstává otevřený problém.[1]
Některé počty jednotkových čtverců nejsou nikdy optimálním počtem v balení. Zejména pokud je čtverec velikosti umožňuje balení jednotkové čtverce, pak tomu tak musí být a to balení možné jsou také čtverce jednotek.[2]
Čtvercové balení v kruhu
Souvisejícím problémem je balení n jednotkové čtverce do kruhu s co nejmenším poloměrem. Pro tento problém jsou známá dobrá řešení n až 35. Zde je minimální řešení pro n až 12:[10]
Počet čtverců | Poloměr kruhu |
---|---|
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... |
Viz také
Reference
- ^ A b Brass, Peter; Moser, William; Pach, János (2005), Výzkumné problémy v diskrétní geometrii, New York: Springer, str. 45, ISBN 978-0387-23815-9, PAN 2163782
- ^ A b Kearney, Michael J .; Shiu, Peter (2002), "Efektivní balení jednotkových čtverců do čtverce", Electronic Journal of Combinatorics, 9 (1), Research Paper 14, 14 pp., PAN 1912796.
- ^ Bentz, Wolfram (2010), „Optimální balení čtverců 13 a 46 jednotek ve čtverci“, Electronic Journal of Combinatorics, 17 (1), Research Paper 126, PAN 2729375
- ^ A b Friedman, Erich (2009), „Balení jednotkových čtverců do čtverců: průzkum a nové výsledky“, Electronic Journal of Combinatorics, Dynamický průzkum 7, PAN 1668055.
- ^ Stromquist, Walter (2003), „Balení 10 nebo 11 čtverců jednotek do čtverce“, Electronic Journal of Combinatorics, 10, Research Paper 8, PAN 2386538.
- ^ Gensane, Thierry; Ryckelynck, Philippe (2005), „Vylepšené husté balíčky shodných čtverců ve čtverci“, Diskrétní a výpočetní geometrie, 34 (1): 97–109, doi:10.1007 / s00454-004-1129-z, PAN 2140885
- ^ Erdős, P.; Graham, R. L. (1975), „Na balení čtverců se stejnými čtverci“ (PDF), Journal of Combinatorial Theory, Řada A, 19: 119–123, doi:10.1016/0097-3165(75)90099-0, PAN 0370368.
- ^ *Chung, Fan; Graham, Ron, Efektivní balení jednotkových čtverců ve velkém čtverci (PDF), vyvoláno 2019-04-28
- ^ Roth, K.F.; Vaughan, R. C. (1978), „Neúčinnost balení čtverců jednotkovými čtverci“, Journal of Combinatorial Theory, Řada A, 24 (2): 170–186, doi:10.1016/0097-3165(78)90005-5, PAN 0487806.
- ^ Friedman, Erich. „Čtverce v kruzích“.
externí odkazy
- Čtverce ve čtvercích, Erich's Packing Center, Erich Friedman, Stetson University