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 "2016 AIME II Problems/Problem 11"

m
m (→‎Solution)
 
(11 intermediate revisions by 8 users not shown)
Line 1: Line 1:
 +
==Problem==
 
For positive integers <math>N</math> and <math>k</math>, define <math>N</math> to be <math>k</math>-nice if there exists a positive integer <math>a</math> such that <math>a^{k}</math> has exactly <math>N</math> positive divisors. Find the number of positive integers less than <math>1000</math> that are neither <math>7</math>-nice nor <math>8</math>-nice.
 
For positive integers <math>N</math> and <math>k</math>, define <math>N</math> to be <math>k</math>-nice if there exists a positive integer <math>a</math> such that <math>a^{k}</math> has exactly <math>N</math> positive divisors. Find the number of positive integers less than <math>1000</math> that are neither <math>7</math>-nice nor <math>8</math>-nice.
  
 
==Solution==
 
==Solution==
−
We claim that an integer <math>N</math> is only <math>k</math>-nice if and only if <math>N \equiv 1 \pmod k</math>. By the number of divisors formula, the number of divisors of <math>\prod_{i=1}^n p_i^{a_i}</math> is <math>\prod_{i=1}^n (a_i+1)</math>. Since all the <math>a_i</math>s are divisible by <math>k</math> in a perfect <math>k</math> power, the only if part of the claim follows. To show that all numbers <math>N \equiv 1 \pmod k</math> are <math>k</math>-nice, write <math>N=bk+1</math>. Note that <math>2^{kb}</math> has the desired number of factors and is a perfect kth power. By PIE, the number of positive integers less than <math>1000</math> that are either <math>1 \pmod 7</math> or <math>1\pmod 8</math> is <math>143+125-18=250</math>, so the desired answer is <math>999-250=\boxed{749}</math>.
+
We claim that an integer <math>N</math> is only <math>k</math>-nice if and only if <math>N \equiv 1 \pmod k</math>. By the number of divisors formula, the number of divisors of <math>\prod_{i=1}^n p_i^{a_i}</math> is <math>\prod_{i=1}^n (a_i+1)</math>. Since all the <math>a_i</math>'s are divisible by <math>k</math> in a perfect <math>k</math> power, the only if part of the claim follows. To show that all numbers <math>N \equiv 1 \pmod k</math> are <math>k</math>-nice, write <math>N=bk+1</math>. Note that <math>2^{kb}</math> has the desired number of factors and is a perfect kth power. By PIE, the number of positive integers less than <math>1000</math> that are either <math>1 \pmod 7</math> or <math>1\pmod 8</math> is <math>142+125-17=250</math>, so the desired answer is <math>999-250=\boxed{749}</math>.
  
−
Solution by Shaddoll
+
Solution by Shaddoll and firebolt360
 +
 
 +
==Solution 2==
 +
All integers <math>a</math> will have factorization <math>2^a3^b5^c7^d...</math>. Therefore, the number of factors in <math>a^7</math> is <math>(7a+1)(7b+1)...</math>, and for <math>a^8</math> is <math>(8a+1)(8b+1)...</math>. The most salient step afterwards is to realize that all numbers <math>N</math> not <math>1 \pmod{7}</math> and also not <math>1 \pmod{8}</math> satisfy the criterion. The cycle repeats every <math>56</math> integers, and by PIE, <math>7+8-1=14</math> of them are either <math>7</math>-nice or <math>8</math>-nice or both. Therefore, we can take <math>\frac{42}{56} * 1008 = 756</math> numbers minus the <math>7</math> that work between <math>1000-1008</math> inclusive, to get <math>\boxed{749}</math> positive integers less than <math>1000</math> that are not nice for <math>k=7, 8</math>.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2016|n=II|num-b=10|num-a=12}}
 
{{AIME box|year=2016|n=II|num-b=10|num-a=12}}
 +
 +
[[Category: Intermediate Number Theory Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 05:19, 16 August 2024

Problem

For positive integers $N$ and $k$, define $N$ to be $k$-nice if there exists a positive integer $a$ such that $a^{k}$ has exactly $N$ positive divisors. Find the number of positive integers less than $1000$ that are neither $7$-nice nor $8$-nice.

Solution

We claim that an integer $N$ is only $k$-nice if and only if $N \equiv 1 \pmod k$. By the number of divisors formula, the number of divisors of $\prod_{i=1}^n p_i^{a_i}$ is $\prod_{i=1}^n (a_i+1)$. Since all the $a_i$'s are divisible by $k$ in a perfect $k$ power, the only if part of the claim follows. To show that all numbers $N \equiv 1 \pmod k$ are $k$-nice, write $N=bk+1$. Note that $2^{kb}$ has the desired number of factors and is a perfect kth power. By PIE, the number of positive integers less than $1000$ that are either $1 \pmod 7$ or $1\pmod 8$ is $142+125-17=250$, so the desired answer is $999-250=\boxed{749}$.

Solution by Shaddoll and firebolt360

Solution 2

All integers $a$ will have factorization $2^a3^b5^c7^d...$. Therefore, the number of factors in $a^7$ is $(7a+1)(7b+1)...$, and for $a^8$ is $(8a+1)(8b+1)...$. The most salient step afterwards is to realize that all numbers $N$ not $1 \pmod{7}$ and also not $1 \pmod{8}$ satisfy the criterion. The cycle repeats every $56$ integers, and by PIE, $7+8-1=14$ of them are either $7$-nice or $8$-nice or both. Therefore, we can take $\frac{42}{56} * 1008 = 756$ numbers minus the $7$ that work between $1000-1008$ inclusive, to get $\boxed{749}$ positive integers less than $1000$ that are not nice for $k=7, 8$.

See also

2016 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
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=2016_AIME_II_Problems/Problem_11&oldid=225119"