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 "Mock AIME II 2012 Problems/Problem 10"
m
 
Line 1: Line 1:
 
==Problem ==
 
==Problem ==
−
Call a set of positive integers <math>\mathcal{S}</math> <math>\textit{lucky}</math> if it can be split into two nonempty disjoint subsets <math>\mathcal{A}</math> and <math>\mathcal{B}</math> with <math>A\cap B=S</math> such that the product of the elements in <math>\mathcal{A}</math> and the product of the elements in <math>\mathcal{B}</math> sum up to the cardinality of <math>\mathcal{S}</math>. Find the number of <math>\textit{lucky}</math> sets such that the largest element is less than <math>15</math>. (Disjoint subsets have no elements in common, and the cardinality of a set is the number of elements in the set.)
+
Call a set of positive integers <math>\mathcal{S}</math> <math>\textit{lucky}</math> if it can be split into two nonempty disjoint subsets <math>\mathcal{A}</math> and <math>\mathcal{B}</math> with <math>A\cup B=S</math> such that the product of the elements in <math>\mathcal{A}</math> and the product of the elements in <math>\mathcal{B}</math> sum up to the cardinality of <math>\mathcal{S}</math>. Find the number of <math>\textit{lucky}</math> sets such that the largest element is less than <math>15</math>. (Disjoint subsets have no elements in common, and the cardinality of a set is the number of elements in the set.)
  
 
==Solution==
 
==Solution==
 
Let the cardinality of <math> \mathcal{S} </math> be <math> n </math>. We therefore want the sum of the products of the elements of <math> \mathcal{A} </math> and <math> \mathcal{B} </math> to be <math> n </math>, and this is constant no matter what the elements of <math> \mathcal{S} </math> are. The set with the smallest such sum of products is the set <math> \{1, 2, \cdots n\} </math>, since if one of the elements is not in this set, then we can replace it with one of the elements in this set and get a smaller product. However, notice that whichever subset <math> \mathcal{A} </math> or <math> \mathcal{B} </math> contains the element <math> n </math>, then the product of the elements of that set will be greater than or equal to <math> n </math>, and the product of the elements of the other set will be positive, and so the sum of the products must be greater than <math> n </math>. Therefore, no lucky set of positive integers is possible and the answer is <math> \boxed{000} </math>.
 
Let the cardinality of <math> \mathcal{S} </math> be <math> n </math>. We therefore want the sum of the products of the elements of <math> \mathcal{A} </math> and <math> \mathcal{B} </math> to be <math> n </math>, and this is constant no matter what the elements of <math> \mathcal{S} </math> are. The set with the smallest such sum of products is the set <math> \{1, 2, \cdots n\} </math>, since if one of the elements is not in this set, then we can replace it with one of the elements in this set and get a smaller product. However, notice that whichever subset <math> \mathcal{A} </math> or <math> \mathcal{B} </math> contains the element <math> n </math>, then the product of the elements of that set will be greater than or equal to <math> n </math>, and the product of the elements of the other set will be positive, and so the sum of the products must be greater than <math> n </math>. Therefore, no lucky set of positive integers is possible and the answer is <math> \boxed{000} </math>.

Latest revision as of 20:13, 8 April 2012

Problem

Call a set of positive integers $\mathcal{S}$ $\textit{lucky}$ if it can be split into two nonempty disjoint subsets $\mathcal{A}$ and $\mathcal{B}$ with $A\cup B=S$ such that the product of the elements in $\mathcal{A}$ and the product of the elements in $\mathcal{B}$ sum up to the cardinality of $\mathcal{S}$. Find the number of $\textit{lucky}$ sets such that the largest element is less than $15$. (Disjoint subsets have no elements in common, and the cardinality of a set is the number of elements in the set.)

Solution

Let the cardinality of $\mathcal{S}$ be $n$. We therefore want the sum of the products of the elements of $\mathcal{A}$ and $\mathcal{B}$ to be $n$, and this is constant no matter what the elements of $\mathcal{S}$ are. The set with the smallest such sum of products is the set $\{1, 2, \cdots n\}$, since if one of the elements is not in this set, then we can replace it with one of the elements in this set and get a smaller product. However, notice that whichever subset $\mathcal{A}$ or $\mathcal{B}$ contains the element $n$, then the product of the elements of that set will be greater than or equal to $n$, and the product of the elements of the other set will be positive, and so the sum of the products must be greater than $n$. Therefore, no lucky set of positive integers is possible and the answer is $\boxed{000}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_II_2012_Problems/Problem_10&oldid=46208"