On n x n board, 2n-1 fields were chosen. Prove that you can paint some of the chosen (not zero) fields green so that
a) in every line and every column, number of green fields is odd
b) in every line and every column, number of green fields is even
n x n board
-
nafistiham
- Posts:829
- Joined:Mon Oct 17, 2011 3:56 pm
- Location:24.758613,90.400161
- Contact:
Re: n x n board
Are the 'chosen' squares defined ?
I mean am I going to 'choose' ? Or it has already been 'chosen' ?
If I don't know what they are, how can I paint them ?
I mean am I going to 'choose' ? Or it has already been 'chosen' ?
If I don't know what they are, how can I paint them ?
\[\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.
Using $L^AT_EX$ and following the rules of the forum are very easy but really important, too.Please co-operate.
Re: n x n board
You don't know what they are. They are randomly chosen 2n-1 fields and I have to prove that no matter which 2n-1 points were chosen I can always paint more than zero of them which satisfy a) and b).
-
nafistiham
- Posts:829
- Joined:Mon Oct 17, 2011 3:56 pm
- Location:24.758613,90.400161
- Contact:
Re: n x n board
suppose the randomly chosen $2n-1$ squares of a $4x4$ squares are in the corner most $3x3$ square. which means, a row and a column don't have any chosen square.
now let us paint.
If we paint more than $0$ squares among those chosen ones, one row and one column remains greenless.
so, is that possible ?
'either, i am going wrong in understanding, or there is something fishy about the problem'
now let us paint.
If we paint more than $0$ squares among those chosen ones, one row and one column remains greenless.
so, is that possible ?
'either, i am going wrong in understanding, or there is something fishy about the problem'
\[\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.
Using $L^AT_EX$ and following the rules of the forum are very easy but really important, too.Please co-operate.
Re: n x n board
Oh, my mistake. It satisfies EITHER a) or b).
-
nafistiham
- Posts:829
- Joined:Mon Oct 17, 2011 3:56 pm
- Location:24.758613,90.400161
- Contact:
Re: n x n board
Ok, now it has got a shape. But, till it is tricky.I haven't solved it yet(don't know will be even able or not 
).
But, got this outline.
in all the cases where there is any row or column is missing a chosen square, means that we must prove the even case. just, manage to put $4$ green squares in $2$ rows and $2$ columns. As, any green square is shared by a row and a column.
Even if every row and column has at least a chosen square, we can try to prove to make it the even one. And, that's easier.
[gonn'a share as soon as I get the solution ]
).But, got this outline.
in all the cases where there is any row or column is missing a chosen square, means that we must prove the even case. just, manage to put $4$ green squares in $2$ rows and $2$ columns. As, any green square is shared by a row and a column.
Even if every row and column has at least a chosen square, we can try to prove to make it the even one. And, that's easier.
[gonn'a share as soon as I get the solution
]\[\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.
Using $L^AT_EX$ and following the rules of the forum are very easy but really important, too.Please co-operate.
-
sakibtanvir
- Posts:188
- Joined:Mon Jan 09, 2012 6:52 pm
- Location:24.4333°N 90.7833°E
Re: n x n board
Okay,Draw a $n \times n$ board where $n$ is even. Now choose all the fields of the leftmost column and the bottom-most row.So, $2n-1$ fields are chosen.Now however You paint them green, it satisfies neither $(a)$ nor $(b)$.If it really happens,then problem becomes a fallacy. 
An amount of certain opposition is a great help to a man.Kites rise against,not with,the wind.
Re: n x n board
sakibtanvir, in your case, just paint every field apart from the left-bottom corner. Then in every row and every column you have odd number of green fields.
-
sakibtanvir
- Posts:188
- Joined:Mon Jan 09, 2012 6:52 pm
- Location:24.4333°N 90.7833°E
Re: n x n board
Sorry,but how??? 
.Check if I am misunderstanding.
If you just paint the field of the left bottom corner, the others have no green field at all or having 0(even) greens.
.Check if I am misunderstanding.If you just paint the field of the left bottom corner, the others have no green field at all or having 0(even) greens.
An amount of certain opposition is a great help to a man.Kites rise against,not with,the wind.
Re: n x n board
So in the left column you have n-1 green fields, in the bottom line you have n-1 green fields (where n is even, so n-1 is odd) and in other columns and lines you have 1 green field, which is also an odd number.Marina19 wrote:sakibtanvir, in your case, just paint every field apart from the left-bottom corner. Then in every row and every column you have odd number of green fields.