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 "1995 USAMO Problems/Problem 1"

m (→‎Solution)
m (→‎Solution)
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
==Problem 1==
+
==Problem==
  
 
Let <math>\, p \,</math> be an odd prime.  The sequence <math>(a_n)_{n \geq 0}</math> is defined as follows: <math>\, a_0 = 0, </math> <math>a_1 = 1, \, \ldots, \, a_{p-2} = p-2 \,</math> and, for all <math>\, n \geq p-1, \,</math> <math>\, a_n \,</math> is the least positive integer that does not form an arithmetic sequence of length <math>\, p \,</math> with any of the preceding terms. Prove that, for all <math>\, n, \,</math> <math>\, a_n \,</math> is the number obtained by writing <math>\, n \,</math> in base <math>\, p-1 \,</math> and reading the result in base <math>\, p</math>.
 
Let <math>\, p \,</math> be an odd prime.  The sequence <math>(a_n)_{n \geq 0}</math> is defined as follows: <math>\, a_0 = 0, </math> <math>a_1 = 1, \, \ldots, \, a_{p-2} = p-2 \,</math> and, for all <math>\, n \geq p-1, \,</math> <math>\, a_n \,</math> is the least positive integer that does not form an arithmetic sequence of length <math>\, p \,</math> with any of the preceding terms. Prove that, for all <math>\, n, \,</math> <math>\, a_n \,</math> is the number obtained by writing <math>\, n \,</math> in base <math>\, p-1 \,</math> and reading the result in base <math>\, p</math>.
Line 13: Line 13:
  
  
−
Lemma 1: for a arithmetic sequence of length <math>\, p \,</math> to exist, there must be a number in the sequence with <math>(p-1)</math> as a digit.
+
Lemma 1: for an arithmetic sequence of length <math>\, p \,</math> to exist, there must be a number in the sequence with <math>(p-1)</math> as a digit.
  
 
A arithmetic sequence of length <math>\, p \,</math> can be represented as
 
A arithmetic sequence of length <math>\, p \,</math> can be represented as
Line 41: Line 41:
  
  
−
lemma 2: Any term contains the digit <math>p-1</math> will form a arithmatic sequence of length-p with preceding terms
+
Lemma 2: Any term containing the digit <math>p-1</math> will form an arithmetic sequence of length-p with preceding terms
  
 
let <math>p-1</math> be the <math>x^{th}</math> digit from the right (There may be more than 1 <math>(p-1)</math>)
 
let <math>p-1</math> be the <math>x^{th}</math> digit from the right (There may be more than 1 <math>(p-1)</math>)
  
−
<math>a=</math>the number with all <math>(p-1)</math> replaced by 0 (e.g: <math>p=7</math>, the number<math>=1361264</math>, then <math>a=1301204</math>)
+
<math>a=</math> the number with all <math>(p-1)</math> replaced by 0 (e.g: <math>p=7</math>, the number<math>=1361264</math>, then <math>a=1301204</math>)
  
