telprobleem

Opgave - NWO 2005 vraag 1

Hoeveel koppels getallen $(a,b)$ met $a < b$ kun je uit de verzameling $\{1,2,\ldots,2005\}$ kiezen met de eigenschap dat $a+b$ een vijfvoud is?

Oplossing

De verzameling opdelen in stukken van vijf levert ons het makkelijkst de oplossing. $\{1,2,\ldots,2005\}=\{1,2,3,4,5\}\cup\{6,7,8,9,10\}\cup\ldots\cup\{2001,2002,2003,2004,2005\}$. We noemen deze disjuncte verzameling $\mathcal A_1$ tot en met $\mathcal A_{401}$ respectievelijk en zien dat ze modulo 5 gelijk zijn. Met ieder element uit $\mathcal A_i$ komt er precies één element uit $\mathcal A_j$ overeen (met $i