5 ms·

Dividing a Square into 7 Similar Rectangles

129 points by ingve 4y ago

lifthrasiir 4y ago
Previously on HN: https://news.ycombinator.com/item?id=34692537 https://news.ycombinator.com/item?id=34692537 This time a news is that the previously known value for n = 7, 1371, turned out to be incomplete due to the program bug and it is now thought to equal to 1372 instead.
- hgsgm 4y ago
  And the bug was quite silly -- it does a simple standard thing (remove obvious symmetries) in a more complicated way (at the end of a long computation, instead of at the start), incorrectly.
  - phkahler 4y ago
    Always good to test code with and without such optimizations to verify the results are the same. That's not always practical though for large problems and optimizations that yield significant time savings.
- actually_a_dog 4y ago
  As the saying goes, there are only two hard problems in computer science: naming things, cache invalidation, and off by one errors.
tromp 4y ago
> we can get two partitions with the same topology where the rectangles have different proportions! > Here is a picture of the apparently new partition that Daniel Gerbet has found: I was really looking forward to seeing both partitions with this topology, but the article sadly doesn't highlight the other one.
- unnah 4y ago
  They do mention that the new partition #1055 has the same topology as partition #1022, and the partitions are numbered in the longer PDF https://math.ucr.edu/home/baez/mathematical/gerbet_partitioning_square_into_rectangles/rect7_detailed.pdf https://math.ucr.edu/home/baez/mathematical/gerbet_partition.... In the shorter PDF it's on page 19, bottom row, second from the left.
- hackcasual 4y ago
  Did my best to match the colors https://imgur.com/HubwY1d https://imgur.com/HubwY1d
