How Many Squares does the Diagonal of an m x n Rectangle Cross?

Given an m x n rectangle drawn on a square grid, we calculate the number of squares that its diagonal passes through.
I found this problem on Cut-the-Knot:
www.cut-the-knot.org/Curricul...
00:00 Intro
00:25 Counting squares
03:22 Solution: 12 x 8 example
06:32 General solution

[@zygoloid]

Neat! We can approach this very similarly using the inclusion-exclusion principle. If we consider the diagonal to cross (0,0) but not (m,n), then the number of squares visited is the number of crossings between squares, and: |crossings| = |horizontal grid crossings u vertical grid crossings| = |h crossings| + |v crossings| - |h crossings n v crossings| = m+n-gcd(m,n) This then generalizes into higher dimensions. Eg, in 3d, the diagonal of a k x m x n cuboid crosses k+m+n-gcd(k,m)-gcd(m,n)-gcd(n,k)+gcd(k,m,n) 1x1x1 cubes.

[@derpsalot6853]

definitely one of the most underrated math channels on youtube

[@Utesfan100]

You outline is what I envisioned after you presented the problem, but as you went through it another approach appeared. The line must cross m vertical lines and n horizontal lines. This gives us the draft formula m+n. Considering any example, we will find that we have over counted the points where we go through a corner. There must be gcd(m,n) such points. Thus there are m+n-gcd(m,n) squares. Nice video, as always.

[@kruksog]

You're doing good stuff. Please keep at it.

[@BsktImp]

Love how these vids remind me of the 70s & 80s Open University programmes.

[@antoinebugnicourt808]

I see this video after a little obsessive moment with Egyptian fractions earlier in the afternoon, so the GCD intuition almost hit me up right away! Good video as usual, I like those short math digressions you offer on here.

[@perappelgren948]

Once again, excellent! Although I hunched the contour of the solution from the outset, I was surprised by the actual result. Very good! Keep up the good work! 👍👍

[@erickehr4475]

The last stage seemed overly complicated. You pass through gcd vertices including the very top right, which doesn’t count so you have m + n - 1 - (gcd - 1) = m + n - gcd

[@worldnotworld]

Yes, that's how I thought of it too. You can bypass dividing the rectangle into smaller ones entirely: use m+n-1 as introduced, and subtract one for each intersection crossed but the last = gcd(m,n)-1.

[@truthkmgmailcom]

H

[@fedorlozben6344]

I thought the same and was very surprised when he decided to divide by gcd.

[@Happy_Abe]

@6:45 it should be n/m

[@stewartzayat7526]

Thankfully the problem is symmetric, so it all checks out nicely either way

[@livedandletdie]

Whichever axis you care about in the 2d question, is not important as long as you're consistent. I like the 1d case, the answer is always 0, because it's only traveling on the edge. It's the easy case.

[@Happy_Abe]

@@stewartzayat7526 yep still works just wanted to say

[@comic4relief]

​@@stewartzayat7526Good point; but it was still an error.

[@user-rh5jd4ch9r]

It was so crazy to learn this thanks dr your the best

[@rsivaraman1729]

In the last part the slope would actually be n/m and not m/n as shown in the video. The final answer wouldn't get affected though because of symmetry

[@Roxor128]

This feels like it's done half the work towards creating an algorithm for drawing a line on a screen.

[@molybd3num823]

thats what came to my mind as well

[@anandarunakumar6819]

Last result is amazing!

[@stevenmellemans7215]

This is strongly linked with the video ‘A tricky sum to solve’ from a year ago.

[@stevenmellemans7215]

Nice proof for mn-2sum(k=1 to n-1; floor(k.m/n))=m+n-gcd(m,n) 😊

[@RigoVids]

I would immagine it’s something like m+n -greatest divisor. The reason I guess this is because every time you would add a square would occur because you enter a new square either horizontally or vertically. The only time this doesn’t happen is 1) at the end of the process, meaning both m and n have been reached (the line followed the whole numbers instead of being partially along) and whenever it passes through a vertex of the grid. Whenever that happens, both the m and n contribute to a new box, but only one new box is generated. I think graphically it’s obvious through iteration that the line can only land on a vertex when m and n are not comprime, meaning they have a lcd greater than one. A more general way to think about it is that they’re already not coprire since they at least share a factor of one, which is why the line lands on the vertex opposite the starting point. Then for every vertex the line passes through, that increases the lcd by one. It then follows that since the original line will result in m+n-1, that the 1 represents the GCD. Just from the example given it seems to make sense, 5 and 3 have a GCD of 1, so 3+5-1= 7

[@paragggoyal1552]

awesome problem!

[@rogerkearns8094]

Who'd have thought it? Interesting, thank you.

[@elrichardo1337]

eyy i remember this problem archetype back in 2018-2019 a buncha different contests all had their own instances of this (most notably the AMC 10/12 and ARML)

[@GnarGnaw]

I immediately got the idea of using the gcd, knowing the fact that a line between two vertices does not intersect any vertex if and only if the coordinates are coprime

[@Gailon1000]

Why is that?

[@cosimobaldi03]

Cool!

[@JWentu]

cool!

[@farfa2937]

Take a shot every time he says “greatest common divisor”

[@yurenchu]

When m, n are co-prime, the answer is m+n-1 . So when m, n are not co-prime, then let k = gcd(m,n), divide the diagonal in k equal segments, each segment crosses (m/k + n/k -1 ) squares, and so the answer for the m, n rectangle is k*(m/k + n/k - 1) = m + n - k = m+n - gcd(m,n).

[@comic4relief]

Seems like he basically said that.

[@yurenchu]

