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 "2009 AIME I Problems/Problem 9"

(→‎Solution)
 
(13 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
A game show offers a contestant three prizes A, B and C, each of which is worth a whole number of dollars from <dollar/><math>1</math> to <dollar/><math>9999</math> inclusive. The contestant wins the prizes by correctly guessing the price of each prize in the order A, B, C. As a hint, the digits of the three prices are given. On a particular day, the digits given were <math>1, 1, 1, 1, 3, 3, 3</math>. Find the total number of possible guesses for all three prizes consistent with the hint.
+
A game show offers a contestant three prizes A, B and C, each of which is worth a whole number of dollars from <math>\$ 1</math> to <math>\$ 9999</math> inclusive. The contestant wins the prizes by correctly guessing the price of each prize in the order A, B, C. As a hint, the digits of the three prices are given. On a particular day, the digits given were <math>1, 1, 1, 1, 3, 3, 3</math>. Find the total number of possible guesses for all three prizes consistent with the hint.
  
 
== Solution ==
 
== Solution ==
−
Since we have 3 numbers, consider how many ways we can put this 3 number in a string of 7 digits by putting A,B,C together
+
[Clarification: You are supposed to find the number of all possible tuples of prices, <math>(A, B, C)</math>, that could have been on that day.]
  
−
For example: <math>A=113, B=13, C=31</math>
+
Since we have three numbers, consider the number of ways we can put these three numbers together in a string of 7 digits. For example, if <math>A=113, B=13, C=31</math>, then the string is
  
−
Then the string is
+
<cmath>1131331.</cmath>
  
−
<cmath>1131331</cmath>
+
Since the strings have seven digits and three threes, there are <math>\binom{7}{3}=35</math> arrangements of all such strings.
  
−
Since the strings have 7 digits and 3 three's. There are
+
In order to obtain all combination of A,B,C, we partition all the possible strings into 3 groups.
  
−
<math>_7C_3</math> of such string
+
Let's look at the example. We have to partition it into 3 groups with each group having at least 1 digit. In other words, we need to find the solution to
  
−
In other to obtain all combination of A,B,C. We partition all the possible strings into 3 groups
+
<cmath>x+y+z=7, x,y,z>0.</cmath>
  
−
Let look at the example.
+
This gives us
  
−
We have to partition it into 3 groups with each group having at least 1 digit
+
<cmath>\binom{6}{2}=15</cmath>
  
−
We have to find solution where
+
ways by stars and bars. But we have counted the one with 5 digit numbers; that is, <math>(5,1,1),(1,1,5),(1,5,1)</math>.
  
−
<cmath>x+y+z=7, 0<x,y,z<5</cmath>
+
Thus, each arrangement has <cmath>\binom{6}{2}-3=12</cmath> ways per arrangement, and there are <math>12\times35=\boxed{420}</math> ways.
  
−
This gives us:
+
==Video Solution==
−
 
+
https://youtu.be/VhyLeQufKr8
−
<cmath>_6C_2</cmath> (balls and urns)
 
−
 
 
−
But we have counted the one with 5 digit numbers. That is <math>(5,1,1),(1,1,5),(1,5,1)</math>
 
−
 
 
−
Thus, each arrangement has <cmath>(_6C_2)-3=12</cmath> ways per arrangement
 
−
 
 
−
Thus, there are <math>(12)(35)ways=\boxed{420}</math>
 
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2009|n=I|num-b=8|num-a=10}}
 
{{AIME box|year=2009|n=I|num-b=8|num-a=10}}
 +
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 22:32, 15 July 2024

Problem

A game show offers a contestant three prizes A, B and C, each of which is worth a whole number of dollars from $$ 1$ to $$ 9999$ inclusive. The contestant wins the prizes by correctly guessing the price of each prize in the order A, B, C. As a hint, the digits of the three prices are given. On a particular day, the digits given were $1, 1, 1, 1, 3, 3, 3$. Find the total number of possible guesses for all three prizes consistent with the hint.

Solution

[Clarification: You are supposed to find the number of all possible tuples of prices, $(A, B, C)$, that could have been on that day.]

Since we have three numbers, consider the number of ways we can put these three numbers together in a string of 7 digits. For example, if $A=113, B=13, C=31$, then the string is

\[1131331.\]

Since the strings have seven digits and three threes, there are $\binom{7}{3}=35$ arrangements of all such strings.

In order to obtain all combination of A,B,C, we partition all the possible strings into 3 groups.

Let's look at the example. We have to partition it into 3 groups with each group having at least 1 digit. In other words, we need to find the solution to

\[x+y+z=7, x,y,z>0.\]

This gives us

\[\binom{6}{2}=15\]

ways by stars and bars. But we have counted the one with 5 digit numbers; that is, $(5,1,1),(1,1,5),(1,5,1)$.

Thus, each arrangement has \[\binom{6}{2}-3=12\] ways per arrangement, and there are $12\times35=\boxed{420}$ ways.

Video Solution

https://youtu.be/VhyLeQufKr8

See also

2009 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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=2009_AIME_I_Problems/Problem_9&oldid=222698"