tailieunhanh - Báo cáo toán học: "Optimal Packings of 13 and 46 Unit Squares in a Square"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Optimal Packings of 13 and 46 Unit Squares in a Square. | Optimal Packings of 13 and 46 Unit Squares in a Square Wolfram Bentz Department of Mathematics Statistics and Computer Science Xavier University Antigonish Nova Scotia Canada wbentz@ Submitted Aug 31 2009 Accepted Sep 6 2010 Published Sep 13 2010 Mathematics Subject Classification 05B40 52C15 Abstract Let s n be the side length of the smallest square into which n non-overlapping unit squares can be packed. We show that s m2 3 m for m 4 7 implying that the most efficient packings of 13 and 46 squares are the trivial ones. The study of packing unit squares into a square goes back to Erdos and Graham 2 who showed that large numbers of unit squares can be packed in a way that is surprisingly efficient. Gobel 5 later addressed the problem of finding efficient packings for a given number n of unit squares and the subject was subsequently published in the popular science literature in various articles by Gardner 4 . Let s n be the side length of the smallest square into which n non-overlapping unit squares can be packed. Non-trivial cases for which s n is known are s m2 1 s m2 2 m for m 2 Nagamochi 7 single values previously shown by Gobel 5 El Moumni 1 and Friedman 3 s 5 2 yj 1 Gobel 5 s 6 3 Kearney and Shiu 6 and s 10 3 yj 1 Stromquist 9 . There are moreover non-trivial best packings and lower bounds known for various values of n. An introduction to the problem as well as an overview of the basic techniques used in the following can be found in the survey article by Friedman 3 . We will show s m2 3 m for m 4 7 which implies that the optimal packings of 13 and 46 squares are the trivial ones with all edges of the unit squares either parallel or perpendicular to those of the containing square. While our results strongly suggest that the same formula holds for the intermediate values m 5 6 no specialized results are currently known in these cases for which the best established packings are trivial and the best lower bounds follow from the general formula