How Many Squares Does the Diagonal Cross ? Edited

I have done a question like this before.

For any sized room with side lengths $m$ and $n$ , the number of tiles(T) that are crossed from the diagonal can be shown by the formula:

$m + n - HCF(m, n) = T$

Substituting the values and simplifying, we get

$A = 32 + 48 - HCF(32, 48)$

$A = 64$

$B = 32 + 47 - HCF(32, 47)$

$B = 78$

$C = 32 + 46 - HCF(32, 46)$

$C = 76$

Adding these up, we get

$64 + 78 + 76 = 218$

218 is the answer.

In a $p \times q$ rectangle where $\gcd(p,q)$ = 1, your journey through tiles can be represented as a string of Us and Rs (U means you cross up, R means you cross right). There will be $p-1$ Rs and $q-1$ Us, to move over $p$ and up $q$ so starting with the first tile you pass through $1 + (p-1) + (q-1) = p+q-1$ tiles.

${m \over \gcd(m,n)} \mbox{ and } {n \over \gcd(m,n)}$ are relatively prime, so imagine $gcd(m,n)$ blocks of this size across the diagonal of the room. Each block meets the next at a multiple of $\left( {m \over \gcd(m,n)}, {n \over \gcd(m,n)} \right)$ , a corner of a tile where you move up and right without entering any tile not counted in a path through a block. So there are $\gcd(m, n) \left( {m \over \gcd(m,n)} +{n \over \gcd(m,n)}-1 \right) = m + n - \gcd(m, n)$ tiles crossed by a $m \times n$ path.

Interesting as a computational geometry problem. Mind you, this solution is only brute force and could be radically improved upon.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from itertools import product
from fractions import Fraction

def crossedTiles(size=(6,9)):
    slope=Fraction(size[0],size[1])
    lattice=product(range(1+size[1]),range(1+size[0]))
    above=[]
    below=[]
    for point in lattice:
        if point[1]>Fraction(point[0]*slope):
            above.append(point)
        if point[1]<Fraction(point[0]*slope):
            below.append(point)
    count=0
    for a in above:
        for b in below:
            if a[0]+1==b[0] and a[1]-1==b[1]:
                count+=1
    return count

print crossedTiles((32,48))+crossedTiles((32,47))+crossedTiles((32,46))

Here are some convention I used to solve the problem

I used ! for multiplication, as I was unable to use the star symbol *

[x] - greatest integer >=x

{x} - least integer <=x

Approach: For a square of mXn. I am trying to check how many squares the diagnal crossed for every unit of n.

Lets take the figure 4X6 described in the question m=4, n=6

Assume x axis along the line of 'n'. and Y axis over line m. and bottom left corner to be origin.

For every unit increment in x, y increases by m/n(=4/6)

For x -> 0 to 1 y -> 0 to 4/6

No of squares crossed by diagnal in band x -> 0 to 1 = 1 = {4/6} - [0]

For x -> 1 to 2 y -> 4/6 to 2!4/6

No of squares crossed by diagnal in band x -> 1 to 2 = 2 = {2!4/6} - [4/3]

For x -> 2 to 3 y -> 2!4/6 to 3!4/6

No of squares crossed by diagnal in band x -> 2 to 3 = 1 = {3!4/6} - [2!4/3] ...

Generalizing for mXn square

b=m/n

no of squares crossed in band n from a to a+1 , a is integer and a<n-1 == {(a+1)b}-[ab]

So total no of squares crossed = ({b}+{2b}+....+{nb}) - ([b]+[2b]+....+[(n-1)b])

Now for 32X48 m=32, n=48,b=32/48

No of squares crossed = ({32/48}+{2!32/48}+...+{48!32/48}) - ([32/48]+[2!32/48]+....+[47!32/48]) = (1+2+2+3+4+4+.....+31+32+32) (0+1+2+2+3+4+4+.....+30+30+31) =64

You can find the pattern above, all the even numbers are repeated twice wheareas all the odd numbers occur only once

Similarly you can find such pattern for 32X46 and 32X47 and solve them to be 76 and 78 respectively

So the answer is 64+76+78 = 218

Please let me know if my presentation is not good enough to convey my thoughts....