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 "2025 AIME II Problems/Problem 7"
m (LaTeX solution 1)
Line 6: Line 6:
 
We split into different conditions:
 
We split into different conditions:
  
−
Note that the set needs to satisfy with all of the elements' lcm = 2025, we need to ensure that the set has at least 1 number that is a multiple of 3^4 and a number that is a multiple of 5^2.  
+
Note that the set needs to satisfy with all of the elements' <math>\text{lcm} = 2025</math>, we need to ensure that the set has at least 1 number that is a multiple of <math>3^4</math> and a number that is a multiple of <math>5^2</math>.  
  
−
Multiples of 3^4: 81, 405, 2025
+
Multiples of <math>3^4</math>: <math>81, 405, 2025</math>
−
Multiples of 5^2: 25, 75, 225, 675, 2025
 
  
−
If the set B contains 2025, then all of the rest 14 factors is no longer important. The valid cases are 2^14.
+
Multiples of <math>5^2</math>: <math>25, 75, 225, 675, 2025</math>
  
−
If the set B doesn't contain 2025, but contains 405, we just need another multiple of 5^2. It could be 1 of them, 2 of them, 3 of them or 4 of them, which has 2^4 - 1 = 15 cases. Excluding 2025, 405, 25, 75, 225, 675, the rest 9 numbers could appear or not appear. Therefore, this case has a valid case of 15 * 2^9.  
+
If the set <math>B</math> contains <math>2025</math>, then all of the rest <math>14</math> factors is no longer important. The valid cases are <math>2^{14}</math>.
  
−
If set B doesn't contain 2025 nor 405, it must contain 81. It also needs to contain at least 1 of the multiples from 5^2, where it would be 15 * 2^8.  
+
If the set <math>B</math> doesn't contain <math>2025</math>, but contains <math>405</math>, we just need another multiple of <math>5^2</math>. It could be 1 of them, 2 of them, 3 of them or 4 of them, which has <math>2^4 - 1 = 15</math> cases. Excluding <math>2025, 405, 25, 75, 225, 675,</math> the rest 9 numbers could appear or not appear. Therefore, this case has a valid case of <math>15 \cdot 2^9</math>.  
  
−
The total valid cases are 2^14 + 15 * (2^9 + 2^8), and the total cases are 2^15.
+
If set <math>B</math> doesn't contain <math>2025</math> nor <math>405</math>, it must contain <math>81</math>. It also needs to contain at least 1 of the multiples from <math>5^2</math>, where it would be <math>15 \cdot 2^8</math>.  
−
The answer is 2^8 * (64 + 30 + 15) / 2^8 * 2^7 = 109/128.  
 
−
Desired answer: 109 + 128 = 237
 
  
−
(Feel free to edit any latex or format problems)
+
The total valid cases are <math>2^{14} + 15 \cdot (2^9 + 2^8)</math>, and the total cases are <math>2^{15}</math>.
 +
 
 +
The answer is <math>\cfrac{2^8 \cdot (64 + 30 + 15)}{2^8 \cdot 2^7}= \frac{109}{128}</math>.
 +
 
 +
Desired answer: <math>109 + 128 = \boxed{237}</math>
  
 
~Mitsuihisashi14
 
~Mitsuihisashi14
 +
 +
~LaTeX by eevee9406
  
 
==Solution 2==
 
==Solution 2==
Line 45: Line 48:
  
 
~Bluesoul
 
~Bluesoul
 +
 +
==See also==
 +
{{AIME box|year=2025|num-b=6|num-a=8|n=II}}
 +
 +
{{MAA Notice}}

Revision as of 03:03, 14 February 2025

Problem

Let $A$ be the set of positive integer divisors of $2025$. Let $B$ be a randomly selected subset of $A$. The probability that $B$ is a nonempty set with the property that the least common multiple of its element is $2025$ is $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

Solution 1

We split into different conditions:

Note that the set needs to satisfy with all of the elements' $\text{lcm} = 2025$, we need to ensure that the set has at least 1 number that is a multiple of $3^4$ and a number that is a multiple of $5^2$.

Multiples of $3^4$: $81, 405, 2025$

Multiples of $5^2$: $25, 75, 225, 675, 2025$

If the set $B$ contains $2025$, then all of the rest $14$ factors is no longer important. The valid cases are $2^{14}$.

If the set $B$ doesn't contain $2025$, but contains $405$, we just need another multiple of $5^2$. It could be 1 of them, 2 of them, 3 of them or 4 of them, which has $2^4 - 1 = 15$ cases. Excluding $2025, 405, 25, 75, 225, 675,$ the rest 9 numbers could appear or not appear. Therefore, this case has a valid case of $15 \cdot 2^9$.

If set $B$ doesn't contain $2025$ nor $405$, it must contain $81$. It also needs to contain at least 1 of the multiples from $5^2$, where it would be $15 \cdot 2^8$.

The total valid cases are $2^{14} + 15 \cdot (2^9 + 2^8)$, and the total cases are $2^{15}$.

The answer is $\cfrac{2^8 \cdot (64 + 30 + 15)}{2^8 \cdot 2^7}= \frac{109}{128}$.

Desired answer: $109 + 128 = \boxed{237}$

~Mitsuihisashi14

~LaTeX by eevee9406

Solution 2

We take the complement and use PIE. Suppose the LCM of the elements of the set is NOT $2025$. Since $2025=3^4 \cdot 5^2$, it must be that no element $x$ in the subset satisfies $v_3(x)=4$ OR no element $x$ in the subset satisfies $v_5(x)=2$ (in this case, $v_p(n)$ gives the exponent of $p$ in the prime factorization of $n$). For the first case, there are $4 \cdot 3 = 12$ possible divisors that could be in our subset ($v_3(x)=0,1,2,3,v_5(x)=0,1,2$ are possible), for a total count of $2^{12}$ subsets. In the second case, there are $5 \cdot 2 = 10$ possible divisors that could be in our subset, for a total count of $2^{10}$ subsets. However, if both conditions are violated, then there are $4 \cdot 2 = 8$ divisors that could be in our subset, for a total count of $2^8$ subsets. Hence, by PIE, the number of subsets whose LCM is NOT $2025$ is equal to $2^{12}+2^{10}-2^8$. The answer is then \[1-\frac{2^{12}+2^{10}-2^8}{2^{5 \cdot 3}}=\frac{109}{128} \implies \boxed{237}.\]

~cxsmi

Solution 3

Write numbers in the form of $3^{a}5^{b}$ where $0\leq a\leq 4; 0\leq b\leq 2$

There are $(4+1)(2+1)=15$ possible divisors of $2025$, so the cardinality of the subsets is $2^{15}$

If I select $3^4\cdot 5^2$, then I guarantee the lcm is 2025, so the other 14 numbers yield $2^{14}$ cases.

If I select $3^4\cdot 5$, then I must select at least one of $3^a5^2$, but I can select any other $9$ numbers, so there are $2^9(\binom{4}{1}+\binom{4}{2}+\binom{4}{3}+\binom{4}{4})=2^9\cdot 15$ ways

If I select $3^4$, same reason above but since we cant selct $3^4\cdot 5; 3^4 5^2$ anymore, there are $2^8(\binom{4}{1}+\binom{4}{2}+\binom{4}{3}+\binom{4}{4})=2^8\cdot 15$ ways

The answer is then $\frac{2^8(15+30+64)}{2^{15}}=\frac{109}{128}\implies \boxed{237}$

~Bluesoul

See also

2025 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 6 		Followed by
Problem 8
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=2025_AIME_II_Problems/Problem_7&oldid=242480"