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 "2010 AIME II Problems/Problem 8"

m (→‎solution)
(Semi-automated contest formatting - script by azjps)
Line 1: Line 1:
−
== Problem 8 ==
+
== Problem ==
−
Let <math>N</math> be the number of ordered pairs of nonempty sets <math>\mathcal{A}</math> and <math>\mathcal{B}</math> that have the following properties:
+
Let <math>N</math> be the number of [[ordered pair]]s of nonempty sets <math>\mathcal{A}</math> and <math>\mathcal{B}</math> that have the following properties:
  
 
<UL>
 
<UL>
Line 11: Line 11:
 
Find <math>N</math>.
 
Find <math>N</math>.
  
−
== solution==
+
== Solution==
−
 
+
Let us [[partition]] the set <math>\{1,2,\cdots,12\}</math> into <math>n</math> numbers in <math>A</math> and <math>12-n</math> numbers in <math>B</math>,  
−
Let us partition the set <math>\{1,2,\cdots,12\}</math> into <math>n</math> numbers in <math>A</math> and <math>12-n</math> numbers in <math>B</math>,  
 
−
 
 
−
Since <math>n</math> must be in <math>B</math> and <math>12-n</math> must be in <math>A</math> (<math>n\ne6</math>, we cannot partition into two sets of 6 because <math>6</math> needs to end up somewhere, <math>n\ne 0</math> or <math>12</math> either)
 
  
 +
Since <math>n</math> must be in <math>B</math> and <math>12-n</math> must be in <math>A</math> (<math>n\ne6</math>, we cannot partition into two sets of 6 because <math>6</math> needs to end up somewhere, <math>n\ne 0</math> or <math>12</math> either).
  
 
We have <math>\dbinom{10}{n-1}</math>  ways of picking the numbers to be in <math>A</math>.  
 
We have <math>\dbinom{10}{n-1}</math>  ways of picking the numbers to be in <math>A</math>.  
  
−
So the answer is <math>\left(\sum_{n=1}^{11} \dbinom{10}{n-1}\right) - \dbinom{10}{5}=2^{10}-252= \boxed{772}</math>
+
So the answer is <math>\left(\sum_{n=1}^{11} \dbinom{10}{n-1}\right) - \dbinom{10}{5}=2^{10}-252= \boxed{772}</math>.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2010|num-b=7|num-a=9|n=II}}
 
{{AIME box|year=2010|num-b=7|num-a=9|n=II}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Revision as of 10:46, 6 April 2010

Problem

Let $N$ be the number of ordered pairs of nonempty sets $\mathcal{A}$ and $\mathcal{B}$ that have the following properties:

  • $\mathcal{A} \cup \mathcal{B} = \{1,2,3,4,5,6,7,8,9,10,11,12\}$,
  • $\mathcal{A} \cap \mathcal{B} = \emptyset$,
  • The number of elements of $\mathcal{A}$ is not an element of $\mathcal{A}$,
  • The number of elements of $\mathcal{B}$ is not an element of $\mathcal{B}$.

Find $N$.

Solution

Let us partition the set $\{1,2,\cdots,12\}$ into $n$ numbers in $A$ and $12-n$ numbers in $B$,

Since $n$ must be in $B$ and $12-n$ must be in $A$ ($n\ne6$, we cannot partition into two sets of 6 because $6$ needs to end up somewhere, $n\ne 0$ or $12$ either).

We have $\dbinom{10}{n-1}$ ways of picking the numbers to be in $A$.

So the answer is $\left(\sum_{n=1}^{11} \dbinom{10}{n-1}\right) - \dbinom{10}{5}=2^{10}-252= \boxed{772}$.

See also

2010 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 7 		Followed by
Problem 9
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=2010_AIME_II_Problems/Problem_8&oldid=34234"