IMO Shortlist 2009 - Problem N5

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

IMO Shortlist 2009 - Problem N5

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1270 posts

April

#1 h Jul 5, 2010, 11:53 AM • 4 Y

Y by arandomperson123, Davi-8191, jhu08, Adventure10

Let $P(x)$ be a non-constant polynomial with integer coefficients. Prove that there is no function $T$ from the set of integers into the set of integers such that the number of integers $x$ with $T^n(x)=x$ is equal to $P(n)$ for every $n\geq 1$ , where $T^n$ denotes the $n$ -fold application of $T$ .

Proposed by Jozsef Pelikan, Hungary

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2043 posts

Zhero

#2 h Jul 6, 2010, 7:59 PM • 9 Y

Y by StanleyST, arandomperson123, jhu08, Adventure10, Mango247, and 4 other users

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1502 posts

SCP

#3 h Jul 14, 2011, 10:51 AM • 2 Y

Y by jhu08, Adventure10

I didn't understand $ia_i$ is trivial, but that is cleared/ thanks.

But isn't it so there is a simpler solution with fact $T(T(x))=x$ has max. $gr(T)^2$ solutions, hence $T^n(x)=x$ has also a finite number of solutions...

edit: it works with polonomials, but not in other way and I saw.

This post has been edited 2 times. Last edited by SCP, Jul 14, 2011, 11:45 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

118 posts

RaleD

#4 h Jul 14, 2011, 10:56 AM • 2 Y

Y by jhu08, Adventure10

$i|a_i$ because of cycles.
And your solution is nonsense because $T$ isn't polymomial.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#5 h Jul 14, 2011, 11:06 AM • 3 Y

Y by jhu08, Adventure10, Mango247

You mean you don't understand that $i \mid a_i$ , i.e. $i$ divides $a_i$ . This follows from the fact that if for some $a$ we have $T^i(a) = a$ , but not $T^j(a) = a$ for any $0<j<i$ , then the orbit of $a$ is given by $i$ distinct numbers $a,T(a),\ldots,T^{i-1}(a)$ , and since orbits are clearly disjoint, it means $a_i$ , which counts all elements of all such orbits, is divisible by $i$ .

As for your second assertion, the concept $\deg T$ is ill-used, since $T$ is not specified to be a polynomial function.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

366 posts

#6 h Feb 4, 2015, 5:41 PM • 3 Y

Y by jhu08, Adventure10, Mango247

Let $b_i$ be the number of primitive solutions to $T^i(x)=x$ . Clearly $i | b_i$ , since $b_i$ is the number of elements of $i$ -cycles of $T$ . And $P(n) = \sum_{d|n} b_d$ . There are two ways to finish

(1) We see that if $q$ is prime, $P(nq) = \sum_{d|n} b_d + \sum_{e} b_e$ , where the second sum runs over divisors of $nq$ with maximal $v_q$ . Therefore $q | P(nq)-P(n)$ , and from this, $q | P(n)-a_0$ , where $a_0$ is the constant term of $P$ . Then the polynomial $P-a_0$ is always divisible by all primes, contradiction since this implies $P$ is constant.

(2) Mobius Inversion. We get $n | b_n = \sum_{d|n} P(d)\mu(n/d)$ and we can finish easily.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

487 posts

#7 h Feb 5, 2015, 10:56 AM • 2 Y

Y by jhu08, Adventure10

Suppose to the contrary. Define $\text{ord}(x)$ to be the smallest integer $d$ such that $T^d(x) = x$ . Let $a_n$ denote the number of positive integers $x$ such that $\text{ord}(x) = n$ .

Let $d = \text{ord}(x)$ . Now, if $T^n(x) = x$ for some $n \in \mathbb{N}$ , let $n = dq+r$ , with $r \in [0,d)$ . Then $x = T^n(x) = T^{dq+r}(x) = T^r(T^{dq}(x)) = T^r(x)$ . Since this is impossible for $r \in (0, d)$ (minimality of $d$ ), we must have $r = 0$ , i.e. $d|n$ . Note also that whenever $d|n$ , $T^n(x) = x$ .

Now, $P(n)$ counts the number of integers $x$ with $T^n(x) = x$ . Since $d|n$ , therefore $P(n)$ must be obtained by adding the number of integers $x$ , for which $\text{ord}(x)$ is in the set of divisors of $n$ . Therefore, $P(n) = \sum_{d|n}a_d$ .

