2022 AIME II Problems/Problem 8
Contents
[hide]Problem
Find the number of positive integers whose value can be uniquely determined when the values of , , and are given, where denotes the greatest integer less than or equal to the real number .
Solution 1
We need to find all numbers between and inclusive that are multiples of , , and/or which are also multiples of , , and/or when is added to them.
We begin by noting that the LCM of , , and is . We can therefore simplify the problem by finding all such numbers described above between and and multiplying the quantity of such numbers by (/ = ).
After making a simple list of the numbers between and and going through it, we see that the numbers meeting this condition are , , , , , , , and . This gives us numbers. * = .
Soon after the test was administered, a formal request was made to also accept as an answer and MAA decided to honor this request. The gist of this request stated that the phrasing of the first part of the question could reasonably be interpreted to mean that one is given the condition to begin with that the integer is less than or equal to . In this case, if one was told that the values of , , and were , , and respectively, then the only possible choice for would be as , , and do not meet the condition as stated in the first part of the problem. ~burkinafaso
Solution 1.5
This is Solution 1 with a slick element included. Solution 1 uses the concept that is a solution for if is a multiple of , , and/or and is a multiple of , , and/or for positive integer values of and essentially any integer value of . But keeping the same conditions in mind for and , we can also say that if is a solution, then is a solution! Therefore, one doesn't have to go as far as determining the number of values between and and then multiplying by . One only has to determine the number of values between and and then multiply by . The values of that work between and are , , , and . This gives us numbers. * = .
Soon after the test was administered, a formal request was made to also accept as an answer and MAA decided to honor this request. The gist of this request stated that the phrasing of the first part of the question could reasonably be interpreted to mean that one is given the condition to begin with that the integer is less than or equal to . In this case, if one was told that the values of , , and were , , and respectively, then the only possible choice for would be as , , and do not meet the condition as stated in the first part of the problem. ~burkinafaso
Solution 2
1. For to be uniquely determined, AND both need to be a multiple of or Since either or is odd, we know that either or has to be a multiple of We can state the following cases:
1. is a multiple of and is a multiple of
2. is a multiple of and is a multiple of
3. is a multiple of and is a multiple of
4. is a multiple of and is a multiple of
Solving for each case, we see that there are possibilities for cases 1 and 3 each, and possibilities for cases 2 and 4 each. However, we over-counted the cases where
1. is a multiple of and is a multiple of
2. is a multiple of and is a multiple of
Each case has possibilities.
Adding all the cases and correcting for over-counting, we get
~Lucasfunnyface
Solution 2 Supplement
Here is a detailed solution for Solution 2.
, , , , , , , , , , 30 integers.
, , , , , , , , , , 20 integers.
, , , , , , , , , , 30 integers.
, , , , , , , , , , 20 integers.
Over-counted cases:
, , , , , , , , , , , , 10 integers.
, , , , , , , , , , , , 10 integers.
Solution 3
The problem is the same as asking how many unique sets of values of , , and can be produced by one and only one value of for positive integers 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 is close to a multiple of 4 in .
For a particular value of , let , , and be the original values of , , and , respectively.
Notice when and , the value of will be 1 less than the original . The value of will be 1 greater than the original value of .
More importantly, this means that no other value less than or greater than will be able to produce the set of original values of , , and , since they make either or differ by at least 1.
Generalizing, we find that must satisfy:
Where and are pairs of distinct values of 4, 5, and 6.
Plugging in the values of and , finding the solutions to the 6 systems of linear congruences, and correcting for the repeated values, we find that there are solutions of .
Solution 3 Supplement
By Chinese Remainder Theorem, the general solution of systems of linear congruences is:
, , Find and such that , Then
, we solve the number of values for , then multiply by to get the number of values for . We are going to solve the following systems of linear congruences:
,
No solution
,
,
No solution
,
, there are values for . For , the answer is .
Sidenote
For solving a system of linear congruences, see https://youtu.be/-a88u99nmkw
Solution 4
Observe that if such that n is a solution to the desired equation, so is , where m is an integer, . So we only need to consider n from 1 to 60. As shown in Solution 2, there are 4 cases which we will split into 2 main cases:
- Case 1: or ,
- Case 2: or ,
There are 4 values of n where satisfying or .
I claim that there are 4 values of satisfying Case 1. Suppose x is one value of n satisfying or , and . Hence the solutions satisfying or , are of the form , so the values of are (mod 5), so (mod 5) and hence the value of m is unique since to satisfy and 2 and 5 are relatively prime.
A similar approach can be used to show the same for Case 2, that there are 4 values of .
Hence our answer is .
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.