Empilement de carrés dans un carré

Page d’aide sur l’homonymie

Pour les articles homonymes, voir Empilement.

L'empilement de carrés dans un carré est un problème d'empilement bidimensionnel dont l'objectif est d'empiler des carrés unités (côté 1) identiques de nombre n dans le carré le plus petit possible de côté a. Si a est un entier, la réponse est a2.

La plus petite valeur de a qui permet d'empiler des carrés de n unités est connue lorsque n est un carré parfait (auquel cas il est √n), ainsi que pour n = 2, 3, 5, 6, 7, 8, 10 , 14, 15, 24 et 35. Le tableau ci-dessous indique la valeur optimale de a pour n ≤ 10[1],[2].

Nombre de carrés unités n Longueur d'un côté du carré extérieur Figure Démonstration[3]
1 1 Immédiat
2 2 Frits Göbel - 1979
3 2 Frits Göbel - 1979
4 2 Immédiat
5 2 + 1/√2 ≈ 2,707 Frits Göbel - 1979
6 3 Michael Kearney et Peter Shiu - 2002
7 3 Erich Friedman - 1999
8 3 Erich Friedman - 1999
9 3 Immédiat
10 3 + 1/√2 ≈ 3,707 Walter Stromquist -1979

D'autres résultats qui ne permettent pas d'établir des empilements optimaux exacts sont connus. Par exemple :

  • S'il est possible d'emballer n2 − 2 carrés unitaires dans un carré du côté a, alors a ≥ n[4].
  • L'approche naïve dans laquelle tous les carrés sont parallèles aux axes de coordonnées et sont placés en contact bord à bord laisse un espace perdu de moins de a + 1 dans un carré du côté a[1].
  • L'espace gaspillé d'une solution optimale est asymptotiquement o(a7/11) ((ici écrit en petite notation))[5].
  • Toutes les solutions doivent gaspiller de l'espace au moins Ω(a1/2) pour certaines valeurs de a[6]
  • 11 carrés unitaires ne peuvent pas être emballés dans un carré de côté inférieur à . En revanche, l'empilement le plus serré connu de 11 carrés se trouve à l'intérieur d'un carré de longueur approximative de 3,8772[2].

Références

  1. ↑ a et b (en) Erich Friedman, Packing unit squares in squares: a survey and new results, (MR 1668055, lire en ligne).
  2. ↑ a et b (en) Walter Stromquist, Packing 10 or 11 unit squares in a square, vol. 10, (MR 2386538, lire en ligne).
  3. ↑ Comment ranger au mieux des carrés, des cercles et autres formes ? Jean-Paul Delahaye, 26 décembre 2018, Pour la science, N° 495
  4. ↑ (en) Michael J. Kearney et Peter Shiu, Efficient packing of unit squares in a square, vol. 9, (MR 1912796, lire en ligne).
  5. ↑ (en) P. Erdős et R. L. Graham, On packing squares with equal squares, vol. 19, coll. « Series A », , 119–123 p. (DOI 10.1016/0097-3165(75)90099-0, MR 0370368, lire en ligne).
  6. ↑ (en) K. F. Roth et R. C. Vaughan, Inefficiency in packing squares with unit squares, vol. 24, coll. « Series A », , 170–186 p. (DOI 10.1016/0097-3165(78)90005-5, MR 0487806).

Liens externes

v · m
Empilement
Empilement de cercles
Empilement de sphères
Empilement de carrés
Autres empilements
Puzzles

Read other articles:

العلاقات الماليزية المصرية

العلاقات الماليزية المصرية ماليزيا مصر   ماليزيا   مصر تعديل مصدري - تعديل   العلاقات الماليزية المصرية هي العلاقات الثنائية التي تجمع بين ماليزيا ومصر.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة ماليزيا مص...

 

Ekspedisi Belanda ke Valdivia