Observe that $d|a_d$ . This is because whenever $\text{ord}(x) = d$ , we also have $\text{ord}(T^i(x)) = d$ $\forall i \in [1, d)$ . To see why, note that $T^{i+d}(x) = T^i(x)$ . If there is a smaller integer $d'$ such that $T^{d'+i}(x) = T^i(x)$ , we may apply $T$ iterated $d-i$ times on either side to obtain $T^{d+d'}(x) = T^d(x) \Longleftrightarrow T^{d'}(x) = x$ , a contradiction. Furthermore, note that we can split these numbers into the aforementioned kind of cycles. To prove that these cycles are disjoint, suppose to the contrary. Then, for some $y$ not in the cycle corresponding to $x$ , we must have $\text{ord}(x) = \text{ord}(y) = d$ and $T^i(x) = T^j(y)$ for some $i, j \in [0, d)$ . Applying $T$ iterated $d-j$ times on either side, we have $T^{d+i-j}(x) = T^d(y) \implies T^{d+i-j}(x) = y$ , contradicting our assumption. Since $a_d$ counts the number of such integers and since these can be split into cycles of length $d$ , we must have $d|a_d$ .

Now, let $p, q$ be distinct primes $\in \mathbb{P}$ . Then, $P(pq) = a_1+a_p+a_q+a_{pq} \equiv a_1+a_q \equiv P(q) \pmod{p}$ But, $P(pq) \equiv P(0) \pmod{p}$ . Therefore, $P(q) \equiv P(0) \pmod{p} \implies p|P(q)-P(0)$ Since $P$ is non-constant, there exists $q$ such that $P(q) \neq P(0)$ (otherwise, there would exist infinitely many roots to $P(x)-P(0)$ ). Now, choosing $p$ arbitrarily large, we have a contradiction, since $P(q)-P(0)$ cannot have arbitrarily large prime divisors.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6882 posts

#8 h Mar 29, 2017, 10:52 PM • 5 Y

Y by anantmudgal09, Aryan-23, v4913, jhu08, Adventure10

Write $T$ in cycle notation and let $c_n \ge 0$ denote the number of cycles of length $n$ . Then the point is that $P(n) = \sum_{d \mid n} d c_d.$ By shifting $P$ by a constant we may assume $c_1 = 0$ . Now we contend $c_q = 0$ for every prime $q$ , which implies $P(q) = 0$ for all primes $q$ , hence $P \equiv 0$ .

First, note that by selecting $p$ prime we get $P(0) \equiv P(p) = c_1 + pc_p \equiv c_1 \equiv 0 \pmod p$ whence $P(0) = 0$ , since $p$ was any prime.

Now observe $P(pq) = c_1 + p \cdot c_p + q \cdot c_q + pq \cdot c_{pq} \implies 0 \equiv P(0) \equiv P(pq) \equiv q c_q \pmod p$ whence $c_q \equiv 0 \pmod p$ for all $p \neq q$ , hence $c_q = 0$ .

This post has been edited 1 time. Last edited by v_Enhance, Mar 30, 2017, 10:23 PM
Reason: q not k

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

409 posts

#9 h Apr 1, 2017, 8:25 AM • 2 Y

Y by jhu08, Adventure10

Take $p$ a prime and $x_0$ such that $T^p(x_0)=x_0$ . We infer that either $x$ is a fixed point or the orbit of $x_0$ within $T$ is of length $p$ . As a general observation that will be used later, if $T^n(x_0)=x_0$ then $T^n (T(x_0))=T(x_0)$ , so all the values from the orbit of $x_0$ satisfy $T^n(x)=x$ .

On a set $R$ whose elements all have finite orbits length we can define the relation $a \sim b\Leftrightarrow a=T^i (b)$ for some nonnegative integer $i$ . It is easy to see that $\sim$ is an equivalence relation and that the class of an element $a$ is exactly the orbit of $a$ . This in turn implies that if the length of the orbits of all the elements are divisible by a number $k$ , then $k$ divides $|R|$ because each class has a multiple of $k$ elements and the classes partition $R$ .

Take $p,q$ distinct primes and look at the set $M=\{x\in \mathbb{Z}| T^{pq}(x)=x\}$ . The length of the orbit of an element in $M$ can only take values in the set $\{1,p,q,pq\}$ . The set $N$ of elements from $M$ with orders $1$ and $q$ is actually the set of solutions to $T^q(x)=x$ , hence its cardinality is $P(q)$ . The set $M-N$ has only elements of orders $p$ and $pq$ , so, by the previous paragraph, the total number of elements in $M-N$ is divisible by $p$ .

