gekende klassieker van voor univ
Opgave - Putnam 2001 dag 2 vraag 1
$n$ is een even natuurlijk getal, men schrijft de getallen $1, 2, \cdots, n^2$ in de vakken van een $n \times n$ bord zodat de $k^{de}$rij, van links naar rechts de getallen
$ (k-1)n + 1, \ (k-1)n + 2, \ \cdots, \ (k-1)n + n$ bevat.
De vakjes worden gekleurd zodat de helft v.d. vakjes in een rij of kolom rood is en de andere $\frac{n}{2}$ vakjes zwart.
Bewijs dat de som van de rode waarden = som van de zwarte waarden.
- login om te reageren
Oplossing
Het getal op de $i^{de}$ rij en de $j^{de}$ kolom is gelijk aan $(i-1)n+j.$ Met $j,n$ natuurlijke getallen $>0$ en $\le n.$
Op elke $i^{de}$ rij staan er evenveel rode als zwarte waarden (opgave), er zijn dus altijd evenveel rode als zwarte getallen met eenzelfde product van n met de waarde $(i-1)n$
In elke $j^{de}$ kolom staan er ook evenveel rode als zwarte hokjes, en dus zijn er altijd evenveel getallen (namelijk $\frac{n}{2}$) in deze kolom met $j$ als extra getal (rechterdeel).
Als men dus de rode en zwarte waarden optelt zal de som "van het aantal keren n" gelijk zijn. Ook zullen de sommen van "de overige getallen zonder n als factor" gelijk zijn.
In formulevorm merken we op dat
$ \sum_{(i,j) \in R}^{} a_{ij} = \frac{n}{2}* \big( \sum_{j=1}^n j+ \sum_{i=1}^{n} (i-1)n \big)= \frac{(n^2+1)n^2}{4} $
We kunnen exact hetzelfde zeggen voor $\sum_{(i,j) \in Z}^{} a_{ij} $ en merken op dat beide waarden inderdaad de helft geven van $1^2+2^2+3^2+\cdots + n^2=\frac{(n^2+1)n^2}2$
De som van de rode waarden is dus gelijk aan de som van de zwarte waarden.