Ekspedisi Belanda ke ValdiviaBagian dari Perang Delapan Puluh TahunHendrik Brouwer mengatur dan memimpin ekspedisi ini hingga ia meninggal di ChiloéTanggal6 November 1642 – 28 December 1643(1 tahun, 1 bulan, 3 minggu dan 1 hari)LokasiPantai Pasifik dari koloni Spanyol di Amerika SelatanPihak terlibat Republik Belanda Kerajaan SpanyolTokoh dan pemimpin Hendrik Brouwer Elias Herckmans Pasukan Chiloé: Andrés Herrera † Fernando de Alvarado Respons Spanyol (1644–1...

 

Tony Goldwyn

Tony GoldwynLahirAnthony Howard GoldwynPekerjaanAktor, direkturTahun aktif1986–sekarangSuami/istriJane Michelle Musky (1987–sekarang) Tony Goldwyn terlahir dengan nama Anthony Howard Goldwyn (lahir 20 Mei 1960 adalah pemeran pria Amerika Serikat. Dia digambarkan penjahat Carl Bruner dalam Ghost, Kolonel Bagley dalam The Last Samurai, dan suara Tarzan dari Disney film animasi Tarzan. Dia bintang di ABC dalam drama Scandal, sebagai Fitzgerald Hibah III, Presiden Amerika Serikat. Filmo...

John Horgan

Premier of British Columbia from 2017 to 2022 For other people named John Horgan, see John Horgan (disambiguation). His ExcellencyJohn HorganHorgan in 2017Canadian Ambassador to GermanyIncumbentAssumed office December 8, 2023Prime MinisterJustin TrudeauPreceded byIsabelle Poupart (acting)36th Premier of British ColumbiaIn officeJuly 18, 2017 – November 18, 2022MonarchsElizabeth IICharles IIILieutenant GovernorJudith GuichonJanet AustinDeputyCarole JamesMike FarnworthPrecede...

 

Yoon So-yi

South Korean actress (born 1985) For the actress born 1993, see Yoon So-hee. In this Korean name, the family name is Moon. In the stage name or pen-name, the surname is Yoon. Yoon So-yiYoon So-yiBornMoon So-yi (1985-01-05) January 5, 1985 (age 39)Seongdong-gu, Seoul, South Korea[1]EducationDongguk UniversityOccupationActressYears active2001–presentAgentEL Park[2]Spouse Jo Sung-yoon ​(m. 2017)​Children1 Korean nameHangul윤소이Hanja尹...

 

Défilé du Père Noël

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article adopte un point de vue régional ou culturel particulier et nécessite une internationalisation (septembre 2022). Merci de l'améliorer ou d'en discuter sur sa page de discussion ! Vous pouvez préciser les sections à internationaliser en utilisant {{section à internationaliser}}. Cet article est une ébauche concernant les traditions. Vous pouvez partager vos connaissances en l’améliorant (...

Quarteira

Civil parish in Algarve, PortugalQuarteiraCivil parish Coat of armsQuarteiraLocation in PortugalCoordinates: 37°04′08″N 8°06′11″W / 37.069°N 8.103°W / 37.069; -8.103Country PortugalRegionAlgarveIntermunic. comm.AlgarveDistrictFaroMunicipalityLouléArea • Total38.16 km2 (14.73 sq mi)Population (2011) • Total21,798 • Density570/km2 (1,500/sq mi)Time zoneUTC±00:00 (WET) • Summer (DS...

 

Pacific spiny dogfish

Species of shark Pacific spiny dogfish Conservation status Least Concern  (IUCN 3.1)[1] Secure  (NatureServe)[2] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Chondrichthyes Subclass: Elasmobranchii Subdivision: Selachimorpha Order: Squaliformes Family: Squalidae Genus: Squalus Species: S. suckleyi Binomial name Squalus suckleyiGirard, 1854[3] Locations of Squalus suckleyi in the Pacific. The Pacific spiny dogfish ...

 

أتراك

هذه المقالة عن المجموعة العرقية الأتراك وليس عن من يحملون جنسية الجمهورية التركية أتراكTürkler (بالتركية) التعداد الكليالتعداد 70~83 مليون نسمةمناطق الوجود المميزةالبلد  القائمة ... تركياألمانياسورياالعراقبلغارياالولايات المتحدةفرنساالمملكة المتحدةهولنداالنمساأسترالي�...

Charles Pelham Villiers

British lawyer and politician The Right HonourableCharles Pelham VilliersEngraving by John Cochran after a portrait by C. A. Du Val.President of the Poor Law BoardIn office9 July 1859 – 26 June 1866MonarchVictoriaPrime MinisterThe Viscount Palmerston The Earl RussellPreceded byThomas Milner GibsonSucceeded byGathorne HardyMember of Parliamentfor Wolverhampton South Wolverhampton (1835–1885)In office6 January 1835 – 16 January 1898MonarchsWilliam IVVictor...

 

Pontificio Collegio Urbano de Propaganda Fide

Catholic university in Rome Not to be confused with Pontifical Urban University. Pontificio Collegio Urbano de Propaganda FideEstablished1 August 1627 (1627-08-01)FounderPope Urban VIIIParent institutionCongregation for the Evangelization of PeoplesReligious affiliationCatholic ChurchRectordon Armando NugnesLocationRome, Italy41°53′58.5″N 12°27′30.1″E / 41.899583°N 12.458361°E / 41.899583; 12.458361Websitewww.collegiourbano.org The Pontificio...

 

Riga Cathedral

Cathedral in Riga, Latvia This article is about the Evangelical Lutheran cathedral of Riga. For the Roman Catholic cathedral, see St. James's Cathedral, Riga. For the Orthodox cathedral, see Cathedral of the Nativity of Christ, Riga. Church in Riga, LatviaRiga CathedralThe Cathedral of Saint MaryRīgas DomsRiga Cathedral with Riga Castle and Daugava River in the backgroundRiga Cathedral56°56′57″N 24°6′16″E / 56.94917°N 24.10444°E / 56.94917; 24.10444Locatio...

Mikroorganisme reduktor sulfat

Desulfovibrio vulgaris salah satu spesies mikroorganisme reduktor sulfat yang banyak dipelajari. Mikroorganisme reduktor sulfat (sulfate-reducing microorganisms, SRM) adalah adalah kelompok mikroorganisme yang terdiri dari bakteri (bakteri reduktor sulfat, sulfate-reducing bacteria, SRB) dan arkea (arkea reduktor sulfat), yang dapat melakukan respirasi anaerobik menggunakan ion sulfat (SO42–) dan mereduksinya menjadi hidrogen sulfida (H2S).[1] Dengan kata lain, mikroorganisme ini ti...

 

Flow (mathematics)

Motion of particles in a fluid For flows in graph theory, see flow network. This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Flow mathematics – news · newspapers · books · scholar · JSTOR (May 2020) Flow in phase space specified by the differential equation of a pendulum. On the horizontal axis...

 

Murcia

For the Anglo-Saxon kingdom, see Mercia. For other uses, see Murcia (disambiguation). Municipality in Region of Murcia, SpainMurciaMunicipalityCathedralCity hall (Moneo building)Monteagudo CastleThe Old BridgeUniversity cloisterCasa Cerdá FlagCoat of armsLocation of MurciaCoordinates: 37°59′10″N 1°7′49″W / 37.98611°N 1.13028°W / 37.98611; -1.13028CountrySpainAutonomous communityRegion of MurciaFounded825 AD (by Abd ar-Rahman II)Government • May...

Perilaku menyimpang

Perilaku menyimpang yang juga biasa dikenal dengan nama penyimpangan sosial adalah perilaku yang tidak sesuai dengan norma sosial di masyarakat atau suatu kelompok atau aturan yang telah diinstitusikan, yaitu aturan yang telah disepakati bersama dalam sistem sosial.[1] Dalam Kamus Besar Bahasa Indonesia perilaku menyimpang diartikan sebagai tingkah laku, perbuatan, atau tanggapan seseorang terhadap lingkungan yang bertentangan dengan norma-norma dan hukum yang ada di dalam masyarakat....

 

Lorenzo Flaherty

Lorenzo Flaherty in una scena del film Pazzo d'amore (1999) Lorenzo Flaherty (Roma, 24 novembre 1967) è un attore italiano, di padre irlandese e di madre italiana[1][2]. Indice 1 Biografia 2 Vita privata 3 Filmografia 3.1 Cinema 3.2 Televisione 4 Programmi televisivi 4.1 Pubblicità 5 Note 6 Collegamenti esterni Biografia Dopo il debutto nel 1986 con il film Dèmoni 2... L'incubo ritorna, regia di Lamberto Bava, lavora anche in teatro sia come attore recitando nel Macbeth sia...

 

鏡板 (圧力容器)

円筒状圧力容器の両端部分に鏡板が溶接されている 鏡板（かがみいた）とは、高圧ガスタンクや原子炉設備等の円筒状圧力容器の両端部をふさぐ[1]、半円状・楕円状などの形状をしている板。 概要 JIS B 8247:1999 圧力容器用鏡板に規格が規定されている。名称の由来は、鏡餅の形状に似ているとも、酒樽の蓋が「かがみ」と呼ばれることに由来するといわれるもの�...

Shooting at the 2024 Summer Olympics – Qualification

This section tabulates the heads of qualification in a form suitable to be filled in as events progress. The full qualification rules[1] for shooting published by ISSF contain intricate conditions too lengthy for inclusion in Wikipedia. Shooting at the2024 Summer OlympicsQualificationRifle50 m rifle three positionsmenwomen10 m air riflemenwomenmixedPistol25 m pistolwomen25 m rapid fire pistolmen10 m air pistolmenwomenmixedShotgunTrapmenwomenSkeetmenwomenmixedvte This article details ...

 

August Lucae

German otologist August Lucae (1835-1911) Johann Constantin August Lucae (24 August 1835 – 17 March 1911) was a German otologist who was a native of Berlin. He studied medicine in Berlin and Bonn, and in 1859 earned his doctorate. He furthered his studies in London with Joseph Toynbee (1815–1866), later returning to Berlin, where he worked in Virchow's pathological institute. In 1871 he became an associate professor, and in 1874 was appointed director of the university policlinic ...