We conclude that $P(pq)=|M|=|N|+|M-N|=P(q)+p\alpha$ , so $p$ divides $P(pq)-P(q)$ , or equivalently $P(0)-P(q)$ . Taking $p$ very large we conclude that $P(0)=P(q)$ . But this happens for an infinite number of primes $q$ , hence $P$ is constant, contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1298 posts

Kayak

#10 h Sep 6, 2017, 7:21 AM • 3 Y

Y by biomathematics, jhu08, Adventure10

Please check my solution

Solution

Random Notes

This post has been edited 3 times. Last edited by Kayak, Sep 6, 2017, 7:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

33 posts

#11 h Dec 19, 2017, 11:25 AM • 3 Y

Y by jhu08, Adventure10, Mango247

It seems to be correct

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2130 posts

DrMath

#12 h Jan 7, 2018, 8:23 PM • 3 Y

Y by jhu08, Adventure10, Mango247

Note that $\sum_{d\mid n} P(d) \mu (n/d)$ gives the number of solutions $x$ such that $T^n(x)=x$ but $T^m(x)\neq x$ for $m<n$ . Clearly, this number must be divisible by $n$ , so we have $n\mid \sum_{d\mid n} P(d)\mu (n/d)$ .

Let $p$ and $q$ be primes and $n>1$ an arbitrary integer. Then $q\mid p^nq\mid P(p^nq)-P(p^n)-P(p^{n-1}q)+P(p^{n-1})$ . Since $q\mid P(p^nq)-P(p^{n-1}q)$ , we get $q\mid P(p^n)-P(p^{n-1})$ . Repeating this for all primes $q$ , we get $P(p^n)=P(p^{n-1})$ . Since this holds for all integers $n>1$ , we get $P(x)$ attains the same value for infinitely integers $x$ , and thus $P$ must be constant, contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathStudent2002

934 posts

MathStudent2002

#13 h Jan 6, 2019, 11:35 PM • 1 Y

Y by Adventure10

Define the order of $x\in \mathbb Z$ to be the minimum $n > 0$ such that $T^n(x) = x$ and $0$ if $n$ does not exist. Note that $a_n \leq P(n)$ is finite. Now, if we draw the graph on $\mathbb Z$ where $x\to T(x)$ , then $a_n = nb_n$ where $b_n$ is the number of cycles of length $n$ ; in particular $n\mid a_n$ . Now, clearly $P(n) = \sum_{d\mid n} a_d,$ so by Mobius Inversion we have $n\mid a_n = \sum_{d\mid n} \mu\left(\frac nd\right) P(d).$ Let $p,q$ be distinct primes. Then, $p\mid a_{pq} = P(1)-P(p)-P(q)+P(pq),$ i.e. $p\mid P(1)-P(q)$ . Combining with $p\mid a_p = P(1)-P(p)$ we get that $p\mid P(1)-P(q)$ for all primes $q$ . In particular, $q$ hits every residue mod $p$ by Dirichlet, so $P$ is constant mod $p$ for all $p$ . This implies $P$ is constant on $\mathbb N$ : indeed, if there existed $a,b > 0$ with $P(a)\neq P(b)$ , then we could find some prime $Q$ such that $P(a)\not\equiv P(b)\pmod Q$ (take $Q > |P(a)-P(b)|$ ), contradiction. So, $P$ is constant on $\mathbb N$ and is a constant polynomial, contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1218 posts

#14 h Apr 1, 2019, 8:44 AM • 1 Y

Y by Adventure10

Nice problem. Here's my solution: FTSOC assume that such a function $T$ exists. Construct an infinite directed graph, and label the vertices $1,2,3, \dots,$ such that there is an edge from $i$ to $j$ if and only if $j=T(i)$ (The graph is not necessarily simple). Let $p$ be some prime, and $f(p)$ denote the number of directed cycles of length $p$ . Also, let $f(1)$ be the number of integers $x$ satisfying $T(x)=x$ (i.e. the number of loops in our graph). Then, the given condition states that $P(p)=pf(p)+f(1)$ (since each element $x$ of a cycle of length $p$ satisfies $T^p(x)=x$ ). Now, $p \mid P(p)-P(0) \Rightarrow P(0) \equiv pf(p)+f(1) \equiv f(1) \pmod{p}$ Thus, $p \mid P(0)-f(1)$ for all primes $p$ , which is only possible if $P(0)=f(1)$ . Let $p'$ be another prime ( $p' \neq p$ ). Then, again from the given condition, we get that $P(pp')=f(1)+pf(p)+p'f(p')+pp'f(pp') \Rightarrow P(pp') \equiv f(1)+pf(p) \equiv P(0)+pf(p) \pmod{p'}$ But, we know that $pp' \mid P(pp')-P(0) \Rightarrow pf(p) \equiv P(pp')-P(0) \equiv 0 \pmod{p'}$ This means that $p' \mid f(p)$ for all primes $p' \neq p$ , which is only possible if $f(p)=0$ . Thus, $P(p)=f(1)$ for all primes $p$ . But then the polynomial $P-f(1)$ has infinitely many roots, and so it must be an identity; which contradicts the fact that $P$ is non-constant. Hence, done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

