В социален клуб има nn членове с членски номера 1,2,,n1,2,\ldots,n. От време на време членовете изпращат подаръци на други членове, включително предмети, които вече са получили като подаръци. За да се избегне неловката ситуация някой да получи подарък, който сам е изпратил, клубът въвежда следното правило: член с номер aa има право да изпрати подарък на член с номер bb тогава и само тогава, когато a(b1)a(b-1) се дели на nn. Докажете, че ако всички спазват това правило, никой няма да получи от друг член подарък, който преди това е изпратил. Еквивалентно: нека GG е насочен граф с върхове v1,v2,,vnv_1,v_2,\ldots,v_n, като има ребро от vav_a към vbv_b тогава и само тогава, когато aa и bb са различни и a(b1)a(b-1) се дели на nn. Докажете, че GG няма насочен цикъл.
📣НОВО: Добавени задачи от Международната олимпиада по математика 2000-2024
Още задачи при скрол