# International Mathematics Competition for University Students 2024

Select Year:

IMC 2024
 Information Schedule Problems & Solutions Results Contact Travel

## IMC2024: Day 2, Problem 9

Problem 9. A matrix $\displaystyle A=(a_{ij})$ is called nice, if it has the following properties:

(i) the set of all entries of $\displaystyle A$ is $\displaystyle \{1,2,\ldots,2t\}$ for some integer $\displaystyle t$;

(ii) the entries are non-decreasing in every row and in every column: $\displaystyle a_{i,j}\leq a_{i,j+1}$ and $\displaystyle a_{i,j}\leq a_{i+1,j}$;

(iii) equal entries can appear only in the same row or the same column: if $\displaystyle a_{i,j}=a_{k,\ell}$, then either $\displaystyle i=k$ or $\displaystyle j=\ell$;

(iv) for each $\displaystyle s=1,2,\ldots,2t-1$, there exist $\displaystyle i\ne k$ and $\displaystyle j\ne \ell$ such that $\displaystyle a_{i,j}=s$ and $\displaystyle a_{k,\ell}=s+1$.

Prove that for any positive integers $\displaystyle m$ and $\displaystyle n$, the number of nice $\displaystyle m\times n$ matrices is even.

For example, the only two nice $\displaystyle 2\times 3$ matrices are $\displaystyle \begin{pmatrix} 1&1&1\\2&2&2 \end{pmatrix}$ and $\displaystyle \begin{pmatrix} 1&1&3\\2&4&4 \end{pmatrix}$.

Fedor Petrov, St Petersburg State University

 IMC1994 IMC1995 IMC1996 IMC1997 IMC1998 IMC1999 IMC2000 IMC2001 IMC2002 IMC2003 IMC2004 IMC2005 IMC2006 IMC2007 IMC2008 IMC2009 IMC2010 IMC2011 IMC2012 IMC2013 IMC2014 IMC2015 IMC2016 IMC2017 IMC2018 IMC2019 IMC2020 IMC2021 IMC2022 IMC2023