Jump to content

Wikipedia:Reference desk/Archives/Mathematics/2018 September 24

From Wikipedia, the free encyclopedia
Mathematics desk
< September 23 << Aug | September | Oct >> September 25 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


September 24

[edit]

Partitioning a rectangle

[edit]

If I divide an axis aligned rectangle using axis aligned cuts, it seems that to avoid having a cut extend all the way across the rectangle I need to divide into at least five areas:

AAB
CDB
CEE

Where does this 5 come from, and what would it be in higher dimensions?

2A01:E34:EF5E:4640:D1FB:4472:BF60:AD71 (talk) 23:17, 24 September 2018 (UTC)[reply]

If I understand what you are doing, I think I can do it in four areas. Bubba73 You talkin' to me? 00:29, 25 September 2018 (UTC)[reply]
Well, must the smaller areas be rectangles? Bubba73 You talkin' to me? 00:56, 25 September 2018 (UTC)[reply]
I'm not fussed about the areas of the (non zero) relative areas of the final rectangles I just want there to be as few as possible and for none of the cuts to run all the way across the original rectangle. It doesn't seem to be possible with fewer than five rectangles in two dimensions. But why five? And how any in three, four or n dimensions? 2A01:E34:EF5E:4640:D1FB:4472:BF60:AD71 (talk) 02:17, 25 September 2018 (UTC)[reply]
If the smaller areas have to be rectangles, then five is the minimum. This isn't much of a proof, but it can be done with five and it can't be done with four. I don't know about higher dimensions. Bubba73 You talkin' to me? 02:56, 25 September 2018 (UTC)[reply]
  • Let's formalize a bit. Assume we are talking about a hypercuboid in dimension d. Visualize each cut as sawing through the cuboid; I understand that we require , else in d=2 there is a solution with four cuts: with cuts alongside the boundaries AB, AC, BD and CD. Assume we want final areas must be hyperrectangles themselves, otherwise in d=2 there is a solution with two cuts: .
The problem depends on what "avoiding a cut extend all the way across" means, and this already bites us on d=3. If it means that that no hyperplane (plane for d=3) can fit inside the cuts (or equivalently that any single cut does not already separate the initial cuboid in two parts) then OP's d=2 solution with 5 pieces is valid at every dimension: for d=3, imagine it is a top view of a cuboid that is sliced alongside the whole height, for higher dimensions that is pretty much the same.
However, it could be understood as meaning that no line can fit inside the cuts, in which case that is tougher. For each dimension i, if you make two cuts with coordinates (assuming a cube of side 1) , I have the feeling that you satisfy the conditions (it is easy to check that no line goes through, but I am not entirely sure the pieces are hypercuboids), that these 2d cuts create 2d+1 pieces (?), and that it is optimal (??). TigraanClick here to contact me 15:27, 25 September 2018 (UTC)[reply]
I'm pretty sure that for the second interpretation there is no solution for d=3 dividing the cube on coordinate multiples of 1/3. Or what amounts to the same thing without fractions, there's no way to divide a 3x3x3 cube into rectangular boxes with integer sides without a cut from one face to the opposite face. Suppose there were. Consider the top layer as a way to cut the 3x3 square into rectangles. None of the square's cuts can go from one edge to the opposite edge, but the only way this can happen is if the square is divided according to the pattern given above or its mirror image. In any case one of the rectangles is the center square. The same argument applies to the middle and bottom layers, so there must be cuts around the center column from the top face to the bottom, and this contradicts the assumption. The argument generalizes to 3x3xn for any n, but I don't know if it's possible for 3x4x4. --RDBury (talk) 21:15, 25 September 2018 (UTC)[reply]
True... After playing around on (inadequate) graphics software, it seems my proposed solution does not cut it (ba dum tss). As in, it cuts out the central cube, but the rest is still in one piece. TigraanClick here to contact me 12:38, 28 September 2018 (UTC)[reply]
This brain teaser was posed at Wikipedia:Reference desk/Archives/Mathematics/2018 June 23#Bathroom tiling question... but elicited no answers.

A year-to-view calendar has the months in a conventional arrangement of three months in each of four rows. The names of the months are printed as normal, but the days (Sunday to Saturday) and the dates (1 to 28, 29, 30, or 31 as the case may be) are printed on removable tiles. You can choose from 1x1 squares (for a single month), 1x2 rectangles (for two adjoining months in a single row) or 1x3 rectangles (covering the whole row) and both sides of the tiles are available for printing. What is the minimum number of tiles you need to print up to ensure your calendar can be used in any year?

Anyone care to take a second look? 86.155.145.191 (talk) 10:58, 2 October 2018 (UTC)[reply]