−
<math>d=\sum10^{x-1}</math> (for all <math>x</math>'s)
+
<math>d=\sum p^{x-1}</math> (for all <math>x</math>'s)
  
 
<math>a,a+d,a+2d,\cdots,a+(p-2)d</math> all precede <math>a_n</math>, thus, <math>a+(p-1)d</math> can't be in the sequence <math>(a_n)_{n \geq 0}</math>
 
<math>a,a+d,a+2d,\cdots,a+(p-2)d</math> all precede <math>a_n</math>, thus, <math>a+(p-1)d</math> can't be in the sequence <math>(a_n)_{n \geq 0}</math>
  
−
Therefore, any term contains the digit <math>p-1</math> can't be a term in the sequence <math>{(a_n)}_{n\ge0}</math>
+
Therefore, any term containing the digit <math>p-1</math> can't be a term in the sequence <math>{(a_n)}_{n\ge0}</math>
  
  
Line 57: Line 57:
 
Since the digit <math>p-1</math> won't appear (lemma 2) and as long as it doesn't appear, the arithmetic sequence of length <math>\, p \,</math> won't be formed (lemma 1), and <math>a_n</math> must be as small as possible,  
 
Since the digit <math>p-1</math> won't appear (lemma 2) and as long as it doesn't appear, the arithmetic sequence of length <math>\, p \,</math> won't be formed (lemma 1), and <math>a_n</math> must be as small as possible,  
  
−
for all <math>\, n, \,</math> <math>\, a_n \,</math> is the number obtained by writing <math>\, n \,</math> in base <math>\, p-1 \,</math> and reading the result in base <math>\, p</math>.
+
Therefore, for all <math>\, n, \,</math> <math>\, a_n \,</math> is the number obtained by writing <math>\, n \,</math> in base <math>\, p-1 \,</math> and reading the result in base <math>\, p</math>.
  
−
== Resources ==
+
== See Also ==
  
 
{{USAMO box|year=1995|before=First Question|num-a=2}}
 
{{USAMO box|year=1995|before=First Question|num-a=2}}
 
* [http://www.artofproblemsolving.com/viewtopic.php?p=136808#136808 Discussion on AoPS/MathLinks]
 
* [http://www.artofproblemsolving.com/viewtopic.php?p=136808#136808 Discussion on AoPS/MathLinks]
 +
{{MAA Notice}}
 +
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 17:23, 22 March 2024

Problem

Let $\, p \,$ be an odd prime. The sequence $(a_n)_{n \geq 0}$ is defined as follows: $\, a_0 = 0,$ $a_1 = 1, \, \ldots, \, a_{p-2} = p-2 \,$ and, for all $\, n \geq p-1, \,$ $\, a_n \,$ is the least positive integer that does not form an arithmetic sequence of length $\, p \,$ with any of the preceding terms. Prove that, for all $\, n, \,$ $\, a_n \,$ is the number obtained by writing $\, n \,$ in base $\, p-1 \,$ and reading the result in base $\, p$.

Solution

I have to make the assumption that $a_{n+1}>a_{n}$ (without this assumption, I can have the sequence

${1,\cdots,p-2,1,1,\cdots,1,2,1,\cdots}$)

All of the following work are in base $p$ otherwise stated


Lemma 1: for an arithmetic sequence of length $\, p \,$ to exist, there must be a number in the sequence with $(p-1)$ as a digit.

A arithmetic sequence of length $\, p \,$ can be represented as

$a,a+d,a+2d,\cdots,a+(p-1)d$

Since no number repeats, $d\neq0$. Thus, d must have a rightmost non-zero digits, and every term in the sequence $0,d,2d,\cdots,(p-1)d$ have the same number of tailing zeros, let's say there are $x$ tailing zeros.

and let $\dfrac{{0,d,2d,\cdots,(p-1)d}}{p^x}=S$

$S\equiv{1,2,...,(p-1)}(mod)p$ since p is an odd prime and the operation divide by $p^x$ has remove all factors of p in S

Thus, there must be a number with $(p-1)$ as a digit if a length-p sequence exist.


Now, I'm going to prove the statement by strong induction.

I'm going to assume that for all $\, k \,$ less than $\, n \,$

$\, a_k \,$ is the number obtained by writing $\, k \,$ in base $\, p-1 \,$ and reading the result in base $\, p$.

(which is true for $n=p-2$ already)

Or in another word, the terms precede $a_n$ contains all number less than $n$ written in base $\, p-1 \,$ and reading the result in base $\, p$.


Lemma 2: Any term containing the digit $p-1$ will form an arithmetic sequence of length-p with preceding terms

let $p-1$ be the $x^{th}$ digit from the right (There may be more than 1 $(p-1)$)

$a=$ the number with all $(p-1)$ replaced by 0 (e.g: $p=7$, the number$=1361264$, then $a=1301204$)

$d=\sum p^{x-1}$ (for all $x$'s)

$a,a+d,a+2d,\cdots,a+(p-2)d$ all precede $a_n$, thus, $a+(p-1)d$ can't be in the sequence $(a_n)_{n \geq 0}$

Therefore, any term containing the digit $p-1$ can't be a term in the sequence ${(a_n)}_{n\ge0}$


Since the digit $p-1$ won't appear (lemma 2) and as long as it doesn't appear, the arithmetic sequence of length $\, p \,$ won't be formed (lemma 1), and $a_n$ must be as small as possible,

Therefore, for all $\, n, \,$ $\, a_n \,$ is the number obtained by writing $\, n \,$ in base $\, p-1 \,$ and reading the result in base $\, p$.

See Also

1995 USAMO (Problems • Resources)
Preceded by
First Question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1995_USAMO_Problems/Problem_1&oldid=217252"