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 "2020 OIM Problems/Problem 2"

(Created page with "== Problem == For each positive integer <math>n</math>, define <math>T_n</math> as the smallest positive integer such that <math>1 + 2 + \cdots + T_n</math> is a multiple of <...")
 
(solution)
Line 5: Line 5:
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
<i>Note the elementary property that will be used without proof: for all positive integers <math>n</math>:</i>
 +
<cmath>1+2+\ldots+n=\frac{1}{2}n(n+1)</cmath>
 +
 
 +
We claim that the only possible <math>m</math> are numbers of the form <math>\boxed{2^x}</math>, where <math>x</math> is a nonnegative integer. First, we show that these numbers do in fact satisfy the condition. By formula, we have <math>\frac{1}{2}T_n(T_n+1)=2^x</math>; thus <math>T_n(T_n+1)=2^{x+1}</math>. Only one of <math>T_n</math> or <math>T_n+1</math> is even.
 +
 
 +
If <math>T_n</math> is even, then we must have <math>2^{x+1}|T_n</math>, which is clearly only possible if <math>T_n\ge2^{x+1}>2^{x+1}-1</math>. If <math>T_n+1</math> is even, then we must have <math>T_n+1\ge2^{x+1}</math>; thus <math>T_n\ge2^{x+1}-1</math>. For all nonnegative <math>x</math>, it is easily shown that <math>2^{x+1}-1\ge2^x</math>; thus,
 +
<cmath>T_n\ge2^{x+1}-1\ge2^x=m</cmath>
 +
so these <math>m</math> satisfy the condition regardless of the parity of <math>T_n</math>.
 +
 
 +
Next, we show that these are the only possible <math>m</math>. First, assume that <math>m=p^k</math> such that <math>p</math> is an odd prime and <math>k</math> is a positive integer. Clearly if <math>T_m=m-1</math>, then the property is satisfied (although this may not be minimal) since we must have <math>2|(m-1)</math>; thus these cases are eliminated. Then consider <math>m</math> as any other odd number. Let <math>m=ab</math> for relatively prime odd integers <math>a,b>1</math>; this is possible since we already considered odd <math>m</math> with only one prime factor. Consider all nonnegative integers <math>\alpha</math> such that
 +
<cmath>\alpha\equiv0\pmod{a}</cmath>
 +
<cmath>\alpha\equiv-1\pmod{b}</cmath>
 +
 
 +
By the [[Chinese Remainder Theorem]], there exists some <math>\alpha\in[0,ab-1]</math> such that the above holds. Clearly <math>\alpha=0</math> does not work, so there exists some unique <math>\alpha\in[1,m-1]</math>; let this be <math>\alpha_0</math>. Notice that <math>\frac{1}{2}\alpha_0(\alpha_0+1)</math> would then be divisible by <math>m=ab</math>, so <math>T_n=\alpha_0</math> would satisfy the property (although it may not be minimized); thus we must have <math>T_n\le\alpha_0<m</math>, eliminating this case.
 +
 
 +
Finally, we consider even <math>m</math>. Let <math>m=2^y\cdot t</math> for positive integers <math>y,t</math> such that <math>t\ne1</math> is odd (because we already showed that <math>t=1</math> works). Then <math>2^y</math> and <math>t</math> are clearly relatively prime.
 +
 
 +
Let <math>\beta_1,\beta_2</math> be nonnegative integers in the interval <math>[1,2^{y+1}t-1]</math> such that
 +
<cmath>\beta_1\equiv0\pmod{2^{y+1}}</cmath>
 +
<cmath>\beta_1\equiv-1\pmod{t}</cmath>
 +
<cmath>\beta_2\equiv-1\pmod{2^{y+1}}</cmath>
 +
<cmath>\beta_2\equiv0\pmod{t}</cmath>
 +
 
 +
Again, since <math>\beta_1=0</math> or <math>\beta_2=0</math> clearly do not satisfy the above, then by the Chinese Remainder Theorem, there will always exist some unique integers <math>\beta_1,\beta_2</math> in the interval <math>[1,2^{y+1}t-1]</math>, so we are able to define them as such above. Next, adding the first/third congruences and the second/fourth congruences:
 +
<cmath>\beta_1+\beta_2\equiv-1\pmod{2^{y+1}}</cmath>
 +
<cmath>\beta_1+\beta_2\equiv-1\pmod{t}</cmath>
 +
Notice that
 +
<cmath>\beta_1+\beta_2\equiv-1\pmod{2^{y+1}t}</cmath>
 +
satisfies this system of congruences; by the Chinese Remainder Theorem, this solution is unique. Thus,
 +
<cmath>\beta_1+\beta_2+1\equiv0\pmod{2^{y+1}t}</cmath>
 +
However, since <math>\beta_1,\beta_2\in[1,2^{y+1}t-1]</math>, this implies that <math>\beta_1+\beta_2+1\in[3,2\cdot2^{y+1}-1]</math>. From the above congruence, the only multiple of <math>2^{y+1}t</math> in this interval is <math>2^{y+1}t</math> itself; thus,
 +
<cmath>\beta_1+\beta_2+1=2^{y+1}t</cmath>
 +
<cmath>\Rightarrow\beta_1+\beta_2=2^{y+1}t-1</cmath>
 +
Assume for the sake of contradiction that both <math>\beta_1,\beta_2<2^yt-1</math>. Then <math>\beta_1+\beta_2<2^{y+1}t-2<2^{y+1}t-1</math>, clearly a contradiction. Thus at least one of <math>\beta_1,\beta_2\ge2^yt-1</math>, implying that at least one of <math>\beta_1,\beta_2\ge m-1</math>. Assume that <math>\beta_1\ge m-1</math>; then <math>\frac{1}{2}\beta_1(\beta_1+1)</math> is divisible by <math>m=2^yt</math> from our congruences above, so setting <math>T_n=\beta_1</math> would suffice (we do not have to prove minimality); thus <math>T_n\le\beta_1</math>; the same goes for <math>\beta_2</math> if <math>\beta_2\ge m-1</math>. As a result, this case is also eliminated, so we are done.
 +
 
 +
