Kādā pilsētā ir \(n\) detektīvi (\(n \geq 2\)) un cita starpā tie izseko arī viens otru. Zināms, ka jebkuriem diviem detektīviem \(A\) un \(B\) vai nu \(A\) izseko \(B\), vai \(B\) izseko \(A\). Pierādīt, ka visus detektīvus var nostādīt vienā rindā tā, ka pirmais izseko otro, otrais - trešo, \(\ldots\), \((n-1)\)-ais izseko \(n\)-to.
Apgalvojumu pierādīsim ar matemātisko indukciju pēc detektīvu skaita \(n\).
Bāze. Ja \(n=2\), apgalvojums ir patiess, t.i., \(A_{1} \rightarrow A_{2}\) (detektīvs \(A_{1}\) izseko detektīvu \(A_{2}\)).
Induktīvais pieņēmums. Pieņemsim, ka \(k\) detektīvi \(A_{1}, A_{2}, \ldots, A_{k}\) nostādīti rindā atbilstoši uzdevuma nosacījumiem:
\[A_{1} \rightarrow A_{2} \rightarrow \cdots \rightarrow A_{i} \rightarrow A_{i+1} \rightarrow \cdots \rightarrow A_{k}\]
*Induktīvā pāreja.* Aplūkojam detektīvu \(A_{k+1}\). Iespējami divi gadījumi: 1. Ja detektīvs \(A_{k+1}\) izseko detektīvu \(A_{1}\) (apzīmēsim \(A_{k+1} \rightarrow A_{1}\) ), tad detektīvu \(A_{k+1}\) var novietot rindas sākumā. 2. Ja \(A_{1} \rightarrow A_{k+1}\), tad iespējami divi gadījumi: - visiem \(i\) izpildās \(A_{i} \rightarrow A_{k+1}\), tad detektīvu \(A_{k+1}\) var nostādīt rindas beigās; - ja visiem \(i\) neizpildās, ka \(A_{i} \rightarrow A_{k+1}\), tad ņemsim mazāko \(i\) tādu, ka \(A_{k+1} \rightarrow A_{i}\), tādā gadījumā \(A_{i-1} \rightarrow A_{k+1}\). Tad detektīvu \(A_{k+1}\) var nostādīt rindā starp detektīviem \(A_{i-1}\) un \(A_{i}\).Līdz ar to esam pieradījuši uzdevuma prasīto.