830 posts

niyu

#15 h May 1, 2019, 11:30 PM • 1 Y

Y by Adventure10

Nothing different from the above solutions, but posting for storage.

Suppose for contradiction that such a function $T$ did exist.

We let the order of an integer $k$ be the minimal $\ell \geq 1$ such that $T^\ell(k) = k$ . Let $f(n)$ be the number of integers $k$ that have order $n$ (where $n \geq 1$ ).

We claim that $n \mid f(n)$ . Indeed, let $k$ be an integer with order $n$ . Then, $k, T(k), T^2(k), \ldots, T^{n - 1}(k)$ all have order $n$ as well; hence, integers of order $n$ come in groups of $n$ , proving the claim.

Now, suppose $k$ satisfies $T^n(k) = k$ . Trivially, the order of $k$ must divide $n$ . It follows that there are
$\begin{align*} \sum_{d \mid n} f(d) \end{align*}$ integers $k$ that satisfy $T^n(k) = k$ . Therefore,
$\begin{align*} P(n) &= \sum_{d \mid n} f(d). \end{align*}$
Now, fix a prime $q$ , and let $p > q$ be a prime. We have
$\begin{align*} P(1) &= f(1) \\ P(p) &= f(1) + f(p) \\ P(q) &= f(1) + f(q) \\ P(pq) &= f(1) + f(p) + f(q) + f(pq). \end{align*}$ Hence,
$\begin{align*} f(pq) &= P(pq) - P(p) - P(q) + P(1). \end{align*}$ Since $p \mid pq \mid f(pq)$ , we have
$\begin{align*} P(pq) - P(p) - P(q) + P(1) &\equiv 0 \pmod{p} \\ P(1) - P(q) &\equiv 0 \pmod{p}. \end{align*}$ Hence, for all primes $p > q$ , we have $p \mid P(1) - P(q)$ , which is enough to imply that $P(q) = P(1)$ . Hence, $P(q) = P(1)$ for all primes $q$ , which is enough to imply that $P$ is a constant polynomial; contradiction. $\Box$

This post has been edited 3 times. Last edited by niyu, May 1, 2019, 11:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#16 h May 12, 2019, 5:33 PM • 2 Y

Y by XbenX, Adventure10

Obviously, we'll assume that such a $(T,P)$ existed.

Let $c_n$ be the number of integers such that the smallest $m$ such that $T^m(x)=x$ is $n$ . We see then that
$P(n)=\sum_{d\mid n} c_d,$ so
$c_n=\sum_{d\mid n}\mu(d)P(n/d)$ by Mobius inversion.

Motivational Remarks
For any two primes $p,q$ , we see that
$c_{pq^n}=P(pq^n)-P(q^n)-P(pq^{n-1})+P(q^{n-1}).$ This must be divisible by $p$ , and we see that $p\mid P(pq^n)-P(pq^{n-1})$ , so we have
$P(q^n)\equiv P(q^{n-1})\pmod{p}$ for all primes $p$ . This implies $P(q^n)=P(q^{n-1})$ for all $n$ , which is clearly a contradiction, as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

308 posts

#17 h Aug 12, 2020, 10:19 AM

Y by

Suppose on the contrary that such function exists, for each positive integer $n$ , suppose that $T$ has $x_n$ $n-$ cycles. Then the number of integer $x$ with $t^n(x)=x$ is equal to
$\sum_{d|n}nx_n=P(n)$ Let $y_n=nx_n$ , by Mobius inversion formula,
$y_n=\sum_{d|n}\mu(d)P(\frac{n}{d})$ In particular for every prime $p$ and integer $\alpha$ we have
$p^{\alpha}|y_{p^\alpha}=\sum_{d|p^{\alpha}}\mu(d)P(\frac{p^{\alpha}}{d})=P(p)-P(1)$ since $\mu(p^i)=0$ for all $i\geq 2$ . This implies $P(p)-P(1)=0$ . Since this holds for every prime $p$ , $P$ must be a constant, contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

258 posts

#18 h Aug 15, 2020, 1:20 PM

Y by

