Re: Rectangles

From: Oscar Lanzi III (ol3_at_webtv.net)
Date: 01/16/05 

Date: Sat, 15 Jan 2005 19:48:02 -0600

You solved half the prolem. Now for the other half. What is the score
for rectangles with relatively prime sides?

In your 2x3 example, where 2 and 3 are relatively prime, you got 4. Now
let's go slowly down the digaonal and see what happens. We start by
going into one square, and stay in that square until -- we cross a grid
line. That's when we add another square to our score. We find, as we
continue, that we add two more squares by crossing two more grid lnes,
for a total of 3 crossings. Thus 4 squares -- the one we started with
and the three we got into cossing the grid lines.

The score for a given rectangle is the number of points where the
diagonal crosses a grid line, plus one for the initial square. Now if
the retangle has relatively prime sides, as assumed in this discussion,
then the grid lines are crossed one at a time -- there's no point inside
the rectangle where two perpendicular grid lines are crossed at the same
time. In an mxn rectangle there are m-1 grid lines one way and n-1 grid
lines the other way. Ergo m+n-2 crossings plus the initial square gives
m+n-1 for the score of an mxn rectangle, when m and n are relatively
prime. Thus in a 2x3 rectnagle, the score is 2+3-1 = 4.

Now you can combine this result with the reduction formula that you've
already posted. You should find that the general formula for any m and
n, relatively prime or not, is m+n-gcd(m,n).

--OL

Relevant Pages

  • RE: Help with developing sudoku gui using GDI+
    ... x/y mouse coordinates to indices in your array. ... Let's assume that your grid ... information like the number that is already filled in on the cell. ... the selected rectangle. ...
    (microsoft.public.dotnet.framework.drawing)
  • Re: Why is OO Popular?
    ... Ellipses are circles is horribly wrong and squares are rectangles is ... Circles are ellipses breaks LSP ... > rectangle can be changed independently ... square value in a rectangle variable or a square value in a square ...
    (comp.object)
  • Re: Agile Ecosystems Vs (Rational) Unified Process
    ... > conflict between Rectangle and Square, and not one line of code ... and practice on the other are seen as mostly independent and separate ... Google Home - Advertising Programs - Business Solutions - About Google ...
    (comp.object)
  • Re: SubTyping versus SubClassing
    ... small subset of ones used in mathematics. ... >> which you'd better have a square for each rectangle, ... Operations defined on the types are that theorems we have to prove ...
    (comp.object)
  • Re: Frage zu verdecktem Member
    ... definieren und zwar in dem man sagt, die Menge der Quadrate ist die Menge aller Rechtecke für die gilt, dass beide Seiten gleich lang sind. ... In Java ist ein Rectangle auch dann ein Rectangle wenn beide Seiten gleich lang sind und kann nicht ein Square werden, weil das Typsystem es nicht erlaubt. ...
    (de.comp.lang.java)