Pilī ir \(500\) istabas. No katras istabas var aiziet uz katru. Starp katrām divām istabām nav vairāk par vienām durvīm. Ja starp divām istabām ir durvis, tad no vienas istabas var aiziet uz otru tikai pa šīm durvīm.
Pierādīt, ka \(9\) sargi var noķert pilī ielavījušos zagli. (Zaglis skaitās noķerts, ja sargs nonāk ar to vienā istabā.)
Pilī var atrast istabu, uz katru pusi no kuras ir ne vairāk kā \(250\) istabas. To pierāda, izvēloties patvaļīgu istabu un, ja kādas durvis ved virzienā ar vairāk nekā \(250\) istabām, tad pavirzāmies pa šīm durvīm uz blakus istabu; atkārtojot šo procesu atrodam vajadzīgo istabu.
Nostādām šajā istabā sargu. Pa katrām šīs istabas durvīm var nokļūt kādā pils istabu grupā. No vienas istabu grupas otrā nonākt, nesastopot šo sargu nevar. Tāpēc atlikušie \(8\) sargi pēc kārtas var pārmeklēt šīs neatkarīgās istabu grupas (tajās ir ne vairāk par \(250\) istabām).
Katrā no šīm grupām sargi rīkojas analogiski. Vienu no sargiem ievieto "centrālajā" istabā, un atlikušie \(7\) sargi pārmeklē atsevišķas istabu grupas, kurās tagad ir ne vairāk kā \(125\) istabas.
Tā turpinot redzam, ka \(6\) sargiem būs jāpārmeklē istabu grupas ar ne vairāk kā \(64\) istabām, \(5\) sargiem – \(32\) istabām, \(4\) sargiem – \(16\) istabām, \(3\) sargiem – \(8\) istabām, \(2\) sargiem – \(4\) istabām, \(1\) sargam – \(2\) istabām.
Skaidrs, ka sargs var noķert zagli divās blakus istabās, pārejot no vienas uz otru.