Haidora and number theory#12296

Haidora and number theory (Editorial)

Problem Author:	Haidara Al Makdid
Prepared by:	Haidara Al Makdid
Edited by:	Hasan Saleh (MathModel)

Solution

Claim : Every integer $n \geq 2$ n \ge 2 satisfies $f (n) = 2$ f(n)=2

Let $d (n)$ denote the number of divisors of $n$ . Consider the sequence defined by $x_{0} = n$ x_0 = n and $x_{k + 1} = d (x_{k})$ x_{k+1} = d(x_k).

For all integers $n > 2$ n \gt 2, the inequality $2 \leq d (n) < n$ 2 \le d(n) < n holds.

Lower Bound: Since $1$ and $n$ are distinct divisors of $n$ for any $n \geq 2$ n \ge 2, we have $d (n) \geq 2$ d(n) \ge 2.
Upper Bound: The divisors of $n$ are a subset of ${1, 2, \dots, n}$ \{1, 2, \dots, n\}. For $n > 2$ n > 2, $n - 1$ n-1 does not divide $n$ (since $n < 2 (n - 1)$ n < 2(n-1)). Thus, the set of divisors is a proper subset of ${1, 2, \dots, n}$ \{1, 2, \dots, n\}, implying $d (n) < n$ d(n) < n.

Every integer sequence defined by $x_{0} = n$ x_0 = n ( $n > 2$ n > 2) and $x_{k + 1} = d (x_{k})$ x_{k+1} = d(x_k) eventually reaches the fixed point 2.

Assume $n > 2$ n > 2. By the Lemma, if $x_{k} > 2$ x_k > 2, then:

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

2 \le x_{k+1} < x_k

This defines a strictly decreasing sequence of integers bounded below by 2. By the method of infinite descent (or the Well-Ordering Principle), such a sequence cannot be infinite; it must eventually reach a value where the strict decreasing condition $x_{k} > 2$ x_k > 2 no longer holds.

Since the sequence is bounded below by $2$ , it must terminate at $x_{m} = 2$ x_m = 2 for some finite index $m$ .

Finally, verifying the fixed point:

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

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

Thus, once the sequence reaches 2, it remains constant at 2 indefinitely.

Therefore , We can assign $x \leftarrow 2$ x \gets 2 when $x \neq = 1$ x \neq 1 and $x = 1$ x=1 when $x = 1$ x=1 (remains untouched) and then our problem is solved.

This forces exactly two of ${a, b, c}$ \{a,b,c\} to be $1$ and the other is not $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