The number of solutions of T^q(X)=X is divisble by q for every prime q that's because we have a string a1,a2,..,a_q with T(a_i)=a_(i+1) and T(a_q)=a1 and we cant have a_i=a_j because then we get that something divides q (the reader should check why). Therefor the string has q different solutions to the equation which are a_i for all i multiplied by the number of such strings and therefore q divides P(q) for all q so q divides the free coeficent of P so q is infinitly big (impossible) or zero.

This post has been edited 1 time. Last edited by Mikeglicker, Aug 15, 2020, 7:36 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

779 posts

#19 h Nov 27, 2020, 4:04 AM

Y by

Suppose FTSOC that such a $T$ exists, and define the $\emph{order}$ of $x$ as the smallest $k$ such that $T^k(x)=x.$ It follows from cycle decomposition that the number of integers with order $k$ is divisible by $k$ for all $k.$

$\textbf{Claim: }$ $P(0)=P(x)$ for infinitely many primes $x.$

$\emph{Proof: }$ Divide the set of primes into two disjoint infinite sets $A$ and $B,$ and fix $p\in A,q\in B.$

Suppose $x$ is an integer satisfying $T^{pq}(x)=x.$ Then, the order of $x$ is $1,p,q,$ or $pq.$ Now observe the following.

The number of integers with order $p$ or $pq$ is divisible by $p.$
The number of integers with order $1$ or $q$ is equivalent to the number of solutions to $T^{q}(x)=x,$ which is $P(q).$

Therefore, $P(pq)\equiv P(q)\pmod{p}.$ But it is well-known that $P(pq)\equiv P(0)\pmod{p},$ so we have $p\mid P(q)-P(0).$

Since we can apply the same reasoning for all $p\in A,$ we have $P(0)=P(q)$ for all $q\in B.$ $\blacksquare$

Therefore, $P$ must be constant, contradiction.

This post has been edited 3 times. Last edited by amuthup, Nov 27, 2020, 4:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1065 posts

Eyed

#20 h Dec 27, 2020, 10:46 PM • 1 Y

Y by AwesomeYRY

Same as everyone else:

Put the function $T$ on a graph of integers, and draw an arrow between $x$ and $T(x)$ . Let $f(n)$ be the number of cycles of length $n$ . Clearly, the only time $T^{n}(x) = x$ is if $x$ is in a cycle of length $d$ , where $d | n$ . This implies
$\sum_{d|n} df(d) = P(d)$ Consider some $n$ such that $v_{p}(n) = r$ , and let $m = \frac{n}{p^{r}}$ . Then, consider $P(n) - P(m)$ ; for any $d | n$ and $d\not | m$ , we must have $p | d$ . Thus, using the formula for $P(n)$ , it implies
$p | P(n) - P(m) \Rightarrow p | P(m) - P(0)$ However, observe that $m$ can take on any value, and $p$ can be any prime. Thus, for all $p$ and all $m$ , this holds. However, for large enough $p$ , we have $p > |P(m) - P(0)|$ , which means $P(m) = P(0)$ . This means $P$ is a constant polynomial, a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1492 posts

#21 h Sep 8, 2021, 1:29 AM • 1 Y

Y by Mango247

Does this work?????

View as a directed graph where we draw an arrow from $x \to T(x).$

Let $c_k$ denote the number of cycles of length $k.$ Assuming there existed a $T,$ $P(n) = \sum_{d \mid n} d c_d.$ Then, consider $P(pq) - P(q)$ for fixed primes $p$ and $q.$ We must have $P(pq) - P(q) = pq c_{pq}.$ Let $P(x) = a_k x^k + \cdots + a_0.$ Then, $pq \mid P(pq) - P(q) \iff p \mid q^k(p^k-1)a_k + q^{k-1} (p^{k-1}-1) + \cdots + q(p-1)$ which gives $p \mid P(q) - a_0.$ However, since we can now fix $q$ and take $p$ very large, this cannot be true for all $(p,q),$ so $P(q) - a_0 = 0 \implies P(q) = a_0$ for all $q,$ which in turn implies that $P$ is constant, contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

304 posts

#22 h Dec 19, 2021, 5:48 AM

Y by

Let $c_i$ denote the number of cycles of length $i$ . We get the following identity. $P(n)=\sum_{d|n} nc_n$ . We claim this is impossible. Indeed, assume that such a polynomial exists. For any prime $p$ we have $P(p)=c_1+pc_p$ . So, $P(p) \equiv c_1$ (mod $p$ ) for every prime $p$ . Thus, $P(x)=x \cdot Q(x)+c_1$ for some integer polynomial $Q$ . Now, we have $pq \cdot Q(pq)+c_1=P(pq)=c_1+pc_p+qc_q+pqc_{pq}$ for any primes $p$ and $q$ . Thus, $pq$ divides $pc_p+qc_q$ but by making $p$ sufficiently large, this identity clearly breaks down. Contradiction.

