We have a $2\times n$ rectangle. We call each $1\times1$ square a room and we show the room in the $i^{th}$ row and $j^{th}$ column as $(i,j)$. There are some coins in some rooms of the rectangle. If there exist more than $1$ coin in each room, we can delete $2$ coins from it and add $1$ coin to its right adjacent room OR we can delete $2$ coins from it and add $1$ coin to its up adjacent room. Prove that there exists a finite configuration of allowable operations such that we can put a coin in the room $(1,n)$.
Problem
Source:
Tags: induction, combinatorics proposed, combinatorics
sororak
21.09.2010 21:13
mahanmath wrote: Thanks Soroush for submit Iran`s problems . You're welcome! It was my duty
iman007
13.01.2021 02:28
we are going to approach this problem inductively, so we apply induction on $n$ for n=2 the problem is trivial so we consider that the problem is true for $n=k$ and then prove that it is true for $k+1$. we actualy should prove that there goes at least $2$ coins in the room either $(2,k+1)$ or $(1,k)$. first consider that there is no point in the room $(2,k+1)$ then the problem is trivial since we have $2^{k+1}$ coins and we can reach $2$ points at $(1,k)$. now we consider that there is exactly one coin in $(2,k+1)$ and the rest $2^{k+1}-1$ coins are on the rest of the table.by pigeonhole principle we have $2^{k-1}$ on the first row or on the second row then it can easily be shown that we can reach two coins on $(1,k)$ or we can reach two coins at $(2,k+1)$ which finishes the proof
AgentC
14.01.2024 14:32
iman007 wrote: now we consider that there is exactly one coin in $(2,k+1)$ and the rest $2^{k+1}-1$ coins are on the rest of the table.by pigeonhole principle we have $2^{k-1}$ on the first row or on the second row then it can easily be shown that we can reach two coins on $(1,k)$ or we can reach two coins at $(2,k+1)$ which finishes the proof Hello, shouldn't it be $2^{k}$ ? since $2^{k+1}-1$ > $2$ x ($2^{k} -1$)