Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2025 USAJMO Problems/Problem 1"
(→‎Solution)
Line 5: Line 5:
  
 
== Solution ==
 
== Solution ==
−
Note that <math>c=f(a)-f(a+1)</math> makes <math>g(a)=g(a+1),</math> so for all <math>c=f(a)-f(a+1)</math> we have that <math>g(x)</math> is not bijective. If there are infinitely many possible values of <math>c,</math> we are done. Otherwise, there are only finitely many possible values of <math>f(a)-f(a+1)</math> so there are only finitely many possible values of <math>-(f(a)-f(a+1))=f(a+1)-f(a).</math> This means there is a minimum <math>d</math> of <math>f(a+1)-f(a).</math> It is clear for <math>x>0</math> that
+
Assume the contrary. Note that <math>c=f(a)-f(a+1)</math> makes <math>g(a)=g(a+1),</math> so for all <math>c=f(a)-f(a+1)</math> we have that <math>g(x)</math> is not bijective. If there are infinitely many possible values of <math>c,</math> we are done. Otherwise, there are only finitely many possible values of <math>f(a)-f(a+1)</math> so there are only finitely many possible values of <math>-(f(a)-f(a+1))=f(a+1)-f(a).</math> This means there is a minimum <math>d</math> of <math>f(a+1)-f(a).</math> It is clear for <math>x>0</math> that
 
<cmath>f(x)=f(0)+\sum_{a=0}^{x-1}(f(a+1)-f(a))\ge dx+f(0)</cmath>
 
<cmath>f(x)=f(0)+\sum_{a=0}^{x-1}(f(a+1)-f(a))\ge dx+f(0)</cmath>
 
and for <math>x<0</math> that
 
and for <math>x<0</math> that

Revision as of 14:30, 14 April 2025

Problem

Let $\mathbb Z$ be the set of integers, and let $f\colon \mathbb Z \to \mathbb Z$ be a function. Prove that there are infinitely many integers $c$ such that the function $g\colon \mathbb Z \to \mathbb Z$ defined by $g(x) = f(x) + cx$ is not bijective. Note: A function $g\colon \mathbb Z \to \mathbb Z$ is bijective if for every integer $b$, there exists exactly one integer $a$ such that $g(a) = b$.

Solution

Assume the contrary. Note that $c=f(a)-f(a+1)$ makes $g(a)=g(a+1),$ so for all $c=f(a)-f(a+1)$ we have that $g(x)$ is not bijective. If there are infinitely many possible values of $c,$ we are done. Otherwise, there are only finitely many possible values of $f(a)-f(a+1)$ so there are only finitely many possible values of $-(f(a)-f(a+1))=f(a+1)-f(a).$ This means there is a minimum $d$ of $f(a+1)-f(a).$ It is clear for $x>0$ that \[f(x)=f(0)+\sum_{a=0}^{x-1}(f(a+1)-f(a))\ge dx+f(0)\] and for $x<0$ that \[f(x)=f(0)-\sum_{a=x}^{-1}\le dx+f(0).\] Then, let $c>-d+3$ be an integer. We have for integers $x>0,$ $x\ge 1,$ so \[g(x)=f(x)+cx\ge (d+c)x+f(0)>3x+f(0)>3+f(0),\] if $x=0$ we have $g(x)=f(0),$ and if $x<0$ we have \[g(x)=f(x)+cx\le (d+c)x+f(0)<3x+f(0)<f(0).\] This means that there is no $a$ such that $g(a)=f(0)+1,$ so $g(x)$ is not bijective.$\blacksquare$

~BS2012

See Also

2025 USAJMO (Problems • Resources)
Preceded by
First Problem 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_USAJMO_Problems/Problem_1&oldid=246636"