Cracking Tiles

GEK1517 Tutorial Three / Question Two: Suppose that there are m×n unit square tiles arranged into a rectangle (a square if m=n; here m and n are positive integers). A crack appears as a diagonal line of the rectangle (see the figure for m=3 and n=5. Speculate on the number of tiles that are ruined and need to be replaced. (Your answers should be in terms of m and n). Provide arguments to support your answers.


Step I: Panic

Step II: After calming down, try the shit out of as many lower values of m and n you could be bothered with.


Assume that the number of tiles follow a rule; nail the rule down to a symbol.
Number of tiles damaged = D(m,n)

Make the following observations which may or may not come useful later on.

m and n are interchangeable.

Extreme case I: Thin rectangle

Extreme case II: Square

After a bit of trying, arrive at the formula
D(m,n) = m + n - 1
which works for the largest number of the cases (including Extreme I cases)
Group cases according to how well they conform to D = m + n - 1 (mirror images are ruled out as trivial)


It should be very clear now what differentiates the two groups.
The left group ("conformist" rectangles) have cracked tiles of continguous shape. The cracks do not pass through a point in between tiles.
The right group ("nonconformist" rectangles) have cracks that pass through a point (or points).
Somehow, passing through a point affects the crack count!

For curiosity's sake, have a closer look at the nonconformist group.


The nonconforming rectangles do not follow a single rule! Evidently, something has to be found out about this group that dictates the D(m,n).

Step III: Observe that every crack starts and ends on a point.

Observe that, if the crack passes through a point in a middle of a rectangle, you can break a smaller rectangle from it with that middle point as a new (top-right or bottom-left) corner. We take bottom-left:


Observe that, if the new rectangle also has the crack passing through a point between tiles, the process can be repeated until there is no point.


A rectangle where the crack does not pass through a point is a conformist rectangle.
We have demonstrated that a nonconformist rectangle can be reduced to a conformist rectangle.

How do you get back the nonconformist rectangle?
Every conformist rectangle, a series of nonconformist rectangles can be constructed by replicating the conformist x times along the crack's diagonal:


What is the D for a rectangle of length xm and height xn?
It is quite clear that this quantity D for a nonconformist rectangle can be taken apart into the sum of cracks for x conformist rectangles.


We arrive at
D(xm,xn) = xD(m,n)
for nonconformists, where D(m,n) is of a conformist rectangle
Which, owing to D(m,n) = m + n - 1, becomes
D(xm,xn) = xD(m,n) = x(m + n - 1) = xm + xn - x

Step IV:
Observe that in nonconformist rectangles (D(xm,xn) = xm + xn - x) width and height have a common factor x
Observe that in conformist rectangles (D(m,n) = m + n - 1) the width and height have no common factors other than 1.
Observe that D(m,n) = m + n - 1 is equivalent to D(1m,1n) = 1m + 1n - 1, which is just a special case for the nonconformists' rule (x = 1).
Observe that x is the highest common factor (h.c.f) between the width xm and height xn; since m and n have no common factors, the common factors include x and possibly a number smaller than x which is also a factor of x (x is still the highest).

Obtain the unified rule for all rectangles of width m and height n:
D(m,n) = m + n - (h.c.f of m and n)
Verify that rule applies to all cases presented above.

--END OF DEMONSTRATION--

Addendum: Ruohan's description of a proof
Set A {(a, an/m), where 0 ≤ a < m}.
Set B {(bm/n, b), where 0 ≤ b < n}.
Each point in A and B correspond to a cracked tile to the right of the point itself. The answer would then be A ∪ B = A + B - (A ∩ B).
Solving A ∩ B would then be solving the integer pairs for an = bm.

Lacuna: I asserted that a nonconformist rectangle be formed by duplicating the same conformist along the crack. I did not explain why a different conformist can not be used. To do so, I may slip into a circular argument.

Spoiler: Lecturer touched on how to count the cracked tiles, and did not arrive at the expression m + n - 1 by accident like I did.