BdMO National 2012: Higher Secondary 09, Secondary 10

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

BdMO National 2012: Higher Secondary 09, Secondary 10

Unread post by Moon » Sat Feb 11, 2012 11:23 pm

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.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

Re: BdMO National 2012: Higher Secondary 09, Secondary 10

Unread post by Moon » Sun Feb 12, 2012 9:07 am

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.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: BdMO National 2012: Higher Secondary 09, Secondary 10

Unread post by *Mahi* » Sun Feb 12, 2012 2:09 pm

ক্লাসিক এবং সোজা!
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
sm.joty
Posts: 327
Joined: Thu Aug 18, 2011 12:42 am
Location: Dhaka

Re: BdMO National 2012: Higher Secondary 09, Secondary 10

Unread post by sm.joty » Sun Feb 12, 2012 11:05 pm

*Mahi* wrote:ক্লাসিক এবং সোজা!
ক্লাসিক কিন্তু সোজা না। আমি ৩ বার করে জিজ্ঞেস করলাম ত্রিমিনো গুলা shuffle করা যাবে কিনা। কোন ভাইয়াই এইটা বুঝাইতে পারল না। কাজেই ৩ দ্বারা বিভাজ্য প্রমান করেই শেষ আর করতে পারি নাই। :cry:
হার জিত চিরদিন থাকবেই
তবুও এগিয়ে যেতে হবে.........
বাধা-বিঘ্ন না পেরিয়ে
বড় হয়েছে কে কবে.........

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: BdMO National 2012: Higher Secondary 09, Secondary 10

Unread post by *Mahi* » Mon Feb 13, 2012 12:05 pm

sm.joty wrote:
*Mahi* wrote:ক্লাসিক এবং সোজা!
ক্লাসিক কিন্তু সোজা না। আমি ৩ বার করে জিজ্ঞেস করলাম ত্রিমিনো গুলা shuffle করা যাবে কিনা। কোন ভাইয়াই এইটা বুঝাইতে পারল না। কাজেই ৩ দ্বারা বিভাজ্য প্রমান করেই শেষ আর করতে পারি নাই। :cry:
সল্যুশন দেখলে কান্না পাবে ;)
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
nafistiham
Posts: 829
Joined: Mon Oct 17, 2011 3:56 pm
Location: 24.758613,90.400161
Contact:

Re: BdMO National 2012: Higher Secondary 09, Secondary 10

Unread post by nafistiham » Mon Feb 13, 2012 3:54 pm

আমি ইংলিশ অংশ টা পড়িনি । তাই, 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.
\[\sum_{k=0}^{n-1}e^{\frac{2 \pi i k}{n}}=0\]
Using $L^AT_EX$ and following the rules of the forum are very easy but really important, too.Please co-operate.
Introduction:
Nafis Tiham
CSE Dept. SUST -HSC 14'
http://www.facebook.com/nafistiham
nafistiham@gmail

User avatar
nafistiham
Posts: 829
Joined: Mon Oct 17, 2011 3:56 pm
Location: 24.758613,90.400161
Contact:

Re: BdMO National 2012: Higher Secondary 09, Secondary 10

Unread post by nafistiham » Wed Feb 15, 2012 6:51 pm

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, 'তিনটি একক বর্গ'
Last edited by Masum on Fri Feb 24, 2012 11:11 pm, edited 1 time in total.
Reason: You can't ask for your marks, at least here.
\[\sum_{k=0}^{n-1}e^{\frac{2 \pi i k}{n}}=0\]
Using $L^AT_EX$ and following the rules of the forum are very easy but really important, too.Please co-operate.
Introduction:
Nafis Tiham
CSE Dept. SUST -HSC 14'
http://www.facebook.com/nafistiham
nafistiham@gmail

User avatar
sm.joty
Posts: 327
Joined: Thu Aug 18, 2011 12:42 am
Location: Dhaka

Re: BdMO National 2012: Higher Secondary 09, Secondary 10

Unread post by sm.joty » Tue Feb 21, 2012 12:01 am

*Mahi* wrote:
sm.joty wrote:
*Mahi* wrote:ক্লাসিক এবং সোজা!
ক্লাসিক কিন্তু সোজা না। আমি ৩ বার করে জিজ্ঞেস করলাম ত্রিমিনো গুলা shuffle করা যাবে কিনা। কোন ভাইয়াই এইটা বুঝাইতে পারল না। কাজেই ৩ দ্বারা বিভাজ্য প্রমান করেই শেষ আর করতে পারি নাই। :cry:
সল্যুশন দেখলে কান্না পাবে ;)
আমার তো সলিউসন না দেখেই কান্না পাইতেসে... :cry:

কিন্তু সলিউসন কই ????? :?:
হার জিত চিরদিন থাকবেই
তবুও এগিয়ে যেতে হবে.........
বাধা-বিঘ্ন না পেরিয়ে
বড় হয়েছে কে কবে.........

User avatar
nafistiham
Posts: 829
Joined: Mon Oct 17, 2011 3:56 pm
Location: 24.758613,90.400161
Contact:

Re: BdMO National 2012: Higher Secondary 09, Secondary 10

Unread post by nafistiham » Tue Feb 21, 2012 2:30 pm

sm.joty wrote:
*Mahi* wrote:
sm.joty wrote: ক্লাসিক কিন্তু সোজা না। আমি ৩ বার করে জিজ্ঞেস করলাম ত্রিমিনো গুলা shuffle করা যাবে কিনা। কোন ভাইয়াই এইটা বুঝাইতে পারল না। কাজেই ৩ দ্বারা বিভাজ্য প্রমান করেই শেষ আর করতে পারি নাই। :cry:
সল্যুশন দেখলে কান্না পাবে ;)
আমার তো সলিউসন না দেখেই কান্না পাইতেসে... :cry:

কিন্তু সলিউসন কই ????? :?:
ভাইয়া, আমার সমাধানটা দেখতে পার । সম্ভবতঃ হয়েছে । ভুল থাকলে বোলো ।
\[\sum_{k=0}^{n-1}e^{\frac{2 \pi i k}{n}}=0\]
Using $L^AT_EX$ and following the rules of the forum are very easy but really important, too.Please co-operate.
Introduction:
Nafis Tiham
CSE Dept. SUST -HSC 14'
http://www.facebook.com/nafistiham
nafistiham@gmail

User avatar
Tahmid Hasan
Posts: 665
Joined: Thu Dec 09, 2010 5:34 pm
Location: Khulna,Bangladesh.

Re: BdMO National 2012: Higher Secondary 09, Secondary 10

Unread post by Tahmid Hasan » Wed Feb 22, 2012 2:03 pm

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$. :)
বড় ভালবাসি তোমায়,মা

Post Reply