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 (Created page with '== Problem 8 == 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: <UL>…')
 
m (→‎solution)
Line 15: Line 15:
 
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> (if <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)
  
  

Revision as of 17:16, 3 April 2010

Problem 8

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