This post has been edited 1 time. Last edited by blackbluecar, Apr 11, 2022, 12:54 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5005 posts

#23 h Apr 4, 2022, 5:46 PM • 1 Y

Y by centslordm

View $T$ as a directed graph in the obvious way. We only care about directed cycles. Let $C(n)$ denote the number of cycles of length $n$ , so we want to have
$P(n)=\sum_{d \mid n} dC(d)$ for all $n$ . In particular, $P(p)=C(1)+pC(p)$ for all primes $p$ . Let $P(x)=xQ(x)+C$ for some constant $C$ , so we can write
$pQ(p)-pC(p)=C(1)-C$ for all $p$ , hence $C(1)-C$ has infinitely many prime divisors so it equals zero, i.e. $P(x)=xQ(x)+C(1)$ . Let $p$ be an arbitrary prime. Then for all $q$ , we have
$pqQ(pq)+C(1)=P(pq)=C(1)+pC(p)+qC(q)+pqC(pq),$ so $q \mid pC(p) \implies q \mid C(p)$ . Thus $C(p)=0$ , as $C(p)$ has infinitely many prime divisors. As such,
$P(p)=C(1)+pC(p)=0$ for all primes $p$ , hence $P$ must be the zero polynomial, which is forbidden. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#24 h Jul 20, 2022, 12:05 AM • 1 Y

Y by Mango247

Consider $T$ as an arrows graph: a collection of chains and cycles. Let $a_i$ denote the number of cycles of length $i$ . Assume that $P(n)$ is the number of fixed points of $T^n(x)$ , then $P(n)$ can be fully characterized as
$P(n) = \sum_{d\mid n} d a_d$ where $\{a_i\}_i$ is an infinite sequence of nonnegative integers. Let $P(x) = b_n x^n + b_{n-1} x^{n-1} + \cdots b_0$ . Then, note that $P(q^{k+1}) \equiv P(q^k) \pmod{q^{k+1}}$ . But, $q^{k+1} \mid P(q^{k+1}) - P(0)$ . Thus, $P(q^k)\equiv P(0) \pmod{q^{k+1}}$ . Thus, $b_1 q^k \equiv 0 \pmod{q^{k+1}}$ . By selecting $p>b$ , we win. $\blacksquare$

poggers

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5609 posts

#25 h Mar 20, 2023, 1:15 PM • 1 Y

Y by CT17

Solved with CT17.

We show that if there exists a function $T$ satisfying the problem conditions, then $P$ is constant.

Notice that any $x$ satisfying $T^n(x) = x$ for some $n\ge 1$ must be in a cycle of $T$ . For each positive integer $n$ , let $a_n$ denote the number of cycles length $n$ of $T$ . Define the order of $x$ to denote the smallest $m\ge 1$ such that $T^m(x) = x$ .

There are in total $n\cdot a_n$ elements of order $n$ for all positive integers $n$ , and $P(n)$ consists of all the elements with order dividing $n$ .
Hence $P(n) = \sum d a_d,$ where the sum is over all divisors of $n$ .

For any prime $p$ , $P(p) = p a_p + a_1$ . This implies that $P(p) \equiv P(0)\equiv a_1 \pmod p$ , for all primes $p$ , hence $P(0) = a_1$ . This implies that $a_p = \frac{P(p) - P(0)}{p}$ .

For any primes $p,q$ , we have $P(pq) = pq a_{pq} + p a_p + qa_q + a_1$ . Take the equation mod $p$ . The LHS is $P(pq) \equiv P(0) = a_1 \pmod p$ , and the RHS is $qa_q + a_1 \pmod p$ . Therefore, $qa_q\equiv 0\pmod p$ , so $p \mid a_q \mid P(q)- P(0)$ . Varying $p$ , we find $P(q) - P(0)$ has infinitely many divisors, so $P(q) = P(0)$ .

Since this is true for all primes $q$ , the polynomial $P(x) -P(0)$ has infinitely many roots, so it must be the zero polynomial, which implies $P$ is constant, as desired.

This post has been edited 3 times. Last edited by megarnie, Mar 20, 2023, 1:16 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8877 posts

#26 h Sep 10, 2023, 8:29 PM

Y by

Funny problem.

