Atrisinājums

Mazākais iespējamais kopējais ceļojumu skaits ir \(10\). Rakstīsim ceļojumus \(6 \times 6\) tabulā, rindiņas atbildīs tūristiem, kolonnas - valstīm, ja tūrists ir bijis ceļojumā uz kādu valsti, tad šajā rūtiņā liksim krustiņu. Pamatosim, ka der tabulā parādītais piemērs. Viegli redzēt, ka jebkuri \(3\) tūristi ir kopumā apmeklējuši vismaz \(4\) valstis, tātad, izvēloties jebkuras \(3\) valstis, vismaz vienu no tām kāds no šiem tūristiem būs apmeklējis.

Pierādīsim, ka ar deviņiem ceļojumiem nepietiek. Aplūkosim \(3\) tūristus, kuri ir devušies vismazāk ceļojumos. Vispirms pamatosim, ka tie kopā ir devušies ne vairāk kā \(3\) ceļojumos. Ja tie būtu devušies četros ceļojumos, tad vismaz kāds no tiem būtu devies divos ceļojumos, tātad arī atlikušie \(3\) tūristi katrs būtu devušies vismaz divos ceļojumos (jo mēs aplūkojam tūristus, kas ir ceļojuši vismazāk). Tātad kopējais ceļojumu skaits ir vismaz \(4+2 \cdot 3=10\) un iegūta pretruna. Līdz ar to ir \(3\) tūristi, kas kopā ir devušies ne vairāk kā \(3\) ceļojumos, tātad tie kopā apmeklējuši ne vairāk kā \(3\) valstis. Tāpēc ir vismaz \(3\) valstis, ko neviens no šiem trim tūristiem nav apmeklējis, kas ir pretrunā ar uzdevuma nosacījumiem.