@@comic4relief Yeah, sorry about that. I finished typing long before I reached the end of the video.

[@comic4relief]

@@yurenchu Ah! He never says co-prime though.

[@oliverwest5336]

Would this extend out into 3D? Would the diagonal of an L*M*N cuboid pass through L+M+N-GCD(L,M,N) cubes? Further, would the general formula for an n-dimensional "box" with sides X_1 to X_n be = [Sum(1 to n) X_n] + GCD(X_1,...,X_n)?

[@patronumtwok2891]

I think you would need taking some pairwise GCDs for a more general formula (otherwise there can be times when it passes through the edge of a cube but not the vertex for example)

[@oliverwest5336]

@@patronumtwok2891 very good point, I think you are correct. Is there an efficient way of writing pairwise GCDs? Or would each one need to be done individually? Thinking more for the n-dimensional case which would need all possible combinations of GCDs?

[@dmytrk]

@@oliverwest5336 def intersections_n(dimensions: tuple) -> int: dimensions = tuple([floor(dim) for dim in dimensions]) if (len(dimensions) == 0): return 0 if (len(dimensions) == 1): return dimensions[0] if len(dimensions) == 2: m, n = dimensions return m + n - gcd(m, n) last_dimension = dimensions[-1] prev_intersections = intersections_n(dimensions[:-1]) return prev_intersections + last_dimension - gcd(prev_intersections, last_dimension)

[@patronumtwok2891]

@@oliverwest5336 I don't think there is any good way to write the sums of GCDs of a set of numbers, best is I think with some good use of the sum symbol. I feel like this might be a case where the final solution may look something like inclusion exclusion but its just a hunch.

[@mathmaximum1647]

@@oliverwest5336it holds gcd(n,m,k) = gcd(gcd(n,m),k) = gcd(n,gcd(m,k)) = gcd(gcd(n,k),m)

[@mathmaximum1647]

can this be generalized to higher dimensions? For an n by m by k prism, we pass through n + m + k - gcd(n,m,k) smaller cubes? What about dim 4 ,5 , …? Nice video!

[@xizar0rg]

RIP Alexander Bogomolny.

[@xlorrix-6320]

in the limit does this formula approach a^2+b^2=c^2 where c is the number of squares?

[@minimath5882]

This makes me wonder how this work with hexagonal and triangular grids?

[@cicik57]

it is m+n if only the line goes not exactly into corner, so we need count amount of corners ,what is how many times the greatest common divisor inclusive 1, will repeat on the path , means m + n - gcd(m,n)-1 because the last corner will always be at the end for example for 6,4 the least common divisor is 2, so we divide on 2 and get the ´cycle´ of size 3,2 what will

[@padraiggluck2980]

The gradient is rise over run.

[@archangecamilien1879]

Perhaps if you determine a way to count the number of squares in any grid, lol, that might be useful...then find the number of squares in the whole grid, subtract the number of squares that are *not* touched by the line (whatever "touch" means, lol, does "tangent", "touches a corner" count?...At any rate, lol, didn't try anything, but it might be easier to count the number of squares that aren't touched by the grid, lol, whatever "touch" is supposed to mean, and then subtract them from the total number of squares...

[@vangrails]

This must be somehow related to Pick's theorem?

[@DrBarker]

It would be interesting to see if there's a way to solve this problem using Pick's theorem! I can see that the number of points on the boundary is relevant (m + n + gcd(m,n)?), and the area is always mn/2, but I can't see how to relate this to the number of squares on the diagonal - maybe the number of interior points can help.

[@hoangslen8416]

This problem i can't solve it on 3 years!

[@tmlen845]

the division into smallee rectangles seems unnecessary. when you see that gcd(m,n) is the number of times it will go trough a corner, it can simply be substracted from M+N+1, to cancel out that it only goes into one new square and not two

[@Amantheparadise]

I was expecting combintorial proof

[@9nr]

Can you please find perfect anti-aliasing algorithm? Basically, which shade of gray which pixels should be to make best perception of smooth slated line

[@alipourzand6499]

Neat! Seeing the solution dosn't mean anything. Math is about proofing things not solving them.

[@mrboombastic_69420]

I've found a simpler method tho, Basically if you have a rectangle of sides "a". "b" There will be 2 formulas Formula 1: If a {dependent side} is even (a/2)+b Formula 2: If a {dependent side} is odd. [(a+1)/2] +b I've figured out how this works but Idk how to properly explain it without a diagram. You can see for yourself that there are atleast "a" boxes in a rectangle of sides axb (Focus on one side say "a") The other side repeats itself exactly "b" times so boxes should have been a+b but we can also see that b goes up once when a goes forth twice, so b repeats itself only half the time, {This is the part where I explain what independent and dependent side is, simpley we can see that one side in the formula is being halved, and added into the other side which is not increased or decreased, I call the one being halved as dependent and other as independent, the other one is called independent because it controls the dependent side (not exactly but since we juts completey give a box to independent that was supposed to be shared between both of them, independent changes the intervals of b so it kinnda controls it in a way) , if we just look closely we can see the independent shares 1 square with the dependent one on each upward increment, and the formula gives this shared pice of box to the independent side, basically taking something away from dependent side on each step. (from each step I mean each time the graph displays 2 boxes together in a straight line) } The same can be said about a by taking b as independent, Now formula is different if our dependent side is odd, so we add one to make it even, divide by 2 and add into independent

[@HJ-gg6ju]

And if a=b?

[@jursamaj]

Your "simpler" method doesn't work. The correct formula is a+b-GCD(a,b). Your formulae are a+b-a/2 (approximately, since a may be odd). The GCD is not always approximately half of a or b, therefore your formulae will not work.