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

m (→‎Solution 2 Supplement)
m (→‎Solution 2 Supplement)
Line 79: Line 79:
 
===Solution 2 Supplement===
 
===Solution 2 Supplement===
  
−
By [https://artofproblemsolving.com/wiki/index.php/Chinese_Remainder_Theorem Chinese Remainder Theorem], the general solution of system of <math>2</math> linear congruences is:
+
By [https://artofproblemsolving.com/wiki/index.php/Chinese_Remainder_Theorem Chinese Remainder Theorem], the general solution of systems of <math>2</math> linear congruences is:
 
  <math>n \equiv r_1 (\bmod { \quad m_1})</math>, <math>n \equiv r_2 (\bmod { \quad m_2})</math>, <math>(m_1, m_2) = 1</math>
 
  <math>n \equiv r_1 (\bmod { \quad m_1})</math>, <math>n \equiv r_2 (\bmod { \quad m_2})</math>, <math>(m_1, m_2) = 1</math>
 
  Find <math>k_1</math> and <math>k_2</math> such that <math>k_1 m_1 \equiv 1 (\bmod{ \quad m_2})</math>, <math>k_2 m_2 \equiv 1 (\bmod{ \quad m_1})</math>
 
  Find <math>k_1</math> and <math>k_2</math> such that <math>k_1 m_1 \equiv 1 (\bmod{ \quad m_2})</math>, <math>k_2 m_2 \equiv 1 (\bmod{ \quad m_1})</math>

Revision as of 06:51, 20 February 2022

Problem

Find the number of positive integers $n \le 600$ whose value can be uniquely determined when the values of $\left\lfloor \frac n4\right\rfloor$, $\left\lfloor\frac n5\right\rfloor$, and $\left\lfloor\frac n6\right\rfloor$ are given, where $\lfloor x \rfloor$ denotes the greatest integer less than or equal to the real number $x$.

Solution 1

1. For $n$ to be uniquely determined, $n$ AND $n + 1$ both need to be a multiple of $4, 5,$ or $6.$ Since either $n$ or $n + 1$ is odd, we know that either $n$ or $n + 1$ has to be a multiple of $5.$ We can state the following cases:

1. $n$ is a multiple of $4$ and $n+1$ is a multiple of $5$

2. $n$ is a multiple of $6$ and $n+1$ is a multiple of $5$

3. $n$ is a multiple of $5$ and $n+1$ is a multiple of $4$

4. $n$ is a multiple of $5$ and $n+1$ is a multiple of $6$

Solving for each case, we see that there are $30$ possibilities for cases 1 and 3 each, and $20$ possibilities for cases 2 and 4 each. However, we over-counted the cases where

1. $n$ is a multiple of $24$ and $n+1$ is a multiple of $5$

2. $n$ is a multiple of $5$ and $n+1$ is a multiple of $24$

Each case has $10$ possibilities.

Adding all the cases and correcting for over-counting, we get $30 + 20 + 30 + 20 - 10 - 10 = \boxed {080}.$

~Lucasfunnyface

Solution 1 Supplement

Here is a detailed solution for Solution 1. 

$1.$ $4 \mid n$, $5 \mid n+1$
$n = 4a$, $n+1 = 4a+1 = 5a - (a - 1)$, $a - 1 = 5k$, $a = 5k+1$, $n = 4(5k+1) = 20k+4$, $20k+4 \le 600$, $20k \le 596$, $k < 30$, $k \in [0, 29]$, 30 integers.

$2.$ $6 \mid n$, $5 \mid n+1$
$n = 6a$, $n+1 = 6a+1 = 5a + a + 1$, $a + 1 = 5k$, $a = 5k-1$, $n = 6(5k-1) = 30k-6$, $30k-6 \le 600$, $30k \le 606$, $k \le 20$, $k \in [1, 20]$, 20 integers.

$3.$ $5 \mid n$, $4 \mid n+1$
$n = 5a$, $n+1 = 5a+1 = 4a + a + 1$, $a + 1 = 4k$, $a = 4k-1$, $n = 5(4k-1) = 20k-5$, $20k-5 \le 600$, $20k \le 605$, $k \le 30$, $k \in [1, 30]$, 30 integers.

$4.$ $5 \mid n$, $6 \mid n+1$
$n = 5a$, $n+1 = 5a+1 = 5(a - 1) + 6$, $a - 1 = 6k$, $a = 6k+1$, $n = 5(6k+1) = 30k+5$, $30k+5 \le 600$, $30k \le 595$, $k < 20$, $k \in [0, 19]$, 20 integers.

Over-counted cases: 

$1.$ $24 \mid n$, $5 \mid n+1$
$n = 24a$, $n + 1= 24a + 1 = 20a + 4a + 1$, $4a+1 = 5k$, $k = 2p+1$, $4a = 5(2p + 1) - 1 = 10p + 4$, $n = 24a = 6(10p + 4) = 60p+24$, $60p + 24 \le 600$, $5p + 2 \le 50$, $5p \le 48$, $p < 10$, $p \in [0, 9]$, 10 integers.

$2.$ $5 \mid n$, $24 \mid n+1$
$n + 1= 5a + 1 = 24a$, $n = 24a - 1 = 20a + 4a - 1$, $4a-1 = 5k$, $k = 2p+1$, $4a = 5(2p + 1) + 1 = 10p + 6$, $n = 24a = 6(10p + 6) = 60p+36$, $60p + 36 \le 600$, $5p + 3 \le 50$, $5p \le 47$, $p < 10$, $k \in [0, 9]$, 10 integers.

$30 + 20 + 30 + 20 - 10 - 10 = \boxed{\textbf{080}}$

~isabelchen

Solution 2

The problem is the same as asking how many unique sets of values of $\lfloor\frac{n}{4}\rfloor$, $\lfloor\frac{n}{5}\rfloor$, and $\lfloor\frac{n}{6}\rfloor$ can be produced by one and only one value of $n$ for positive integers $n$ less than or equal to 600.

Seeing that we are dealing with the unique values of the floor function, we ought to examine when it is about to change values, for instance, when $n$ is close to a multiple of 4 in $\lfloor\frac{n}{4}\rfloor$.

For a particular value of $n$, let $a$, $b$, and $c$ be the original values of $\lfloor\frac{n}{4}\rfloor$, $\lfloor\frac{n}{5}\rfloor$, and $\lfloor\frac{n}{6}\rfloor$, respectively.

Notice when $n$ $\equiv0\mod4$ and $n$ $\equiv4\mod5$, the value of $\lfloor\frac{n-1}{4}\rfloor$ will be 1 less than the original $a$. The value of $\lfloor\frac{n+1}{5}\rfloor$ will be 1 greater than the original value of $b$.

More importantly, this means that no other value less than or greater than $n$ will be able to produce the set of original values of $a$, $b$, and $c$, since they make either $a$ or $b$ differ by at least 1.


Generalizing, we find that $n$ must satisfy: 

                                           $n$ $\equiv0\mod$ $j$

                                           $n$ $\equiv{k-1}\mod$ $k$

Where $j$ and $k$ are pairs of distinct values of 4, 5, and 6.

Plugging in the values of $j$ and $k$, finding the solutions to the 6 systems of linear congruences, and correcting for the repeated values, we find that there are $\boxed{080}$ solutions of $n$.

Solution 2 Supplement

By Chinese Remainder Theorem, the general solution of systems of $2$ linear congruences is: 

$n \equiv r_1 (\bmod { \quad m_1})$, $n \equiv r_2 (\bmod { \quad m_2})$, $(m_1, m_2) = 1$
Find $k_1$ and $k_2$ such that $k_1 m_1 \equiv 1 (\bmod{ \quad m_2})$, $k_2 m_2 \equiv 1 (\bmod{ \quad m_1})$
Then $n \equiv k_2 m_2 r_1 + k_1 m_1 r_2 (\bmod{ \quad m_1 m_2})$

$lcm[4, 5, 6] = 60$, we solve the number of values for $n \le 60$, then multiply by $10$ to get the number of values for $n \le 600$. We are going to solve the following $6$ systems of linear congruences: 

$\begin{cases} n \equiv 0 \mod{4} \\ n \equiv -1 \mod{5} \end{cases}$
$n \equiv 1 \cdot 5 \cdot 0 + 4 \cdot 4 \cdot (-1) \equiv -16 \equiv 4 \mod{20}$, $n \in \{ 4, 24, 44 \}$

$\begin{cases} n \equiv 0 \mod{4} \\ n \equiv -1 \mod{6} \end{cases}$
No solution

$\begin{cases} n \equiv 0 \mod{5} \\ n \equiv -1 \mod{4} \end{cases}$
$n \equiv 4 \cdot 4 \cdot 0 + 5 \cdot 5 \cdot (-1) \equiv -5 \equiv 15 \mod{20}$, $n \in \{ 15, 35, 55 \}$

$\begin{cases} n \equiv 0 \mod{5} \\ n \equiv -1 \mod{6} \end{cases}$
$n \equiv 1 \cdot 6 \cdot 0 + 5 \cdot 5 \cdot (-1) \equiv -25 \equiv 5 \mod{30}$, $n \in \{ 5, 35 \}$

$\begin{cases} n \equiv 0 \mod{6} \\ n \equiv -1 \mod{4} \end{cases}$
No solution

$\begin{cases} n \equiv 0 \mod{6} \\ n \equiv -1 \mod{5} \end{cases}$
$n \equiv 5 \cdot 5 \cdot 0 + 1 \cdot 6 \cdot (-1) \equiv -6 \equiv 24 \mod{30}$, $n \in \{ 24, 54 \}$

$n \in \{ 4, 5, 15, 24, 35, 44, 54, 55 \}$, there are $8$ values for $n \le 60$. For $n \le 600$, the answer is $8 \cdot 10 = \boxed{\textbf{080}}$.

~isabelchen

Solution 3

We need to find all numbers between $1$ and $600$ inclusive that are multiples of $4$, $5$, and/or $6$ which are also multiples of $4$, $5$, and/or $6$ when $1$ is added to them.

We begin by noting that the LCM of $4$, $5$, and $6$ is $60$. We can therefore simplify the problem by finding all such numbers described above between $1$ and $60$ and multiplying the quantity of such numbers by $10$ ($600$/$60$ = $10$).

After making a simple list of the numbers between $1$ and $60$ and going through it, we see that the numbers meeting this condition are $4$, $5$, $15$, $24$, $35$, $44$, $54$, and $55$. This gives us $8$ numbers. $8$ * $10$ = $\boxed{080}$. ~burkinafaso

Solution 4

This is Solution 3 with a slick element included. Solution 3 uses the concept that $60k+l$ is a solution for $n$ iff $60k+l$ is a multiple of $3$, $4$, and/or $5$ and $60k+l+1$ is a multiple of $3$, $4$, and/or $5$ for positive integer values of $l$ and essentially any integer value of $k$. But keeping the same conditions in mind for $k$ and $l$, we can also say that if $60k+l$ is a solution, then $60k-l-1$ is a solution! Therefore, one doesn't have to go as far as determining the number of values between $1$ and $60$ and then multiplying by $10$. One only has to determine the number of values between $1$ and $30$ and then multiply by $20$. The values of $n$ that work between $1$ and $30$ are $4$, $5$, $15$, and $24$. This gives us $4$ numbers. $4$ * $20$ = $\boxed{080}$. ~burkinafaso

Sidenote

For solving a system of linear congruences, see https://youtu.be/-a88u99nmkw

See Also

2022 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

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=2022_AIME_II_Problems/Problem_8&oldid=171674"