isaacfrond 4y ago
As this incident demonstrates, errors can easily creep into mathematical proofs, even those written by experts. The only way to mitigate this is to use computer-readable proofs, which can be verified by algorithms to ensure correctness. Especially computer generated proofs should be distrusted unless their output is generated as a computer verifiable. Successful example is Flyspeck, that translated a proof with a large computer generated part into a computer readable one (http://www.proof-technologies.com/flyspeck/ http://www.proof-technologies.com/flyspeck/) Computer-readable proofs provide a rigorous and reliable way to verify mathematical results, reducing the likelihood of mistakes and increasing confidence in the validity of mathematical arguments. However, the use of computer-readable proofs is still not widespread in the mathematical community, and it is not yet a standard part of mathematics education. The tools are ready, it is just that doing the hard work going from a handwritten one to a computer-readable proof is not sufficiently appreciated. It should become more widely used in mathematics, and be incorporated into mathematics education curricula at all levels. Doing so will not only help prevent errors but also promote transparency and reproducibility in mathematical research.
- DeathArrow 4y ago
  >The only way to mitigate this is to use computer-readable proofs, which can be verified by algorithms to ensure correctness. What if the algorithms have errors? What if a cosmic ray flips one bit of memory?
  - cjfd 4y ago
    100% accuracy will never be achievable. What might be achievable, though, is a higher degree of confidence than we currently have. Of course, the correctness of algorithms should also have to have a computer validated proof.
  - nkrisc 4y ago
    > What if the algorithms have errors? Errors will always happen. > What if a cosmic ray flips one bit of memory? Run it several times and compare results until you reach the desired level of statistical certainty.
unwind 4y ago
This is a bit whooosh for my poor head, but very cool to notice that Greg Egan [1] (an SF author definitely represented in my bookshelves) is active in that scene. [1]: https://gregegan.net/ https://gregegan.net/
DeathArrow 4y ago
Now we might see this on Leetcode or Hackerrank interviews: "Write a software that takes a number n and outputs the number m, of all different modes a square can be divided into n similar rectangles."
wiz21c 4y ago
Makes me think of Mondrian's paintings :-) Just add the colors :-)
elteto 4y ago
Very cool that Greg Egan did some work on this! He is the author of Permutation City.
robomartin 4y ago
What is the definition of “similar rectangle”?
- shagie 4y ago
  The ratio of the long side to the short side is the same. A rectangle that is 2x1 is similar to a rectangle that is 4x2.
  - robomartin 4y ago
    The images I saw in the two articles (original and update) don't look like the rectangles have the same aspect ratio. I didn't measure them, so, yes, I could be wrong.
Gordonjcp 4y ago
The chart of possible divisions reminds me of those coloured block card things they used for Jet Set Willy's copy protection in the early 80s.

129 points by ingve 4y ago

Previously on HN: https://news.ycombinator.com/item?id=34692537 https://news.ycombinator.com/item?id=34692537 This time a news is that the previously known value for n = 7, 1371, turned out to be incomplete due to the program bug and it is now thought to equal to 1372 instead.

hgsgm 4y ago
And the bug was quite silly -- it does a simple standard thing (remove obvious symmetries) in a more complicated way (at the end of a long computation, instead of at the start), incorrectly.
- phkahler 4y ago
  Always good to test code with and without such optimizations to verify the results are the same. That's not always practical though for large problems and optimizations that yield significant time savings.
actually_a_dog 4y ago
As the saying goes, there are only two hard problems in computer science: naming things, cache invalidation, and off by one errors.

tromp 4y ago

> we can get two partitions with the same topology where the rectangles have different proportions! > Here is a picture of the apparently new partition that Daniel Gerbet has found: I was really looking forward to seeing both partitions with this topology, but the article sadly doesn't highlight the other one.

unnah 4y ago
They do mention that the new partition #1055 has the same topology as partition #1022, and the partitions are numbered in the longer PDF https://math.ucr.edu/home/baez/mathematical/gerbet_partitioning_square_into_rectangles/rect7_detailed.pdf https://math.ucr.edu/home/baez/mathematical/gerbet_partition.... In the shorter PDF it's on page 19, bottom row, second from the left.
hackcasual 4y ago
Did my best to match the colors https://imgur.com/HubwY1d https://imgur.com/HubwY1d

isaacfrond 4y ago

As this incident demonstrates, errors can easily creep into mathematical proofs, even those written by experts. The only way to mitigate this is to use computer-readable proofs, which can be verified by algorithms to ensure correctness. Especially computer generated proofs should be distrusted unless their output is generated as a computer verifiable. Successful example is Flyspeck, that translated a proof with a large computer generated part into a computer readable one (http://www.proof-technologies.com/flyspeck/ http://www.proof-technologies.com/flyspeck/) Computer-readable proofs provide a rigorous and reliable way to verify mathematical results, reducing the likelihood of mistakes and increasing confidence in the validity of mathematical arguments. However, the use of computer-readable proofs is still not widespread in the mathematical community, and it is not yet a standard part of mathematics education. The tools are ready, it is just that doing the hard work going from a handwritten one to a computer-readable proof is not sufficiently appreciated. It should become more widely used in mathematics, and be incorporated into mathematics education curricula at all levels. Doing so will not only help prevent errors but also promote transparency and reproducibility in mathematical research.

DeathArrow 4y ago
>The only way to mitigate this is to use computer-readable proofs, which can be verified by algorithms to ensure correctness. What if the algorithms have errors? What if a cosmic ray flips one bit of memory?
- cjfd 4y ago
  100% accuracy will never be achievable. What might be achievable, though, is a higher degree of confidence than we currently have. Of course, the correctness of algorithms should also have to have a computer validated proof.
- nkrisc 4y ago
  > What if the algorithms have errors? Errors will always happen. > What if a cosmic ray flips one bit of memory? Run it several times and compare results until you reach the desired level of statistical certainty.

unwind 4y ago

This is a bit whooosh for my poor head, but very cool to notice that Greg Egan [1] (an SF author definitely represented in my bookshelves) is active in that scene. [1]: https://gregegan.net/ https://gregegan.net/

DeathArrow 4y ago

Now we might see this on Leetcode or Hackerrank interviews: "Write a software that takes a number n and outputs the number m, of all different modes a square can be divided into n similar rectangles."

wiz21c 4y ago

Makes me think of Mondrian's paintings :-) Just add the colors :-)

elteto 4y ago

Very cool that Greg Egan did some work on this! He is the author of Permutation City.

robomartin 4y ago

What is the definition of “similar rectangle”?

shagie 4y ago
The ratio of the long side to the short side is the same. A rectangle that is 2x1 is similar to a rectangle that is 4x2.
- robomartin 4y ago
  The images I saw in the two articles (original and update) don't look like the rectangles have the same aspect ratio. I didn't measure them, so, yes, I could be wrong.

Gordonjcp 4y ago

The chart of possible divisions reminds me of those coloured block card things they used for Jet Set Willy's copy protection in the early 80s.