Suppose that such a function $P$ exists. Let $a_k$ be the number of cycles of length $k$ , so $P(n) = \sum_{d \mid n} da_d.$ Then by Mobius inversion, $na_n = \sum_{d \mid n} \mu(d) P\left(\frac nd\right).$ For $n = p^r$ prime, this implies $p^r \mid P(p) - P(1)$ for all $r$ , thus $P(p) = P(1)$ and $P$ must be constant.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4191 posts

#27 h Jan 20, 2024, 5:37 AM

Y by

Note that a fixed point of $T^n$ is precisely the numbers in cycles of length $d\mid n$ . Let $c(d)$ denote the number of cycles of length $d$ . Thus, we have $\sum_{d\mid n}dc(d)=P(n).$
We claim that this implies that $P$ is constant, which would solve the problem.

\begin{claim}
For any prime $p$ , we have $c(p)=\frac{P(p)-P(1)}{p}.$ \end{claim}

This follows by $c(1)+pc(p)=P(p).$
Of course, the next thing to try is $P(pq)$ .

\begin{claim}
For distinct primes $p$ and $q$ , we have $c(pq)=\frac{P(pq)-P(p)-P(q)+P(1)}{pq}.$ \end{claim}

To prove this, use the the fact that $c(1)+pc(p)+qc(q)+pqc(pq)=P(pq)$ combined with the previous claim. In particular, we have $pq\mid P(pq)-P(p)-P(q)+P(1),$ which implies that $p\mid P(pq)-P(p)-P(q)+P(1).$ Since $p\mid P(pq)-P(p)$ , we have $p\mid P(1)-P(q).$ Thus, $P(1)\equiv P(q)\pmod{p}$ for all primes $p$ and $q$ . Note that since $P(1)$ and $P(q)$ are finite, this holding for all primes $p\neq q$ implies that $P(1)=P(q)$ . Thus, the polynomial reaches the same value of $P(1)$ infinitely often. By polynomial identity theorem, $P$ is constant, and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

198 posts

#28 h Jan 30, 2024, 1:08 PM

Y by

Let $a_n$ be the number of cycles in the graph of $G$ . Then it's clear that $\sum_{d \mid n} d \cdot a_d = P(n)$ for all positive integer $n$ . Then mobius inversion formula yields $a_n \cdot n = \sum_{d \mid n} P(d) \mu(\frac{n}{d})$ . Therefore $P(pq^a) - P(q^a) - P(pq^{a-1}) + P(q^{a-1}) \equiv 0 (pq^a)$ , so $p \mid P(q^a) - P(q^{a-1})$ for all primes $p, q$ . But this is an evident contradiction. $\blacksquare$

This post has been edited 1 time. Last edited by thdnder, Jan 30, 2024, 1:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

419 posts

#29 h Feb 28, 2024, 8:25 PM

Y by

Let $n$ be a positive integer and $p$ be a prime. Let $f(x)$ denote the number of numbers $z$ such that $T^x(z)=z$ holds for $f(x)$ values of $z$ . Note, we have
$P(n)=\sum_{d\mid n}df(d)$ It follows that $p\mid P(np)-P(n)$ and since $p\mid P(np)-P(0)$ , we have that $p\mid P(n)-P(0)$ . Taking $p>|P(n)-P(0)|$ forces $P(n)=P(0)$ which is the constant polynomial, a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1746 posts

awesomeming327.

#30 h Jun 4, 2024, 10:44 PM

Y by

Represent $T$ as a directed graph where each edge $x\to T(x)$ is drawn. Then, $T^n(x)=x$ if and only if $x$ is in a cycle of size $d$ where $d\mid n$ . Let $k$ be the number of loops. Then, for all primes $p$ , $P(p)$ is the number of vertices in cycles of size $p$ , plus $k$ . Therefore, $P(p)\equiv k\pmod p$ for infinitely many $p$ , which means that we can write $P(x)=xQ(x)+k$ for some integer polynomial $Q$ .

Now, fix some prime $p$ and vary $q$ , then we have $P(pq)=pqa+pb+qc+k$ , where $a$ is the number of cycles of size $pq$ , $b$ is the number of cycles of size $p$ , and $c$ is the number of cycles of size $q$ . Then, $pq\mid pqa+pb+qc$ so $pq\mid pb+qc$ which implies $q\mid b$ for all $q$ , which means $b=0$ . This means that $P(x)=k$ for all primes which is a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1560 posts

#31 h Jun 29, 2024, 5:09 PM

Y by

