2022 AIME II Problems/Problem 8

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. 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 $20$ possibilities for cases 1 and 3 each, and $30$ possibilities for cases 2 and 4 each. However, we overcounted 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 overcounting, we get $20 + 30 + 20 + 30 - 10 - 10 = \boxed {080}.$

~Lucasfunnyface

Side note: solution does not explain how we found the 20 possibilities, 30, possibilities, etc. It would be great if somebody added that in.

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:

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$ .

Sidenote

The mod computation can be more easily done by first finding the solutions in the range 1-60, correcting for overcounting, and multiplying by 10.

Alternatively, before taking the time to consider a systematic solution, you can notice that the general pattern of the problem “repeats” every 60 positive integers. From there, bash to see how many of the first 60 numbers work and multiply by 10.

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

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

Page

Toolbox

Search

2022 AIME II Problems/Problem 8

Contents

Problem

Solution

Solution 2

Sidenote

See Also