Parlamentā ir \(2013\) deputāti; katram no viņiem ir domstarpības ar ne vairāk kā \(d\) (\(0 \leq d \leq 2012\)) citiem deputātiem. Domstarpības ir abpusējas: ja \(A\) ir domstarpības ar \(B\), tad arī \(B\) ir domstarpības ar \(A\). Pierādīt, ka deputātus var sadalīt \(d+1\) komisijā tā, lai nekādiem diviem vienas komisijas locekļiem nebūtu domstarpību savā starpā.
Pierādīsim vispārīgāku apgalvojumu: ja parlamentā ir \(n\) deputāti un katram no viņiem ir domstarpības ar ne vairāk kā \(d\) citiem deputātiem, kur \(0 \leq d \leq n\), tad deputātus var sadalīt \(d+1\) komisijā tā, lai vienas komisijas nekādiem diviem deputātiem nebūtu domstarpību savā starpā. Tādā gadījumā uzdevumā prasītais sekos no pierādītā apgalvojuma, ja \(n=2013\). Pierādāmo apgalvojumu pamatosim ar matemātisko indukciju pēc \(n\).
Indukcijas bāze. Ja \(n=d+1\), tad katrā no \(d+1\) komisijām iekļaujam tieši vienu deputātu. Acīmredzami, ka tad starp vienas komisijas locekļiem nekādiem diviem deputātiem nebūtu domstarpību savā starpā.
Induktīvais pieņēmums. Pieņemsim, ka gadījumā, ja parlamentā ir \(n\) deputāti, tad viņus var sadalīt vajadzīgajā veidā.
Induktīvā pāreja. Pieņemsim, ka parlamentā ir \(n+1\) deputāts; parādīsim, ka arī tad viņus var sadalīt \(d+1\) komisijā vajadzīgajā veidā.
Izvēlamies patvaļīgu deputātu \(A\). Atlikušos \(n\) deputātus sadala \(d+1\) komisijā tā, lai starp vienas komisijas locekļiem nekādiem diviem deputātiem nebūtu domstarpību savā starpā (ko var izdarīt, saskaņā ar induktīvo pieņēmumu). Deputātam \(A\) ir domstarpības ar ne vairāk kā \(d\) citiem deputātiem, taču izveidota \(d+1\) komisija. Tas nozīmē, ka ir vismaz viena tāda komisija, ka \(A\) nav domstarpību ne ar vienu šīs komisijas deputātu. Tad \(A\) varam iekļaut šajā komisijā, līdz ar ko arī \(n+1\) deputāts ir sadalīts \(d+1\) komisijā vajadzīgajā veidā. Induktīvā pāreja ir izdarīta, tātad apgalvojums ir pierādīts.