Let $c_i$ the number of integers satisfying that $T^i(x)=x$ and $T^j(x) \ne x$ for all $1 \le j <i$ , then note that if $x$ works so do $T(x), T^2(x), \cdots, T^{i-1}(x)$ and since we said that they are all different we must in fact have $i \mid c_i$ , now the problem condition is that $P(n)=\sum_{d \mid n} c_d$ , now for some $n$ consider primes $p>n$ , then:
$P(pn)=\sum_{d \mid pn} c_d=\sum_{d \mid n} c_d+\sum_{d \mid n} c_{pd}=P(n)+\sum_{d \mid n} c_{pd}$ Now each $c_{pd}$ is divisible by $p$ so we in fact have $p \mid P(pn)-P(n)$ for all $p>n$ primes, but this means $p \mid P(n)-P(0)$ ans by setting a huge prime we get $P(n)=P(0)$ for all positive integers $n$ , thus $P$ is constant, contradiction!.
Therefore no such function $T$ should exist thus we are done :cool:

:cool:

.

This post has been edited 1 time. Last edited by MathLuis, Jun 29, 2024, 5:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

245 posts

#32 h Jul 24, 2024, 11:05 AM

Y by

Assume the contrary and let the \emph{order} of $n$ be defined as the amount of numbers $x$ such that $n$ is the smallest natural number such that $T^n(x)=x$ , and let it be denoted by $\text{ord}(n)$ . One can easily see that $n \mid \text{ord}(n) \text{ and } P= \text{ord} \ast 1$ And hence let $q$ be any prime and we get
$\bullet$ $P(1)=\text{ord}(1)$ .
$\bullet$ $P(q)=\text{ord}(1)+\text{ord}(q) \implies q \mid P(0)-P(1) \iff P(0)=P(1)$ .
And so
$\begin{align*} \implies & P(qr)=\text{ord}(1)+\text{ord}(q)+\text{ord}(r)+\text{ord}(qr)\\ \implies & qr \mid P(qr)+P(1)-P(q)-P(r)\\ \implies & q \mid P(r)-P(0) \end{align*}$ for any two distinct primes $q$ , $r$ ; and we easily get that $P(X) \equiv P(0)$ , which is a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

774 posts

#33 h Aug 22, 2024, 12:09 AM

Y by

You can actually prove it's zero not just for the primes.

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

302 posts

N3bula

#34 h Oct 14, 2024, 9:04 AM

Y by

Let, $g_T(i)$ be the number of values $x$ such that $T^i(x)=x$ and $i$ is the minimal value for which that occurs, clearly we have that $n\mid g_T(n)$ ,
thus let $g_T(1)=k$ , now let $f_T(i)$ denote the number of values such that $T^i(x)=x$ , thus we get that $f_T(p^2)\equiv k\pmod p^2$ for some $g_T(p)\neq 0$ ,
as we can't have infinetly many values where $g_T(p)=0$ . Thus we get that $p^2\mid g_T(p)$ , which because of infintely many primes having that property
means the minimal power term that isnt the constant term must be at least $2$ , and by repeating this argument we get that the minimal power term that
isnt the constant term is abitrarily large which is a contradicition.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1930 posts

#35 h Nov 8, 2024, 3:54 PM

Y by

This problem is quite contrived, since we really only need to consider the cycles of $T$ . Say there are $a_n$ cycles of length $n$ , then we get
$\sum_{d\mid n}da_d=P(n).$ Consider this for $n$ a prime. Then $a_1+pa_p=P(p)$ , so $P(0)\equiv a_1\pmod p$ . This is true for all $p$ , so $P(0)=a_1$ . Thus we may set $a_1=0$ and $P(0)=0$ (since $a_1$ and $P(0)$ always appear in the equation).

Now we will prove that for every number $n$ , $a_n=0$ . We will do this by strong inducting on $\Omega(n)$ . So say we proved it for when $\Omega(n)=m$ , now consider $\Omega(n)=m+1$ . Consider a prime $p\nmid n$ , using $pn$ in the big equation has the RHS divisible by $p$ and the LHS is just $na_n$ mod $p$ . So $p\mid na_n$ for all $p\nmid n$ , so $a_n=0$ .

Thus $P$ is constant, contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

183 posts

#36 h Jan 16, 2025, 12:22 PM • 1 Y

Y by L13832

Why was this so easy

This post has been edited 1 time. Last edited by lelouchvigeo, Jan 16, 2025, 12:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

774 posts

#37 h Jan 27, 2025, 6:12 PM

Y by

Subjective Rating (MOHs)
Please contact westskigamer@gmail.com if there is an error with any of my solution for cash bounties by 3/18/2025.

Reminds me of 2D Prefix Sums

Attachments:

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a