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 "1989 AIME Problems/Problem 14"

(→‎Solution)
(wikify)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Given a positive integer <math>n^{}_{}</math>, it can be shown that every complex number of the form <math>r+si^{}_{}</math>, where <math>r^{}_{}</math> and <math>s^{}_{}</math> are integers, can be uniquely expressed in the base <math>-n+i^{}_{}</math> using the integers <math>1,2^{}_{},\ldots,n^2</math> as digits. That is, the equation
+
Given a positive [[integer]] <math>n^{}_{}</math>, it can be shown that every [[complex number]] of the form <math>r+si^{}_{}</math>, where <math>r^{}_{}</math> and <math>s^{}_{}</math> are integers, can be uniquely expressed in the base <math>-n+i^{}_{}</math> using the integers <math>1,2^{}_{},\ldots,n^2</math> as digits. That is, the equation
 
<center><math>r+si=a_m(-n+i)^m+a_{m-1}(-n+i)^{m-1}+\cdots +a_1(-n+i)+a_0</math></center>
 
<center><math>r+si=a_m(-n+i)^m+a_{m-1}(-n+i)^{m-1}+\cdots +a_1(-n+i)+a_0</math></center>
 
is true for a unique choice of non-negative integer <math>m^{}_{}</math> and digits <math>a_0,a_1^{},\ldots,a_m</math> chosen from the set <math>\{0^{}_{},1,2,\ldots,n^2\}</math>, with <math>a_m\ne 0^{}^{}</math>. We write
 
is true for a unique choice of non-negative integer <math>m^{}_{}</math> and digits <math>a_0,a_1^{},\ldots,a_m</math> chosen from the set <math>\{0^{}_{},1,2,\ldots,n^2\}</math>, with <math>a_m\ne 0^{}^{}</math>. We write
 
<center><math>r+si=(a_ma_{m-1}\ldots a_1a_0)_{-n+i}</math></center>
 
<center><math>r+si=(a_ma_{m-1}\ldots a_1a_0)_{-n+i}</math></center>
 
to denote the base <math>-n+i^{}_{}</math> expansion of <math>r+si^{}_{}</math>. There are only finitely many integers <math>k+0i^{}_{}</math> that have four-digit expansions
 
to denote the base <math>-n+i^{}_{}</math> expansion of <math>r+si^{}_{}</math>. There are only finitely many integers <math>k+0i^{}_{}</math> that have four-digit expansions
−
<center><math>k=(a_3a_2a_1a_0)_{-3+i^{}_{}}~~~~a_3\ne 0.</math></center>
+
<center><math>k=(a_3a_2a_1a_0)_{-3+i^{}_{}}~~</math><math>~~a_3\ne 0.</math></center>
 
Find the sum of all such <math>k^{}_{}</math>.
 
Find the sum of all such <math>k^{}_{}</math>.
  
Line 13: Line 13:
 
<math>(-3+i)^1=-3+i ; (-3+i)^2=8-6i ; (-3+i)^3=-18+26i</math>
 
<math>(-3+i)^1=-3+i ; (-3+i)^2=8-6i ; (-3+i)^3=-18+26i</math>
  
−
So we need to solve the [[diophantine equation]] <math>a_1-6a_2+26a_3=0</math>.
+
So we need to solve the [[diophantine equation]] <math>a_1-6a_2+26a_3=0 \Longrightarrow a_1-6a_2=-26a_3</math>.
−
 
 
−
<math>a_1-6a_2=-26a_3</math>
 
  
 
The minimum the left hand side can go is -54, so <math>a_3\leq 2</math>, so we try cases:
 
The minimum the left hand side can go is -54, so <math>a_3\leq 2</math>, so we try cases:
  
−
Case 1: <math>a_3=2</math>
+
*Case 1: <math>a_3=2</math>
−
 
+
:The only solution to that is <math>(a_1, a_2, a_3)=(2,9,2)</math>.
−
The only solution to that is <math>(a_1, a_2, a_3)=(2,9,2)</math>.
+
*Case 2: <math>a_3=1</math>
−
 
+
:The only solution to that is <math>(a_1, a_2, a_3)=(4,5,1)</math>.
−
Case 2: <math>a_3=1</math>
+
*Case 3: <math>a_3=0</math>
−
 
+
:<math>a_3</math> cannot be 0, or else we do not have a four digit number.
−
The only solution to that is <math>(a_1, a_2, a_3)=(4,5,1)</math>.
 
