This problem is a fundamental illustration of mathematical induction, but it is still a bit tricky.
"tromino" is an L-shaped object consisting of three squares of the same size.
Consider a 2n X 2n square. If one of the smaller squares is removed from a corner of the large square, the the resulting region can be completely covered by trominos.
I will try to use Polya's method.
Understanding the problem
Known: the square (size, shape) need to be covered
Unknown: I must discover whether trominos can cover that square
Devising a plan
It seems a bit difficult at first glance, but I notice that the problem deals with a natural number n, so the idea of induction may help.
Proof
I carry out my plan using mathematical induction.
Base Case: when n = 1, the region after removal is exactly a tromino. So the theorem holds when n = 1
Induction Step: suppose when n = k, the theorem holds, so the 2^k X 2^k square region after removing the corner can be covered by trominos. Let me examine the 2^k+1 X 2^k+1 square. It should be like this:
Then we can put a tromino in the middle
And we can obverse the region can be divided into four 2^k X 2^k medium-sized regions as illustrated:
By induction hypothesis, those four regions can be covered by trominos, and the three small blank squares can be covered by one tromino, so the whole region can be covered by trominos as well. so the theorem holds for n = k + 1. By MI, we know the resulting region can always be covered by trominos.
Looking back
After looking back, we find that without a plan of using induction, it will be very difficult to come up with a good idea to strictly solve this problem. So it is a good idea to use Polya's method when solving tricky problems.
"tromino" is an L-shaped object consisting of three squares of the same size.
Consider a 2n X 2n square. If one of the smaller squares is removed from a corner of the large square, the the resulting region can be completely covered by trominos.
I will try to use Polya's method.
Understanding the problem
Known: the square (size, shape) need to be covered
Unknown: I must discover whether trominos can cover that square
Devising a plan
It seems a bit difficult at first glance, but I notice that the problem deals with a natural number n, so the idea of induction may help.
Proof
I carry out my plan using mathematical induction.
Base Case: when n = 1, the region after removal is exactly a tromino. So the theorem holds when n = 1
Induction Step: suppose when n = k, the theorem holds, so the 2^k X 2^k square region after removing the corner can be covered by trominos. Let me examine the 2^k+1 X 2^k+1 square. It should be like this:
Then we can put a tromino in the middle
And we can obverse the region can be divided into four 2^k X 2^k medium-sized regions as illustrated:
By induction hypothesis, those four regions can be covered by trominos, and the three small blank squares can be covered by one tromino, so the whole region can be covered by trominos as well. so the theorem holds for n = k + 1. By MI, we know the resulting region can always be covered by trominos.
Looking back
After looking back, we find that without a plan of using induction, it will be very difficult to come up with a good idea to strictly solve this problem. So it is a good idea to use Polya's method when solving tricky problems.
No comments:
Post a Comment