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!

  • 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 May 30 '13 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 May 30 '13 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 May 31 '13 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 May 31 '13 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.