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"

(ok)
m (→‎Solution 3 (Complementary Counting))
(8 intermediate revisions by 5 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==
−
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,
+
===Solution 1===
 +
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</math></div>
 
<div style="text-align:center;"><math>11xy,\qquad 1x1y,\qquad1xy1</math></div>
Line 9: Line 10:
 
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.
 
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 16:
 
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>216+216=\boxed{432}</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
  
 
== See Also ==
 
== See Also ==

Revision as of 15:03, 13 December 2020

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

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

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=139550"