Skip to main content

Timeline for 1 rectangle <= 4 squares

Current License: CC BY-SA 2.5

24 events
when toggle format what by license comment
Mar 7, 2010 at 22:35 history edited TonyK CC BY-SA 2.5
added 11 characters in body
Mar 3, 2010 at 21:49 history edited TonyK CC BY-SA 2.5
added 35 characters in body
Mar 3, 2010 at 14:00 history edited TonyK CC BY-SA 2.5
added 40 characters in body; added 2 characters in body
Mar 2, 2010 at 22:35 history edited TonyK CC BY-SA 2.5
added 14 characters in body; Post Made Community Wiki
Mar 2, 2010 at 21:49 history edited TonyK CC BY-SA 2.5
added 85 characters in body
Mar 2, 2010 at 21:39 history edited TonyK CC BY-SA 2.5
deleted 2890 characters in body; edited body
Mar 2, 2010 at 18:09 comment added TonyK I've just had a look at some linear programming pages, and it seems that searching for integer solutions is slower, not faster. Oh well.
Mar 2, 2010 at 17:30 history edited TonyK CC BY-SA 2.5
added 10 characters in body; edited body; added 20 characters in body
Mar 2, 2010 at 17:18 comment added TonyK FG, is your software able to look for integer solutions? If so, you can set the square constraint to |sum| <= 15,and the central 3x7 rectangle to 56. Then the solution will be much nicer, and probably faster to find. (What software are you using?)
Mar 2, 2010 at 15:35 comment added Yaakov Baruch this thread beats a lot of good novels!
Mar 2, 2010 at 15:27 comment added F_G OK, I have now a new model that is much easier to solver (uses sparser constraints) - I can confirm that 2x7 leads indeed to 67/18. And 3x7 leads to 56/15. More coming later today ...
Mar 2, 2010 at 14:26 comment added F_G The problem with my 1x8 test is that the solution I get does not seem to be easy to round nicely like the previous ones (some factors are obvious, like 7, but others seem inconsistent). Anyway, I put it here: dl.dropbox.com/u/217239/sol_rectangle.html I am using the symmetry.
Mar 2, 2010 at 13:46 comment added TonyK Also, FG, have you built the symmetry into your model? So that you only need 23x23 variables for a 45x45 grid?
Mar 2, 2010 at 13:16 comment added TonyK That's exactly what I'm doing, Yaakov. But it's terribly slow. FG has a much better method -- one minute, instead of a day or two! Can you say a bit more about it, FG? And perhaps you could post your solution for the 8x1 rectangle.
Mar 2, 2010 at 13:06 history edited TonyK CC BY-SA 2.5
added 83 characters in body
Mar 2, 2010 at 11:40 comment added Yaakov Baruch Once you have a consistent and non-improvable set of bounds, you can collapse one interval to a point within, one rectangle at a time, then refresh the set of bounds and repeat the procedure until all intervals have shrunk to a point. Unfortunately, I don't know if one can also collapse the 3 (or 1) symmetric images of the chosen rectangle without a refresh in between.
Mar 2, 2010 at 11:35 comment added F_G TonyK, I can confirm 26/7 is possible for a 1x8 rectangle within a 39x46 grid. Maybe we can discuss how we obtain those grids ? I use a linear programming formulation (a variable for every cell, a constraint for every square), which is quick (optimally solved in less than a minute) but runs out of memory around the 45x45 size (too many squares - it should be possible to remove some redundancies).
Mar 2, 2010 at 10:33 history edited TonyK CC BY-SA 2.5
added 9 characters in body
Mar 2, 2010 at 10:01 history edited TonyK CC BY-SA 2.5
added 520 characters in body; added 9 characters in body
Mar 2, 2010 at 7:52 comment added TonyK Yes, LK, the upper bounds are proved. (But the program uses floating-point arithmetic. For a proper computer-assisted proof, I suppose it would need to use rationals.)
Mar 2, 2010 at 7:51 history edited TonyK CC BY-SA 2.5
added 1245 characters in body
Mar 2, 2010 at 3:17 comment added F_G As far as I can check, 25/7 can also be obtained on a smaller 23x29 grid ; 31x36 seems optimal for 85/23.
Mar 2, 2010 at 2:08 comment added F_G TonyK, this is great ! I thought for a while that 3.5 could not be beaten, but I was looking at wrong (central rectangle/grid) size combinations (mostly too small grids).
Mar 1, 2010 at 23:10 history answered TonyK CC BY-SA 2.5