−
 
 
−
Case 3: <math>a_3=0</math>
 
−
 
 
−
<math>a_3</math> cannot be 0, or else we do not have a four digit number.
 
  
−
So we have the four digit integers <math>(292a_0)_{-3+i}</math> and <math>(154a_0)_{-3+i}</math>, and we need to find the sum of all integers k that can be expressed by one of those.
+
So we have the four digit integers <math>(292a_0)_{-3+i}</math> and <math>(154a_0)_{-3+i}</math>, and we need to find the sum of all integers <math>k</math> that can be expressed by one of those.
  
 
<math>(292a_0)_{-3+i}</math>:
 
<math>(292a_0)_{-3+i}</math>:
  
−
We plug the first three digits into base 10 to get <math>30+a_0</math>. The sum of the integers k in that form is 345.
+
We plug the first three digits into base 10 to get <math>30+a_0</math>. The sum of the integers <math>k</math> in that form is <math>345</math>.
  
 
<math>(154a_0)_{-3+i}</math>:
 
<math>(154a_0)_{-3+i}</math>:
  
−
We plug the first three digits into base 10 to get <math>10+a_0</math>. The sum of the integers k in that form is 145.
+
We plug the first three digits into base 10 to get <math>10+a_0</math>. The sum of the integers <math>k</math> in that form is <math>145</math>. The answer is <math>345+145=\boxed{490}</math>.
−
 
 
−
345+145=<math>\boxed{490}</math>
 
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=1989|num-b=13|num-a=15}}
 
{{AIME box|year=1989|num-b=13|num-a=15}}
 +
 +
[[Category:Intermediate Complex Numbers Problems]]

Revision as of 13:15, 25 November 2007

Problem

Given a positive integer $n^{}_{}$, it can be shown that every complex number of the form $r+si^{}_{}$, where $r^{}_{}$ and $s^{}_{}$ are integers, can be uniquely expressed in the base $-n+i^{}_{}$ using the integers $1,2^{}_{},\ldots,n^2$ as digits. That is, the equation

$r+si=a_m(-n+i)^m+a_{m-1}(-n+i)^{m-1}+\cdots +a_1(-n+i)+a_0$

is true for a unique choice of non-negative integer $m^{}_{}$ and digits $a_0,a_1^{},\ldots,a_m$ chosen from the set $\{0^{}_{},1,2,\ldots,n^2\}$, with $a_m\ne 0^{}^{}$ (Error compiling LaTeX. Unknown error_msg). We write

$r+si=(a_ma_{m-1}\ldots a_1a_0)_{-n+i}$

to denote the base $-n+i^{}_{}$ expansion of $r+si^{}_{}$. There are only finitely many integers $k+0i^{}_{}$ that have four-digit expansions

$k=(a_3a_2a_1a_0)_{-3+i^{}_{}}~~$$~~a_3\ne 0.$

Find the sum of all such $k^{}_{}$.

Solution

First, we find the first three powers of $-3+i$:

$(-3+i)^1=-3+i ; (-3+i)^2=8-6i ; (-3+i)^3=-18+26i$

So we need to solve the diophantine equation $a_1-6a_2+26a_3=0 \Longrightarrow a_1-6a_2=-26a_3$.

The minimum the left hand side can go is -54, so $a_3\leq 2$, so we try cases:

  • Case 1: $a_3=2$
The only solution to that is $(a_1, a_2, a_3)=(2,9,2)$.
  • Case 2: $a_3=1$
The only solution to that is $(a_1, a_2, a_3)=(4,5,1)$.
  • Case 3: $a_3=0$
$a_3$ cannot be 0, or else we do not have a four digit number.

So we have the four digit integers $(292a_0)_{-3+i}$ and $(154a_0)_{-3+i}$, and we need to find the sum of all integers $k$ that can be expressed by one of those.

$(292a_0)_{-3+i}$:

We plug the first three digits into base 10 to get $30+a_0$. The sum of the integers $k$ in that form is $345$.

$(154a_0)_{-3+i}$:

We plug the first three digits into base 10 to get $10+a_0$. The sum of the integers $k$ in that form is $145$. The answer is $345+145=\boxed{490}$.

See also

1989 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 13 		Followed by
Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1989_AIME_Problems/Problem_14&oldid=20232"