BdMO National 2012: Higher Secondary 09, Secondary 10

[Moon]

Problem:
A triomino is an $L$-shaped pattern made from three unit squares. A $2^k \times 2^k$ chessboard has one of its squares missing. Show that the remaining board can be covered with triominoes.

[Moon]

Induction, twice! One for obvious reason. Second (not really induction, but explicit construction) for proving that every L-shaped triomino like figure with with $2^k\times 2^k$ squares (in the place of the unit squares in normal triomino) can be covered just using triominos.

[*Mahi*]

ক্লাসিক এবং সোজা!

[sm.joty]

ক্লাসিক এবং সোজা!

ক্লাসিক কিন্তু সোজা না। আমি ৩ বার করে জিজ্ঞেস করলাম ত্রিমিনো গুলা shuffle করা যাবে কিনা। কোন ভাইয়াই এইটা বুঝাইতে পারল না। কাজেই ৩ দ্বারা বিভাজ্য প্রমান করেই শেষ আর করতে পারি নাই।

[*Mahi*]

ক্লাসিক এবং সোজা!

ক্লাসিক কিন্তু সোজা না। আমি ৩ বার করে জিজ্ঞেস করলাম ত্রিমিনো গুলা shuffle করা যাবে কিনা। কোন ভাইয়াই এইটা বুঝাইতে পারল না। কাজেই ৩ দ্বারা বিভাজ্য প্রমান করেই শেষ আর করতে পারি নাই।

সল্যুশন দেখলে কান্না পাবে

[nafistiham]

আমি ইংলিশ অংশ টা পড়িনি । তাই, unit square এর জন্য প্রমান করার পরও যেকোনো sqaureএর জন্য প্রমান করে রেখে দিছি ।
প্রমানঃ

firstly, let us prove that if the missing square is at the corner, what happens...the $2\times 2$ square it is situated in is nothing but a trimino.let us take a trimino at it's corner so, the rest part is three triminos.because, we have taken the three unit squares from three $2\times 2$ squares.so, this $4\times 4$ is filled with triminos.the base case is complete.let us think about the surrounding three $4\times 4$ now we can take a trimino using three unit squares from these three $4\times 4$ squares like the base case the rest of them will be filled with triminos.by induction we can prove that for any $2^k\times 2^k$ square.where the corner square is missing.

let us now prove that in any $2^k \times 2^k$ square the missing square can be moved to the corner.
we can divide the square in $4$ parts any of them consists the missing piece.we can rotate it to make the missing piece at the corner as much as possible.if it is not at the corner.we can divide it in $4$ parts again and again and rotate again and again.

no matter how much change we do, the first part does not change.so it is done i think.

[nafistiham]

In the contest, I proved the base case.but, after that, i simply said that, if we take out the $4\times 4$ square there will be left out a trimino of $4\times 4$ squares in the $8 \times 8$ square .then again by taking out the $8 \times 8$ sqaure there will be a bigger trimino and induction like that.
because, in the bangla problem there was just said a trimino is made of 'তিনটি বর্গ' not, 'তিনটি একক বর্গ'

[sm.joty]

ক্লাসিক এবং সোজা!

ক্লাসিক কিন্তু সোজা না। আমি ৩ বার করে জিজ্ঞেস করলাম ত্রিমিনো গুলা shuffle করা যাবে কিনা। কোন ভাইয়াই এইটা বুঝাইতে পারল না। কাজেই ৩ দ্বারা বিভাজ্য প্রমান করেই শেষ আর করতে পারি নাই।

সল্যুশন দেখলে কান্না পাবে

আমার তো সলিউসন না দেখেই কান্না পাইতেসে...

কিন্তু সলিউসন কই ?????

[nafistiham]

ক্লাসিক কিন্তু সোজা না। আমি ৩ বার করে জিজ্ঞেস করলাম ত্রিমিনো গুলা shuffle করা যাবে কিনা। কোন ভাইয়াই এইটা বুঝাইতে পারল না। কাজেই ৩ দ্বারা বিভাজ্য প্রমান করেই শেষ আর করতে পারি নাই।

সল্যুশন দেখলে কান্না পাবে

আমার তো সলিউসন না দেখেই কান্না পাইতেসে...

কিন্তু সলিউসন কই ?????

ভাইয়া, আমার সমাধানটা দেখতে পার । সম্ভবতঃ হয়েছে । ভুল থাকলে বোলো ।

[Tahmid Hasan]

here's my solution
it is trivial for $k=1$
let us assume that the statement holds for $k=n$,let us also assume that there is such a permutation that the 'blank' square lies on the edge.(ফাঁকা বর্গটা যেন কোণায় থাকে)
now for $k=n+1$,we take $4$ chessboards of $2^n*2^n$ such that after joining them they form a $2^{n+1}*2^{n+1}$ square for which $3$ blank squares are in the middle and the other is at the edge.
now we can cover the $3$ three blank squares with a trimino.
thus our assumption(the additional one too) holds for $k=n+1$
so by mathematical induction it holds for all natural $k$.