Гайдо́ра та теорія чисел#12296

Гайдо́ра та теорія чисел (Розбір)

Автор проблеми:	Гайдо́ра Аль Макдід
Підготовлено:	Гайдо́ра Аль Макдід
Редагував:	Хасан Салех (MathModel)

Рішення

Твердження: Кожне ціле число $n \geq 2$ n \ge 2 задовольняє $f (n) = 2$ f(n)=2

Нехай $d (n)$ позначає кількість дільників $n$ . Розглянемо послідовність, визначену як $x_{0} = n$ x_0 = n та $x_{k + 1} = d (x_{k})$ x_{k+1} = d(x_k).

Для всіх цілих чисел $n \geq 2$ n \ge 2 виконується нерівність $2 \leq d (n) < n$ 2 \le d(n) < n.

Нижня межа: Оскільки $1$ та $n$ є різними дільниками $n$ для будь-якого $n \geq 2$ n \ge 2, маємо $d (n) \geq 2$ d(n) \ge 2.
Верхня межа: Дільники $n$ є підмножиною ${1, 2, \dots, n}$ \{1, 2, \dots, n\}. Для $n > 2$ n > 2, $n - 1$ n-1 не ділить $n$ (оскільки $n < 2 (n - 1)$ n < 2(n-1)). Таким чином, множина дільників є правильною підмножиною ${1, 2, \dots, n}$ \{1, 2, \dots, n\}, що означає $d (n) < n$ d(n) < n.

Кожна ціла послідовність, визначена як $x_{0} = n$ x_0 = n ( $n > 2$ n > 2) та $x_{k + 1} = d (x_{k})$ x_{k+1} = d(x_k), врешті-решт досягає фіксованої точки 2.

Припустимо, що $n > 2$ n > 2. За Лемою, якщо $x_{k} > 2$ x_k > 2, тоді:

2 \leq x_{k + 1} < x_{k}

2 \le x_{k+1} < x_k

Це визначає строго спадну послідовність цілих чисел, обмежену знизу 2. За методом нескінченного спаду (або принципом добре впорядкованих множин), така послідовність не може бути нескінченною; вона повинна врешті-решт досягти значення, де умова строгого спаду $x_{k} > 2$ x_k > 2 більше не виконується.

Оскільки послідовність обмежена знизу 2, вона повинна завершитися при $x_{m} = 2$ x_m = 2 для деякого скінченного індексу $m$ .

Нарешті, перевіряючи фіксовану точку:

d (2) = ∣ {1, 2} ∣ = 2

d(2) = |\{1, 2\}| = 2

Таким чином, як тільки послідовність досягає 2, вона залишається сталою на 2 безкінечно.

Отже, ми можемо призначити $x \leftarrow 2$ x \gets 2, коли $x \neq = 1$ x \neq 1, і $x = 1$ x=1, коли $x = 1$ x=1 (залишається незмінним), і тоді наша проблема вирішена.

Це змушує точно два з ${a, b, c}$ \{a,b,c\} бути $1$ , а інше не є $1$ .

def solve():
    a,b,c=map(int,input().split())
    if([a,b,c].count(1)==2):
       print("Yes")
    else:
       print("No")

for _ in range(int(input())):
    solve()

Python