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 "1983 AIME Problems/Problem 10"

(→‎Solution)
m (→‎Solution 4 (Easy casework))
 
(14 intermediate revisions by 8 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
The numbers <math>1447</math>, <math>1005</math>, and <math>1231</math> have something in common. Each is a four-digit number beginning with <math>1</math> that has exactly two identical digits. How many such numbers are there?
+
The numbers <math>1447</math>, <math>1005</math> and <math>1231</math> have something in common: each is a <math>4</math>-digit number beginning with <math>1</math> that has exactly two identical digits. How many such numbers are there?
  
−
== Solution ==
+
==Solution 1==
−
Suppose the two identical [[digit]]s are both one. Since the thousands digits must be one, the other one can be in only one of three digits,
+
Suppose that the two identical digits are both <math>1</math>. Since the thousands digit must be <math>1</math>, only one of the other three digits can be <math>1</math>. This means the possible forms for the number are
  
−
<div style="text-align:center;"><math>11xy,\qquad 1x1y,\qquad1xy1,\qquad11yx,\qquad1y1x,\qquad1yx1</math></div>
+
<div style="text-align:center;"><math>11xy,\qquad 1x1y,\qquad1xy1</math></div>
  
−
Because the number must have exactly two identical digits, <math>x\neq y</math>, <math>x\neq1</math>, and <math>y\neq1</math>. Hence, there are <math>6\cdot9\cdot8=432</math> numbers of this form.
+
Because the number must have exactly two identical digits, <math>x\neq y</math>, <math>x\neq1</math>, and <math>y\neq1</math>. Hence, there are <math>3\cdot9\cdot8=216</math> numbers of this form.
  
−
Suppose the two identical digits are not one. Therefore, consider the following possibilities,
+
Now suppose that the two identical digits are not <math>1</math>. Reasoning similarly to before, we have the following possibilities:
  
 
<div style="text-align:center;"><math>1xxy,\qquad1xyx,\qquad1yxx.</math></div>
 
<div style="text-align:center;"><math>1xxy,\qquad1xyx,\qquad1yxx.</math></div>
Line 15: Line 15:
 
Again, <math>x\neq y</math>, <math>x\neq 1</math>, and <math>y\neq 1</math>. There are <math>3\cdot9\cdot8=216</math> numbers of this form.
 
Again, <math>x\neq y</math>, <math>x\neq 1</math>, and <math>y\neq 1</math>. There are <math>3\cdot9\cdot8=216</math> numbers of this form.
  
−
Thus, the desired answer is <math>432+216=\boxed{648}</math>.
+
Thus the answer is <math>216+216=\boxed{432}</math>.
 +
 
 +
==Solution 2==
 +
Consider a sequence of <math>4</math> digits instead of a <math>4</math>-digit number. Only looking at the sequences which have one digit repeated twice, we notice that the probability that the sequence starts with 1 is <math>\frac{1}{10}</math>. This means we can find all possible sequences with one digit repeated twice, and then divide by <math>10</math>.
 +
 
 +
If we let the three distinct digits of the sequence be <math>a, b,</math> and <math>c</math>, with <math>a</math> repeated twice, we can make a table with all possible sequences:
 +
 
 +
<cmath>\begin{tabular}{ccc}
 +
aabc & abac & abca \\
 +
baac & baca & \\
 +
bcaa && \\
 +
\end{tabular} </cmath>
 +
 
 +
There are <math>6</math> possible sequences.
 +
 
 +
Next, we can see how many ways we can pick <math>a</math>, <math>b</math>, and <math>c</math>. This is <math>10(9)(8) = 720</math>, because there are <math>10</math> digits, from which we need to choose <math>3</math> with regard to order. This means there are <math>720(6) = 4320</math> sequences of length <math>4</math> with one digit repeated. We divide by 10 to get <math>\boxed{432}</math> as our answer.
 +
 
 +
==Solution 3 (Complementary Counting)==
 +
We'll use complementary counting. We will split up into <math>3</math> cases: (1) no number is repeated, (2) <math>2</math> numbers are repeated, and <math>2</math> other numbers are repeated, (3) <math>3</math> numbers are repeated, or (4) <math>4</math> numbers are repeated.
 +
 
 +
Case 1:
 +
There are <math>9</math> choices for the hundreds digit (it cannot be <math>1</math>), <math>8</math> choices for the tens digit (it cannot be <math>1</math> or what was chosen for the hundreds digit), and <math>7</math> for the units digit. This is a total of <math>9\cdot8\cdot7=504</math> numbers.
 +
 
 +
Case 2:
 +
One of the three numbers must be <math>1</math>, and the other two numbers must be the same number, but cannot be <math>1</math> (That will be dealt with in case 4). There are <math>3</math> choices to put the <math>1</math>, and there are <math>9</math> choices (any number except for <math>1</math>) to pick the other number that is repeated, so a total of <math>3\cdot9=27</math> numbers.
 +
 
 +
Case 3:
 +
We will split it into <math>2</math> subcases: one where <math>1</math> is repeated <math>3</math> times, and one where another number is repeated <math>3</math> times.
 +
When <math>1</math> is repeated <math>3</math> times, then one of the digits is not <math>1</math>. There are <math>9</math> choices for that number, and <math>3</math> choices for its location,so a total of <math>9\cdot3=27</math> numbers.
 +
When a number other than <math>1</math> is repeated <math>3</math> times, then there are <math>9</math> choices for the number, and you don't have any choices on where to put that number.
 +
So in Case 3 there are <math>27+9=36</math> numbers
 +
 
 +
Case 4:
 +
There is only <math>1</math> number: <math>1111</math>.
 +
 
 +
There are a total of <math>1000</math> <math>4</math>-digit numbers that begin with <math>1</math> (from <math>1000</math> to <math>1999</math>), so by complementary counting you get <math>1000-(504+27+36+1)=\boxed{432}</math> numbers.
 +
 
 +
Solution by Kinglogic
 +
 
 +
== Solution 4 (Easy casework) ==
 +
Let us proceed by casework.
 +
 
 +
Case 1:
 +
We will count the amount of numbers that have two identical digits that are not one. The thousands digit is fixed, and we are choosing two spots to hold two identical digits that are chosen from <math>0, 2-9</math>, which is <math>9</math> options. For the last digit, their are <math>8</math> possibilities since it can be neither <math>1</math> or the other number that is chosen. The final outcome is <math>{3}\choose{2}</math> <math>* 9 * 8 = 216</math> possibilities for this case.
 +
 
 +
Case 2:
 +
The last case will be the amount of numbers that have two identical digits thare are <math>1</math>. There are <math>{3}\choose{1}</math> places to pick the <math>1</math>. For the other <math>2</math> digits, there are <math>9</math> and <math>8</math> options respectively. Thus, we have <math>3 * 9 * 8 = 216</math>.
 +
Summing the two cases, we get <math>216 + 216 = \boxed{432}</math>.
  
 
== See Also ==
 
== See Also ==

Latest revision as of 19:26, 14 January 2023

Problem

The numbers $1447$, $1005$ and $1231$ have something in common: each is a $4$-digit number beginning with $1$ that has exactly two identical digits. How many such numbers are there?

Solution 1

Suppose that the two identical digits are both $1$. Since the thousands digit must be $1$, only one of the other three digits can be $1$. This means the possible forms for the number are

$11xy,\qquad 1x1y,\qquad1xy1$

Because the number must have exactly two identical digits, $x\neq y$, $x\neq1$, and $y\neq1$. Hence, there are $3\cdot9\cdot8=216$ numbers of this form.

Now suppose that the two identical digits are not $1$. Reasoning similarly to before, we have the following possibilities:

$1xxy,\qquad1xyx,\qquad1yxx.$

Again, $x\neq y$, $x\neq 1$, and $y\neq 1$. There are $3\cdot9\cdot8=216$ numbers of this form.

Thus the answer is $216+216=\boxed{432}$.

Solution 2

Consider a sequence of $4$ digits instead of a $4$-digit number. Only looking at the sequences which have one digit repeated twice, we notice that the probability that the sequence starts with 1 is $\frac{1}{10}$. This means we can find all possible sequences with one digit repeated twice, and then divide by $10$.

If we let the three distinct digits of the sequence be $a, b,$ and $c$, with $a$ repeated twice, we can make a table with all possible sequences:

\[\begin{tabular}{ccc} aabc & abac & abca \\ baac & baca & \\ bcaa && \\ \end{tabular}\]

There are $6$ possible sequences.

Next, we can see how many ways we can pick $a$, $b$, and $c$. This is $10(9)(8) = 720$, because there are $10$ digits, from which we need to choose $3$ with regard to order. This means there are $720(6) = 4320$ sequences of length $4$ with one digit repeated. We divide by 10 to get $\boxed{432}$ as our answer.

Solution 3 (Complementary Counting)

We'll use complementary counting. We will split up into $3$ cases: (1) no number is repeated, (2) $2$ numbers are repeated, and $2$ other numbers are repeated, (3) $3$ numbers are repeated, or (4) $4$ numbers are repeated.

Case 1: There are $9$ choices for the hundreds digit (it cannot be $1$), $8$ choices for the tens digit (it cannot be $1$ or what was chosen for the hundreds digit), and $7$ for the units digit. This is a total of $9\cdot8\cdot7=504$ numbers.

Case 2: One of the three numbers must be $1$, and the other two numbers must be the same number, but cannot be $1$ (That will be dealt with in case 4). There are $3$ choices to put the $1$, and there are $9$ choices (any number except for $1$) to pick the other number that is repeated, so a total of $3\cdot9=27$ numbers.

Case 3: We will split it into $2$ subcases: one where $1$ is repeated $3$ times, and one where another number is repeated $3$ times. When $1$ is repeated $3$ times, then one of the digits is not $1$. There are $9$ choices for that number, and $3$ choices for its location,so a total of $9\cdot3=27$ numbers. When a number other than $1$ is repeated $3$ times, then there are $9$ choices for the number, and you don't have any choices on where to put that number. So in Case 3 there are $27+9=36$ numbers

Case 4: There is only $1$ number: $1111$.

There are a total of $1000$ $4$-digit numbers that begin with $1$ (from $1000$ to $1999$), so by complementary counting you get $1000-(504+27+36+1)=\boxed{432}$ numbers.

Solution by Kinglogic

Solution 4 (Easy casework)

Let us proceed by casework.

Case 1: We will count the amount of numbers that have two identical digits that are not one. The thousands digit is fixed, and we are choosing two spots to hold two identical digits that are chosen from $0, 2-9$, which is $9$ options. For the last digit, their are $8$ possibilities since it can be neither $1$ or the other number that is chosen. The final outcome is ${3}\choose{2}$ $* 9 * 8 = 216$ possibilities for this case.

Case 2: The last case will be the amount of numbers that have two identical digits thare are $1$. There are ${3}\choose{1}$ places to pick the $1$. For the other $2$ digits, there are $9$ and $8$ options respectively. Thus, we have $3 * 9 * 8 = 216$. Summing the two cases, we get $216 + 216 = \boxed{432}$.

See Also

1983 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Problem 11
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=1983_AIME_Problems/Problem_10&oldid=186622"