Tiling a Triangular Grid

Question

Design and explain a recursive divide-and-conquer algorithm. Anyone has ideas?

Given an isosceles right triangular grid for some k ≥ 2 as shown in Figure 1(b), this problem asks you to completely cover it using the tiles given in Figure 1(a). The bottom-left corner of the grid must not be covered. No two tiles can overlap and all tiles must remain completely inside the given triangular grid. You must use all four types of tiles shown in Figure 1(a), and no tile type can be used to cover more than 40% of the total grid area. You are allowed to rotate the tiles, as needed, before putting them on the grid.

Answer 1

This is the idea of induction indeed, and is similar to the famous example "L-Tile" covering

As you said, you have solved the problem for k = 2, it's a good and correct starting point to solve small example first, yet I think this problem there is a bit tricky for k = 2 case, mainly due to the each type cannot exceed 40% constrain.

Then for k>2, say k = 3 in your example, we try to make use of what you have solved, i.e. the case k = 2

With very simple observation, one may notice that for k = n, it can actually be made up of 4 k=n-1 cases (see image below)

Now the shaded part in the middle form a hole that can filled by 1 type B, so we can first filled the 4 small n-1 case and fill the hole with type B...

But then this construction face a problem: type B will exceed 40% of the area!

Consider k = 2, no matter how you fill the area, 2 type B must be used, I do not have a strong proof but by some brute force trail & error you should be convinced. Then for k = 3, we have 4 small triangles meaning we have 2*4 = 8 Type B, plus 1 more to fill the hole will gives us 9 Type B, each uses 1.5 sq units, which total uses up 13.5 sq units.

As k = 3, the total area is (2^3)^2 / 2 = 32 sq units 13.5/32 = 0.42.... which violate the constrain!

So what to do? Here is the reason why we have to use a trick to handle the k = 2 case (I assume you have go through this part as you said you know how to do k = 2 case)

First, we know that using our constructive method to build a large triangle from 4 smaller triangles, only Type B will violate this constrain (i.e. the 40% area), you can verify yourself. So we want to reduce the total number of Type B used, yet each smaller triangle must use at least 2 Type B, so the only place we may reduce is the empty hole in the middle of the large triangle, can we use other Type instead of Type B? At the same time, we want the other parts of the small triangle remain unchanged so that we can use same argument to do an induction (i.e. in general speaking, form 2^n triangle from 4 2^(n-1) triangles using same construction method)

The answer is YES if we special design the k = 2 case See my construction below: (There maybe other construction works too, but I only need to know one)

The trick is I intentionally move 1 Type B next to the empty(gray) triangle Let's stop right here for a bit, and do some verification:

To construct a k = 2 case, we use

• 2 Type A = 2 sq.units < 40%
• 2 Type B = 3 sq.units < 40%
• 1 Type C = 1.5 sq.units < 40%
• 1 Type D = 1 sq.unit < 40%

Total use 7.5 sq.units, good

Now imagine we use exactly the same method to construct those 4 triangles to make a large one, the middle one still be an empty hole with shape of Type B, but now instead of filling it with 1 Type B, we fill the hole TOGETHER WITH the 3 Type B just next to them (look back the k = 2 case), using Type A & D (I use same color scheme as above for easy understanding), we do this for all 3 small triangles which made up the hole in the middle.

Here is the last part (I know it's long...) We have reduce the number of Type B used when constructing a large triangle from smaller ones, but at the same time we increase the number of Type A & D used! So is this new construction method valid?

First notice that it does not change any parts of the small triangles except the Type B next to the gray triangle, i.e. If the 40% constrain is fulfilled, this method is inductive and recursive to fill a 2^n side triangle

Then let's count again the number of each Type we used.

For k = 3, total units is 32, we uses:

• 2*4+3 = 11 Type A = 11 sq.units < 40%
• 2*4-3 = 5 Type B = 7.5 sq.units < 40%
• 1*4 = 4 Type C = 6 sq.units < 40%
• 1*4+3 = 7 Type D = 7 sq.unit < 40%

Total we cover 31.5 units, good, now let's proof the 40% constrain is satisfied for k = n > 3

Let FA(n-1) be the total area of Type A used to fill 2^n-1 triangles using our new method, likewise, FB(n-1), FC(n-1), FD(n-1) with similar definitions

Assume F*(n-1) is true, i.e. not exceeding 40% of total area, we proof that F*(n) is true.

We got

FA(n) = FA(n-1)*4 + 3*1

FB(n) = FB(n-1)*4 - 3*1.5

FC(n) = FC(n-1)*4

FD(n) = FD(n-1)*4 + 3*1

We only show the proof for FD(n), other three should be proofed with similar method (M.I.)

Using method of substitution, FD(n) = 2*(4^(n-2)) - 1 for n>=3 (You should at least try to come up with this equation yourself)

We want to show FD(n)/(2^2(n)/2) < 0.4

i.e. 2FD(n)/4^n < 0.4

Consider LHS,

LHS = (4*(4^(n-2)) - 2)/4^n

< 4^(n-1)/4^n = 1/4 < 0.4 Q.E.D

That means using this method, all Type A-D will not exceed 40% of total area for any 2^k sided triangle, for k >= 3, finally we show that inductively, there is a method satisfy all constrains to construct such a triangle.

TL;DR

1. The hard part is to satisfy the 40% area constrain
2. Use a special construction on k = 2 case first, try to use it to build k = 3 case (then k = 4, k = 5...idea of induction!)
3. When using k=n-1 case to build k=n case, write down the formula of total area consumed by each type, and show that they would not exceed 40% of total areas
4. Combined point 2 & 3, it's an induction method to show that for any k >= 2, there is a method (which we described) to fill the 2^k sided triangle without breaking any constrains