even odd even odd

For discussing Olympiad Level Combinatorics problems
User avatar
asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm
Location: Sylhet,Bangladesh

even odd even odd

Unread post by asif e elahi » Tue May 31, 2016 5:04 pm

A $2015\times 2015$ grid is coloured like a chessboard so that the four corner squres are coloured black. We put pebbles in some of the cells so that every row and column contains an odd number of cells with pebbles. Prove that there are an even number of white cells with pebbles.

Golam Musabbir Joy
Posts: 11
Joined: Tue Jun 16, 2015 5:11 am
Location: Barisal, Bangladesh

Re: even odd even odd

Unread post by Golam Musabbir Joy » Mon Aug 08, 2016 12:19 am

Can any row or column be empty?

User avatar
asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm
Location: Sylhet,Bangladesh

Re: even odd even odd

Unread post by asif e elahi » Mon Aug 08, 2016 1:10 am

Golam Musabbir Joy wrote:Can any row or column be empty?
No, as $0$ is an even number.

Nayeemul Islam Swad
Posts: 22
Joined: Sat Dec 14, 2013 3:28 pm

Re: even odd even odd

Unread post by Nayeemul Islam Swad » Mon Aug 08, 2016 5:30 pm

Hint:
Let $x_i$ and $y_j$ be the rows and columns, respectively, $1 \leq x_i,y_j \leq 2015$. Let $S$ be the set of the squares containing pebble. Then what is the parity of $\sum_{(x_i,y_j)\in S}x_i + y_i?$
Why so SERIOUS?!??!

User avatar
asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm
Location: Sylhet,Bangladesh

Re: even odd even odd

Unread post by asif e elahi » Tue Aug 09, 2016 10:55 am

Nayeemul Islam Swad wrote:Hint:
Let $x_i$ and $y_j$ be the rows and columns, respectively, $1 \leq x_i,y_j \leq 2015$. Let $S$ be the set of the squares containing pebble. Then what is the parity of $\sum_{(x_i,y_j)\in S}x_i + y_i?$
I don't see how to use this hint. Write your whole solution please.

Nayeemul Islam Swad
Posts: 22
Joined: Sat Dec 14, 2013 3:28 pm

Re: even odd even odd

Unread post by Nayeemul Islam Swad » Tue Aug 09, 2016 1:38 pm

Solution:
I think my notation isn't clear. I meant when considering only values, $x_i = y_i = i$. But when I say $x_i$, I am refering to the row no. of the $i$'th row, not the column no. of the $i$'th column.
Now let $\sum_{(x_i,y_j)\in S}x_i+y_j = N$
We'll show $N$ is even.
First set $N = 0.$
Then go through all the rows and for each row $x_i$, for any pebble-square in that row $(x_i, y_j)\in S$, just add $x_i = i$ to the sum.
Then after continuing the process for all rows, we have $N = 1\times \text{odd} + 2\times \text{odd} +\dots+2015\times \text{odd}$ as there are odd number of pebbles in each row.
Again after going through all the colums we have,
$N = 1\times (\text{odd}+\text{odd}) + 2\times (\text{odd}+\text{odd}) +\dots$
$+2015\times(\text{odd}+\text{odd})$
$=$ something even.
Now let's count it in a different way.
Let, $N_B = \sum_{(x_i,y_j)\in S \text{ and } (x_i,y_j) \text{ is black}}x_i+y_j.$ Similarly $N_W = \sum_{(x_i,y_j)\in S \text{ and } (x_i,y_j) \text{ is white}}x_i+y_j.$
So, $N = N_B + N_W$
Notice that, $x_i+y_j$ is odd if $(x_i,y_j)$ is white and even in case of black.
So, each 'pair-sum' in $N_B$ is even
$\rightarrow N_B$ is even
$\rightarrow N_W$ must be even too
But as each 'pair-sum' in $N_W$ is odd, number of pairs in $N_W$ have to be even ie. number of white squares $\in S$ is even.
Why so SERIOUS?!??!

User avatar
asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm
Location: Sylhet,Bangladesh

Re: even odd even odd

Unread post by asif e elahi » Tue Aug 09, 2016 4:27 pm

Nayeemul Islam Swad wrote:Solution:
I think my notation isn't clear. I meant when considering only values, $x_i = y_i = i$. But when I say $x_i$, I am refering to the row no. of the $i$'th row, not the column no. of the $i$'th column.
Now let $\sum_{(x_i,y_j)\in S}x_i+y_j = N$
We'll show $N$ is even.
First set $N = 0.$
Then go through all the rows and for each row $x_i$, for any pebble-square in that row $(x_i, y_j)\in S$, just add $x_i = i$ to the sum.
Then after continuing the process for all rows, we have $N = 1\times \text{odd} + 2\times \text{odd} +\dots+2015\times \text{odd}$ as there are odd number of pebbles in each row.
Again after going through all the colums we have,
$N = 1\times (\text{odd}+\text{odd}) + 2\times (\text{odd}+\text{odd}) +\dots$
$+2015\times(\text{odd}+\text{odd})$
$=$ something even.
Now let's count it in a different way.
Let, $N_B = \sum_{(x_i,y_j)\in S \text{ and } (x_i,y_j) \text{ is black}}x_i+y_j.$ Similarly $N_W = \sum_{(x_i,y_j)\in S \text{ and } (x_i,y_j) \text{ is white}}x_i+y_j.$
So, $N = N_B + N_W$
Notice that, $x_i+y_j$ is odd if $(x_i,y_j)$ is white and even in case of black.
So, each 'pair-sum' in $N_B$ is even
$\rightarrow N_B$ is even
$\rightarrow N_W$ must be even too
But as each 'pair-sum' in $N_W$ is odd, number of pairs in $N_W$ have to be even ie. number of white squares $\in S$ is even.
oka
There is an easier solution. Just take the $1,3,5,\dots 2015th$ rows and $1,3,5\dots 2015th$ columns and prove that the number of squares with pebbles i these rows and columns is even. White squares are counted once and all the black squares are counted twice. The conclusion follows.

I used this idea to solve $IMO$ $2016$ $P2$ in the contest. 8-)

Nayeemul Islam Swad
Posts: 22
Joined: Sat Dec 14, 2013 3:28 pm

Re: even odd even odd

Unread post by Nayeemul Islam Swad » Tue Aug 09, 2016 6:05 pm

Nice solu joss application
^ Little typo which might confuse others...
"Black squares are counted twice and all the white squares are counted once."
Why so SERIOUS?!??!

Post Reply