10
$\begingroup$

I thought that rectangles were simple, and squares even simpler. Until my research has led me to several questions about rectangles and squares, which I can't solve.

I started by posting this question in math.stackexchange: Probable Squares in a Square Cake. Finally I found a solution for 2 players, but for 3 or more players the problem becomes much more difficult, and I don't have a solution yet.

So I posted a related question that is simpler (- no probability measures, only points): Square Cake with Raisins, for which I even offered a bounty, but still no solution.

And a third related question, which is yet simpler (- no points, only squares): One Square per Person; I found an upper bound, but it is not tight.

A fourth question which is also related is: Usable Rectangles

I feel that I could approach such questions better with some lemmas about squares and rectangles.

As an example, I managed to found an upper bound to one square per person, using the following lemma: "a square A can intersect at most 4 interior-disjoint squares that are as large or larger that A." It may seem a simple claim to the expert mathematician, but I am not a mathematician, and for me, a collection of such lemmas would be very helpful.

Can you suggest a textbook or a review paper, that summarizes such basic facts about squares and rectangles?

Some things I have already found:

  • A New Tractable Subclass of the Rectangle Algebra - the title is promising, but actually the paper deals with constraints about rectangles. The paper relates to the question: 'given a set of constraints such as "rectangle A should be above rectangle B, B should partially overlap C, and C should contain A". is there an assignment of rectangles that satisfy all constraints?'.
  • Packing Problems - surveys several solutions to several problems of packing in 2 dimensions, for example: 'given a supply of large rectangles and several small rectangles, what is the optimal way to pack the small rectangles in the large ones, such that the number of large rectangles needed is minimized?'.
  • The quest for the perfect square - deals with the question: 'How can we divide a square into sub-squares that are all different?'. This is related to division, however, the limitation to different squares is not relevant in my case.
  • A Doubly Exponentially Crumbled Cake - deals with division of a square cake, however, the goal is to maximize the area, not the probability.
  • Squares in Squares - several best-known results for packing unit squares in larger squares.

These papers are all interesting, but I am still looking for some basic rectangles/squares lemmas that will help me make a progress in my research. Thanks!

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ One note that comes to mind (and this may not be of any use) is that a square can be decomposed into 1, 4, or 6, 7, 8, ... subsquares (not necessarily of the same size). Showing 2, 3, and 5 are impossible is a nice exercise (especially 5). Once you have 1, 6, and 8, you can take a single subsquare and re-subdivide into a 2x2 for a net gain of 3. E.g., 1 to 4, and then 4 to 7; and then from 6, 7, and 8 you can get all subsequent natural numbers. (There are lots of other fun students activities that can be done with this idea, but that would stray too far from your question.) $\endgroup$
    – Benjamin Dickman
    Commented May 30, 2013 at 22:52
  • 1
    $\begingroup$ Also: to count, e.g., the number of rectangles that can be formed (in the natural way) in an n by n grid of unit squares, turn it into an n by n multiplication table and sum the entries. In particular, the number of squares that can be formed in an n by n grid of unit squares is the sum along the diagonal, n(n+1)(2n+1)/6. $\endgroup$
    – Benjamin Dickman
    Commented May 30, 2013 at 22:55
  • $\begingroup$ >Probable Squares in a Square Cake. Finally I found a solution for 2 players, but for 3 or more players the problem becomes much more difficult, and I don't have a solution yet.< Meaning Alice gets the least probable square out of $k\ge 3$ she draws? $\endgroup$
    – fedja
    Commented May 31, 2013 at 1:05
  • $\begingroup$ @fedja: yes. I started working on k=3 , and found out that it requires (at least in the method I used) to solve the problem for k=2 and non-square cakes, specifically L-shaped cakes. With any shape of a cake, the solution is different. I am looking for a way to generalize.. $\endgroup$
    – Erel Segal-Halevi
    Commented May 31, 2013 at 6:20
  • 1
    $\begingroup$ You might see whether you can gain understanding by considering Schramm's theorem, as detailed recently in this MO question: Squaring a square and discrete Ricci flow. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 7, 2020 at 1:37

0

Reset to default

You must log in to answer this question.