~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406]
  
 
== See also ==
 
== See also ==
 
[[OIM Problems and Solutions]]
 
[[OIM Problems and Solutions]]

Revision as of 22:06, 8 April 2025

Problem

For each positive integer $n$, define $T_n$ as the smallest positive integer such that $1 + 2 + \cdots + T_n$ is a multiple of $n$. For example, $T_5 = 4$ since $1$, $1 + 2$ and $1 + 2 + 3$ are not multiples of $5$, but $1 + 2 + 3 + 4$ is a multiple of $5$. Find all positive integers $m$ such that $T_m \ge m$.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

Note the elementary property that will be used without proof: for all positive integers $n$: \[1+2+\ldots+n=\frac{1}{2}n(n+1)\]

We claim that the only possible $m$ are numbers of the form $\boxed{2^x}$, where $x$ is a nonnegative integer. First, we show that these numbers do in fact satisfy the condition. By formula, we have $\frac{1}{2}T_n(T_n+1)=2^x$; thus $T_n(T_n+1)=2^{x+1}$. Only one of $T_n$ or $T_n+1$ is even.

If $T_n$ is even, then we must have $2^{x+1}|T_n$, which is clearly only possible if $T_n\ge2^{x+1}>2^{x+1}-1$. If $T_n+1$ is even, then we must have $T_n+1\ge2^{x+1}$; thus $T_n\ge2^{x+1}-1$. For all nonnegative $x$, it is easily shown that $2^{x+1}-1\ge2^x$; thus, \[T_n\ge2^{x+1}-1\ge2^x=m\] so these $m$ satisfy the condition regardless of the parity of $T_n$.

Next, we show that these are the only possible $m$. First, assume that $m=p^k$ such that $p$ is an odd prime and $k$ is a positive integer. Clearly if $T_m=m-1$, then the property is satisfied (although this may not be minimal) since we must have $2|(m-1)$; thus these cases are eliminated. Then consider $m$ as any other odd number. Let $m=ab$ for relatively prime odd integers $a,b>1$; this is possible since we already considered odd $m$ with only one prime factor. Consider all nonnegative integers $\alpha$ such that \[\alpha\equiv0\pmod{a}\] \[\alpha\equiv-1\pmod{b}\]

By the Chinese Remainder Theorem, there exists some $\alpha\in[0,ab-1]$ such that the above holds. Clearly $\alpha=0$ does not work, so there exists some unique $\alpha\in[1,m-1]$; let this be $\alpha_0$. Notice that $\frac{1}{2}\alpha_0(\alpha_0+1)$ would then be divisible by $m=ab$, so $T_n=\alpha_0$ would satisfy the property (although it may not be minimized); thus we must have $T_n\le\alpha_0<m$, eliminating this case.

Finally, we consider even $m$. Let $m=2^y\cdot t$ for positive integers $y,t$ such that $t\ne1$ is odd (because we already showed that $t=1$ works). Then $2^y$ and $t$ are clearly relatively prime.

Let $\beta_1,\beta_2$ be nonnegative integers in the interval $[1,2^{y+1}t-1]$ such that \[\beta_1\equiv0\pmod{2^{y+1}}\] \[\beta_1\equiv-1\pmod{t}\] \[\beta_2\equiv-1\pmod{2^{y+1}}\] \[\beta_2\equiv0\pmod{t}\]

Again, since $\beta_1=0$ or $\beta_2=0$ clearly do not satisfy the above, then by the Chinese Remainder Theorem, there will always exist some unique integers $\beta_1,\beta_2$ in the interval $[1,2^{y+1}t-1]$, so we are able to define them as such above. Next, adding the first/third congruences and the second/fourth congruences: \[\beta_1+\beta_2\equiv-1\pmod{2^{y+1}}\] \[\beta_1+\beta_2\equiv-1\pmod{t}\] Notice that \[\beta_1+\beta_2\equiv-1\pmod{2^{y+1}t}\] satisfies this system of congruences; by the Chinese Remainder Theorem, this solution is unique. Thus, \[\beta_1+\beta_2+1\equiv0\pmod{2^{y+1}t}\] However, since $\beta_1,\beta_2\in[1,2^{y+1}t-1]$, this implies that $\beta_1+\beta_2+1\in[3,2\cdot2^{y+1}-1]$. From the above congruence, the only multiple of $2^{y+1}t$ in this interval is $2^{y+1}t$ itself; thus, \[\beta_1+\beta_2+1=2^{y+1}t\] \[\Rightarrow\beta_1+\beta_2=2^{y+1}t-1\] Assume for the sake of contradiction that both $\beta_1,\beta_2<2^yt-1$. Then $\beta_1+\beta_2<2^{y+1}t-2<2^{y+1}t-1$, clearly a contradiction. Thus at least one of $\beta_1,\beta_2\ge2^yt-1$, implying that at least one of $\beta_1,\beta_2\ge m-1$. Assume that $\beta_1\ge m-1$; then $\frac{1}{2}\beta_1(\beta_1+1)$ is divisible by $m=2^yt$ from our congruences above, so setting $T_n=\beta_1$ would suffice (we do not have to prove minimality); thus $T_n\le\beta_1$; the same goes for $\beta_2$ if $\beta_2\ge m-1$. As a result, this case is also eliminated, so we are done.

~ eevee9406

See also

OIM Problems and Solutions

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_OIM_Problems/Problem_2&oldid=246348"