Given a table $m\times n$, in each cell of which a number $+1$ or $-1$ is written. It is known that initially exactly one $-1$ is in the table, all the other numbers being $+1$. During a move, it is allowed to chose any cell containing $-1$, replace this $-1$ by $0$, and simultaneously multiply all the numbers in the neighbouring cells by $-1$ (we say that two cells are neighbouring if they have a common side). Find all $(m,n)$ for which using such moves one can obtain the table containing zeros only, regardless of the cell in which the initial $-1$ stands.
Problem
Source: Baltic Way 2004, problem 11
Tags: algorithm, combinatorics unsolved, combinatorics
Myth
18.12.2004 18:50
I used chessboard coloring + calculations modulo 4 to show that we cannot elliminate all numbers in case $2\,|\,n$, $2\,|\,m$.
Omid Hatami
23.12.2004 14:16
We can do this if and only if $2|(m-1)(n-1)$ It needs only a simple double counting. and for $m$ odd or $n$ odd the it's easy to give a solution
Myth
23.12.2004 14:26
Omid Hatami! I said the same thing.
hamedkazerooni
24.12.2004 13:02
baraye omide hatami. salam. man ham ghabool daram bayad (m-1)(n-1) bar 2 bakhshpazeer bashad. ebteda sabet khaham kard agar (m-1)(n-1) bar 2 bakhshpazeer bashad meetavan een kar ra anjam dad. be ezaye paye badihi ast. hal farz mikonam baraye kamtar az m, n ke dar sharte bala sedgh mikonand tavanesteh bashim een kar ra bokonim hala baraye m va n mikhaham een kar ra bokonam. esme jadval haiee ke m-1*n-1 anha bar 2 bakhshpazeerand ra tablo migozareem. farz konim m tedad satrha va n tedad radifhast bayad hadeaghal yeki az m ya n fard bashad agar m fard bood tebghe farze ghavi dar esteghra(masahat) baraye m*t ham sabet shodeh be torike ke t koochektar az n va m*t mostatile tablo bashad. hala yek radif m*1 ezafeh kardeh az anja ke m fard ast ba yek algorithm sotooni ra ke dar an adade -1 gharar darad ra entekhab va har bar yek khaneh az an ra ke -1 dar an neveshteh shodeh ra entekhab va amale morede nazar dar masale ra anjam midahim ba kami deghat mifahmim tamam khanehaye een radif 0 shodeh va dar samte rast va chab (dar soorate vojood) do jadval ba yek adade -1 va tablo bevojood amadeh ast. pas kar tamam ast . chon dar hengame amale masale faghat adade dakhel haman mostatilha taghieer mikonand . agar n fard bood esteslali moshabeh vali een bar yek sadre 18n ra hazf mikonim. ama baraye anke sabet konim een shart kafeest berahati mitavan did ke har bar ke rooye khanehaee ke dar satrhaye bala va paeen va sotoonhaye chab va rast een amal ra anjam dahim -1 sabet ast. va har bar ke dar khanehaye mostatile m-18n-1 anjam dahim tedad -1 haye jadval tagheer mikonad. az tarafi faghat dar soorati mishavad tamame khanehaye jadval 0 shavand ke har khaneh yek bar entekhab shavad. -1 dar ebteda be andaze fardta darim baraye anke kole jadval khali az -1 shavad bayad khanehaye mostatil tooyeeye zoj bashad.
pbornsztein
24.12.2004 13:17
Hmmm...I guess he said the same thing too Pierre.
Myth
24.12.2004 14:29
pbornsztein wrote: Hmmm...I guess he said the same thing too Pierre.
Omid Hatami
25.12.2004 14:48
Well please don't post solutions in farsi Also I told the problem is simple.