Difference between revisions of "2021 AIME II Problems/Problem 11"
MRENTHUSIASM (talk | contribs) m (→Solution 2 (Illustrations)) |
MRENTHUSIASM (talk | contribs) (→Solution 4 (Logic)) |
||
(40 intermediate revisions by 5 users not shown) | |||
Line 4: | Line 4: | ||
However, upon hearing that all four students replied no, each student was able to determine the elements of <math>S</math>. Find the sum of all possible values of the greatest element of <math>S</math>. | However, upon hearing that all four students replied no, each student was able to determine the elements of <math>S</math>. Find the sum of all possible values of the greatest element of <math>S</math>. | ||
− | ==Solution 1 | + | ==Solution 1== |
− | + | Note that <math>\operatorname{lcm}(6,7)=42.</math> It is clear that <math>42\not\in S</math> and <math>84\not\in S,</math> otherwise the three other elements in <math>S</math> are divisible by neither <math>6</math> nor <math>7.</math> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | Note that <math>\ | ||
− | |||
− | |||
+ | In the table below, the multiples of <math>6</math> are colored in yellow, and the multiples of <math>7</math> are colored in green. By the least common multiple, we obtain cycles: If <math>n</math> is a possible maximum value of <math>S,</math> then <math>n+42</math> must be another possible maximum value of <math>S,</math> and vice versa. By observations, we circle all possible maximum values of <math>S.</math> | ||
<asy> | <asy> | ||
/* Made by MRENTHUSIASM */ | /* Made by MRENTHUSIASM */ | ||
size(20cm); | size(20cm); | ||
− | + | fill((5,0)--(6,0)--(6,2)--(5,2)--cycle,yellow); | |
− | + | fill((11,0)--(12,0)--(12,3)--(11,3)--cycle,yellow); | |
− | + | fill((17,1)--(18,1)--(18,3)--(17,3)--cycle,yellow); | |
− | + | fill((23,1)--(24,1)--(24,3)--(23,3)--cycle,yellow); | |
− | + | fill((29,1)--(30,1)--(30,3)--(29,3)--cycle,yellow); | |
− | + | fill((35,1)--(36,1)--(36,3)--(35,3)--cycle,yellow); | |
− | |||
− | + | fill((6,0)--(7,0)--(7,2)--(6,2)--cycle,green); | |
− | + | fill((13,0)--(14,0)--(14,3)--(13,3)--cycle,green); | |
− | + | fill((20,1)--(21,1)--(21,3)--(20,3)--cycle,green); | |
− | + | fill((27,1)--(28,1)--(28,3)--(27,3)--cycle,green); | |
− | + | fill((34,1)--(35,1)--(35,3)--(34,3)--cycle,green); | |
− | |||
− | |||
fill((42,3)--(41,3)--(41,2)--cycle,yellow); | fill((42,3)--(41,3)--(41,2)--cycle,yellow); | ||
Line 46: | Line 30: | ||
fill((42,2)--(42,1)--(41,1)--cycle,green); | fill((42,2)--(42,1)--(41,1)--cycle,green); | ||
− | + | for (real i=9.5; i<=41.5; ++i) { | |
− | + | label("$"+string(i+0.5)+"$",(i,2.5),fontsize(9pt)); | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | label(" | ||
− | |||
− | |||
− | |||
− | |||
− | + | for (real i=0.5; i<=41.5; ++i) { | |
− | + | label("$"+string(i+42.5)+"$",(i,1.5),fontsize(9pt)); | |
− | + | } | |
− | draw(( | + | |
− | draw(( | + | for (real i=0.5; i<=14.5; ++i) { |
− | draw((0,0) | + | label("$"+string(i+84.5)+"$",(i,0.5),fontsize(9pt)); |
− | + | } | |
+ | |||
+ | draw(circle((6.5,1.5),0.45)); draw(circle((6.5,0.5),0.45)); | ||
+ | draw(circle((7.5,1.5),0.45)); draw(circle((7.5,0.5),0.45)); | ||
+ | draw(circle((8.5,1.5),0.45)); draw(circle((8.5,0.5),0.45)); | ||
+ | draw(circle((13.5,2.5),0.45)); draw(circle((13.5,1.5),0.45)); draw(circle((13.5,0.5),0.45)); | ||
+ | draw(circle((14.5,2.5),0.45)); draw(circle((14.5,1.5),0.45)); draw(circle((14.5,0.5),0.45)); | ||
+ | draw(circle((20.5,2.5),0.45)); draw(circle((20.5,1.5),0.45)); | ||
+ | draw(circle((23.5,2.5),0.45)); draw(circle((23.5,1.5),0.45)); | ||
+ | draw(circle((29.5,2.5),0.45)); draw(circle((29.5,1.5),0.45)); | ||
+ | draw(circle((30.5,2.5),0.45)); draw(circle((30.5,1.5),0.45)); | ||
+ | draw(circle((35.5,2.5),0.45)); draw(circle((35.5,1.5),0.45)); | ||
+ | draw(circle((36.5,2.5),0.45)); draw(circle((36.5,1.5),0.45)); | ||
+ | draw(circle((37.5,2.5),0.45)); draw(circle((37.5,1.5),0.45)); | ||
+ | |||
+ | draw((9,3)--(42,3)); | ||
+ | draw((0,2)--(42,2)); | ||
+ | draw((0,1)--(42,1)); | ||
+ | draw((0,0)--(15,0)); | ||
+ | |||
+ | for (real i=0; i<9; ++i) | ||
+ | { | ||
+ | draw((i,2)--(i,0)); | ||
+ | } | ||
− | + | for (real i=9; i<16; ++i) | |
+ | { | ||
+ | draw((i,3)--(i,0)); | ||
+ | } | ||
+ | for (real i=16; i<=42; ++i) | ||
+ | { | ||
+ | draw((i,3)--(i,1)); | ||
+ | } | ||
+ | </asy> | ||
+ | From the second row of the table above, we perform casework on the possible maximum value of <math>S:</math> | ||
<cmath>\begin{array}{c||c|c|l} | <cmath>\begin{array}{c||c|c|l} | ||
& & & \\ [-2.5ex] | & & & \\ [-2.5ex] | ||
Line 105: | Line 94: | ||
80 & \{77,78,79,80\} & & \text{The student who gets } 80 \text{ will reply yes.} | 80 & \{77,78,79,80\} & & \text{The student who gets } 80 \text{ will reply yes.} | ||
\end{array}</cmath> | \end{array}</cmath> | ||
− | |||
Finally, all possibilities for <math>S</math> are <math>\{34,35,36,37\}, \{47,48,49,50\}, \{76,77,78,79\},</math> and <math>\{89,90,91,92\},</math> from which the answer is <math>37+50+79+92=\boxed{258}.</math> | Finally, all possibilities for <math>S</math> are <math>\{34,35,36,37\}, \{47,48,49,50\}, \{76,77,78,79\},</math> and <math>\{89,90,91,92\},</math> from which the answer is <math>37+50+79+92=\boxed{258}.</math> | ||
− | <u><b> | + | <u><b>Remarks</b></u> |
− | + | <ol style="margin-left: 1.5em;"> | |
− | + | <li>Alternatively, we can reconstruct the second table in this solution as follows, where Y and N denote the replies of "yes" and "no", respectively. Notice that this table has some kind of symmetry! | |
<asy> | <asy> | ||
Line 126: | Line 114: | ||
} | } | ||
− | fill((4,1)--(8,1)--(8,2)--(4,2)--cycle, | + | fill((4,1)--(8,1)--(8,2)--(4,2)--cycle,mediumgray); |
− | fill((33,1)--(37,1)--(37,2)--(33,2)--cycle, | + | fill((33,1)--(37,1)--(37,2)--(33,2)--cycle,mediumgray); |
fill((42,4)--(41,4)--(41,3)--cycle,yellow); | fill((42,4)--(41,4)--(41,3)--cycle,yellow); | ||
fill((42,4)--(42,3)--(41,3)--cycle,green); | fill((42,4)--(42,3)--(41,3)--cycle,green); | ||
− | + | for (real i=0.5; i<=41.5; ++i) { | |
− | label(" | + | label("$"+string(i+42.5)+"$",(i,3.5),fontsize(9pt)); |
− | + | } | |
− | + | ||
− | + | draw(circle((6.5,3.5),0.45)); | |
− | + | draw(circle((7.5,3.5),0.45)); | |
− | + | draw(circle((8.5,3.5),0.45)); | |
− | + | draw(circle((13.5,3.5),0.45)); | |
− | + | draw(circle((14.5,3.5),0.45)); | |
− | + | draw(circle((20.5,3.5),0.45)); | |
− | + | draw(circle((23.5,3.5),0.45)); | |
− | + | draw(circle((29.5,3.5),0.45)); | |
− | + | draw(circle((30.5,3.5),0.45)); | |
− | + | draw(circle((35.5,3.5),0.45)); | |
+ | draw(circle((36.5,3.5),0.45)); | ||
+ | draw(circle((37.5,3.5),0.45)); | ||
− | label("Y",(3.5,2.5), | + | label("Y",(3.5,2.5),blue); label("N",(4.5,2.5),blue); |
− | label("N",(5.5,2.5), | + | label("N",(5.5,2.5),blue); label("N",(6.5,2.5),blue); |
− | label("N",(4.5,1.5), | + | label("N",(4.5,1.5),blue); label("N",(5.5,1.5),blue); |
− | label("N",(6.5,1.5), | + | label("N",(6.5,1.5),blue); label("N",(7.5,1.5),blue); |
− | label("N",(5.5,0.5), | + | label("N",(5.5,0.5),blue); label("N",(6.5,0.5),blue); |
− | label("N",(7.5,0.5), | + | label("N",(7.5,0.5),blue); label("Y",(8.5,0.5),blue); |
− | label("Y",(10.5,2.5), | + | label("Y",(10.5,2.5),blue); label("N",(11.5,2.5),blue); |
− | label("N",(12.5,2.5), | + | label("N",(12.5,2.5),blue); label("N",(13.5,2.5),blue); |
− | label("N",(11.5,1.5), | + | label("N",(11.5,1.5),blue); label("N",(12.5,1.5),blue); |
− | label("N",(13.5,1.5), | + | label("N",(13.5,1.5),blue); label("Y",(14.5,1.5),blue); |
− | label("Y",(17.5,2.5), | + | label("Y",(17.5,2.5),blue); label("Y",(18.5,2.5),blue); |
− | label("Y",(19.5,2.5), | + | label("Y",(19.5,2.5),blue); label("N",(20.5,2.5),blue); |
− | label("N",(20.5,1.5), | + | label("N",(20.5,1.5),blue); label("Y",(21.5,1.5),blue); |
− | label("Y",(22.5,1.5), | + | label("Y",(22.5,1.5),blue); label("Y",(23.5,1.5),blue); |
− | label("Y",(26.5,2.5), | + | label("Y",(26.5,2.5),blue); label("N",(27.5,2.5),blue); |
− | label("N",(28.5,2.5), | + | label("N",(28.5,2.5),blue); label("N",(29.5,2.5),blue); |
− | label("N",(27.5,1.5), | + | label("N",(27.5,1.5),blue); label("N",(28.5,1.5),blue); |
− | label("N",(29.5,1.5), | + | label("N",(29.5,1.5),blue); label("Y",(30.5,1.5),blue); |
− | label("Y",(32.5,2.5), | + | label("Y",(32.5,2.5),blue); label("N",(33.5,2.5),blue); |
− | label("N",(34.5,2.5), | + | label("N",(34.5,2.5),blue); label("N",(35.5,2.5),blue); |
− | label("N",(33.5,1.5), | + | label("N",(33.5,1.5),blue); label("N",(34.5,1.5),blue); |
− | label("N",(35.5,1.5), | + | label("N",(35.5,1.5),blue); label("N",(36.5,1.5),blue); |
− | label("N",(34.5,0.5), | + | label("N",(34.5,0.5),blue); label("N",(35.5,0.5),blue); |
− | label("N",(36.5,0.5), | + | label("N",(36.5,0.5),blue); label("Y",(37.5,0.5),blue); |
− | + | for (real i=0; i<=42; ++i) | |
+ | { | ||
+ | draw((i,4)--(i,3)); | ||
+ | } | ||
− | + | draw((0,4)--(42,4)); | |
− | + | draw((0,3)--(42,3)); | |
− | + | </asy></li> | |
− | draw((0,3 | + | <li>As a confirmation, we can verify that each student will be able to deduce what <math>S</math> is upon hearing the four replies of "no" in unison. For example, if <math>S=\{47,48,49,50\},</math> then all students will know that no one gets <math>46</math> or <math>51,</math> otherwise that student will reply yes (as discussed). Therefore, all students will conclude that <math>S</math> has only one possibility.</li><p> |
− | + | </ol> | |
− | |||
− | |||
− | </ | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | We know right away that <math>42\not\in S</math> and <math>84\not\in S</math> as stated in Solution 1. | ||
+ | |||
+ | To get a feel for the problem, let’s write out some possible values of <math>S</math> based on the teacher’s remarks. The first multiple of 7 that is two-digit is 14. The closest multiple of six from 14 is 12, and therefore there are two possible sets of four consecutive integers containing 12 and 14; <math>\{11,12,13,14\}</math> and <math>\{12,13,14,15\}</math>. Here we get our first crucial idea; that if the multiples of 6 and 7 differ by two, there will be 2 possible sets of <math>S</math> without any student input. Similarly, if they differ by 3, there will be only 1 possible set, and if they differ by 1, 3 possible sets. | ||
+ | |||
+ | Now we read the student input. Each student says they can’t figure out what <math>S</math> is just based on the teacher’s information, which means each student has to have a number that would be in 2 or 3 of the possible sets (This is based off of the first line of student input). However, now that each student knows that all of them have numbers that fit into more than one possible set, this means that S cannot have two possible sets because otherwise, when shifting from one set to the other, one of the end numbers would not be in the shifted set, but we know each number has to fall in two or more possible sets. For example, take <math>\{11,12,13,14\}</math> and <math>\{12,13,14,15\}</math>. The numbers at the end, 11 and 15, only fall in one set, but each number must fall in at least two sets. This means that there must be three possible sets of S, in which case the actual S would be the middle S. | ||
+ | Take for example <math>\{33,34,35,36\}</math>, <math>\{34,35,36,37\}</math>, and <math>\{35,36,37,38\}</math>. 37 and 34 fall in two sets while 35 and 36 fall in all three sets, so the condition is met. Now, this means that the multiple of 6 and 7 must differ by 1. | ||
+ | Since 42 means the difference is 0, when you add/subtract 6 and 7, you will obtain the desired difference of 1, and similarly adding/subtracting 6 or 7 from 84 will also obtain the difference of 1. Thus there are four possible sets of <math>S</math>; <math>\{34,35,36,37\}</math>, <math>\{47,48,49,50\}</math>, <math>\{76,77,78,79\}</math> and <math>\{89,90,91,92.\}</math>. Therefore the sum of the greatest elements of the possible sets <math>S</math> is <math>37+50+79+92=\boxed{258}</math> | ||
+ | |||
+ | ~KingRavi | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | In a solution that satisfies these constraints, the multiple of 6 must be adjacent to multiple of 7. The other two numbers must be on either side. | ||
+ | |||
+ | WLOG assume the set is <math>\{a,6j,7k,b\}</math>. The student with numbers <math>a</math>, <math>6j</math>, and <math>7k</math> can think the set is <math>\{a-1, a,6j,7k\}</math> or <math>\{a,6j,7k,b\}</math>, and the students with number <math>6j</math>, <math>7k</math>, and <math>b</math> can think the set is <math>\{a,6j,7k,b\}</math> or <math>\{6j,7k,b, b+1\}</math>. Therefore, none of the students know the set for sure. | ||
+ | |||
+ | Playing around with the arrangement of the multiple of 6 and multiple of 7 shows that this is the only configuration viewed as ambiguous to all the students. (Therefore when they hear nobody else knows either, they can find out it is this configuration) | ||
+ | |||
+ | Considering <math>S</math> as <math>\{a,6j,7k,b\}</math>,b is 2 mod 6 and 1 mod 7, so <math>b</math> is 8 mod 42. (since it is all 2-digit, the values are either 50 or 92). | ||
+ | |||
+ | Similarly, considering <math>S</math> as <math>\{a,7j,6k,b\}</math>, <math>b</math> is 1 mod 6 and 2 mod 7, so <math>b</math> is 37 mod 42. The values that satisfy that are 37 and 79. | ||
+ | |||
+ | The total sum of all these values is therefore <math>50+92+37+89=\boxed{258}</math>. | ||
+ | |||
+ | This solution will even work when the bounds (in this question, 2-digit so <100) are much larger and it is impractical to perform casework. | ||
+ | |||
+ | ~balav123 | ||
+ | |||
+ | ==Solution 4 (Logic)== | ||
+ | |||
+ | Consider the tuple <math>(a, a+1, a+2, a+3)</math> as a possible <math>S</math>. If one of the values in <math>S</math> is <math>3</math> or <math>4 \pmod{7}</math>, observe the student will be able to deduce <math>S</math> with no additional information. This is because, if a value is <math>b = 3 \pmod{7}</math> and <math>S</math> contains a <math>0 \pmod{7}</math>, then the values of <math>S</math> must be <math>(b-3, b-2, b-1, b)</math>. Similarly, if we are given a <math>b \equiv 4 \pmod{7}</math> and we know that <math>0 \pmod{7}</math> is in <math>S</math>, <math>S</math> must be <math>(b, b+1, b+2, b+3).</math> Hence, the only possibility for <math>a</math> is <math>5, 6 \pmod{7}.</math> | ||
+ | |||
+ | In either case, we are guaranteed there is a <math>6, 0, 1 \pmod{7}</math> value in <math>7</math>. The difference comes down to if there is a <math>5 \pmod{7}</math> value or a <math>1 \pmod{7}</math> value. The person receiving such value will be able to determine all of <math>S</math> but the <math>6, 0, 1 \pmod{7}</math> people will not be able to differentiate the two cases ... yet. | ||
+ | |||
+ | Now consider which value among the consecutive integers is <math>c \equiv 3 \pmod{6}</math>, if any. The person will know that <math>S</math> is either <math>(c-3, c-2, c-1, c)</math> or <math>(c, c+1, c+2, c+3)</math> to have a <math>0 \pmod{6}</math> value in <math>S</math>. Neither the <math>6, 1 \pmod{7}</math> person can be <math>3 \pmod{7}</math>, else they can decipher what <math>S</math> is right off the bat by considering which set has <math>0 \pmod{7}.</math> This translates to the possible <math>5 \pmod{7}</math> or <math>1 \pmod{7}</math> person cannot be <math>0 \pmod{6}</math>. We are given that <math>0 \pmod{7}</math> and <math>0 \pmod{6}</math> cannot be the same person. Hence we conclude one of the <math>6 \pmod{7}</math> or <math>1 \pmod{7}</math> must be the <math>0 \pmod{6}</math> person. | ||
+ | |||
+ | Let the <math>6 \pmod{7}</math> person be <math>0 \pmod{6}.</math> Then--hypothetical--<math>c \equiv 2 \pmod{7}</math> person is <math>3 \pmod{6}.</math> After the first round, the <math>6, 0, 1 \pmod{7}</math> people realize that <math>2 \pmod{7}</math> is not in <math>S</math> else they would have deduced <math>S</math> by noting <math>S</math> was either <math>(c-3, c-2, c-1, c)</math> or <math>(c, c+1, c+2, c+3)</math> to have a <math>0 \pmod{6}</math> and choosing the former based on where <math>0 \pmod{7}</math> is. Hence they figure out <math>S</math> by knowing <math>5 \pmod{7}.</math> So <math>a \equiv 5 \pmod{7}</math> and <math>a \equiv 5 \pmod{6}</math> (from <math>6 \pmod{7}</math> person being <math>0 \pmod{6}</math>). | ||
+ | |||
+ | Similarly, if <math>1 \pmod{7}</math> person is <math>0 \pmod{6}</math> we find that <math>a \equiv 6 \pmod{7}</math> (so a <math>2 \pmod{7}</math> is in <math>S</math>) and <math>a \equiv 4 \pmod{6}.</math> | ||
+ | |||
+ | By CRT, the possibilities are <math>a \equiv 5, 34 \pmod{42}.</math> The sum of the greatest values of <math>S</math> are the sum of <math>a + 3</math> and so we get <math>(34 + 3) + (47 + 3) + (76 + 3) + (89 + 3) = \boxed{258}.</math> | ||
+ | |||
+ | ~Aaryabhatta1 | ||
==Video Solution== | ==Video Solution== | ||
https://www.youtube.com/watch?v=7jKjilTRhs4 | https://www.youtube.com/watch?v=7jKjilTRhs4 | ||
+ | |||
+ | ==Animated Solution by Interstigation== | ||
+ | https://youtu.be/TKXU33jnXkI | ||
+ | |||
+ | ~Interstigation | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2021|n=II|num-b=10|num-a=12}} | {{AIME box|year=2021|n=II|num-b=10|num-a=12}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 10:59, 4 February 2024
Contents
Problem
A teacher was leading a class of four perfectly logical students. The teacher chose a set of four integers and gave a different number in
to each student. Then the teacher announced to the class that the numbers in
were four consecutive two-digit positive integers, that some number in
was divisible by
, and a different number in
was divisible by
. The teacher then asked if any of the students could deduce what
is, but in unison, all of the students replied no.
However, upon hearing that all four students replied no, each student was able to determine the elements of . Find the sum of all possible values of the greatest element of
.
Solution 1
Note that It is clear that
and
otherwise the three other elements in
are divisible by neither
nor
In the table below, the multiples of are colored in yellow, and the multiples of
are colored in green. By the least common multiple, we obtain cycles: If
is a possible maximum value of
then
must be another possible maximum value of
and vice versa. By observations, we circle all possible maximum values of
From the second row of the table above, we perform casework on the possible maximum value of
Finally, all possibilities for
are
and
from which the answer is
Remarks
- Alternatively, we can reconstruct the second table in this solution as follows, where Y and N denote the replies of "yes" and "no", respectively. Notice that this table has some kind of symmetry!
- As a confirmation, we can verify that each student will be able to deduce what
is upon hearing the four replies of "no" in unison. For example, if
then all students will know that no one gets
or
otherwise that student will reply yes (as discussed). Therefore, all students will conclude that
has only one possibility.
~MRENTHUSIASM
Solution 2
We know right away that and
as stated in Solution 1.
To get a feel for the problem, let’s write out some possible values of based on the teacher’s remarks. The first multiple of 7 that is two-digit is 14. The closest multiple of six from 14 is 12, and therefore there are two possible sets of four consecutive integers containing 12 and 14;
and
. Here we get our first crucial idea; that if the multiples of 6 and 7 differ by two, there will be 2 possible sets of
without any student input. Similarly, if they differ by 3, there will be only 1 possible set, and if they differ by 1, 3 possible sets.
Now we read the student input. Each student says they can’t figure out what is just based on the teacher’s information, which means each student has to have a number that would be in 2 or 3 of the possible sets (This is based off of the first line of student input). However, now that each student knows that all of them have numbers that fit into more than one possible set, this means that S cannot have two possible sets because otherwise, when shifting from one set to the other, one of the end numbers would not be in the shifted set, but we know each number has to fall in two or more possible sets. For example, take
and
. The numbers at the end, 11 and 15, only fall in one set, but each number must fall in at least two sets. This means that there must be three possible sets of S, in which case the actual S would be the middle S.
Take for example
,
, and
. 37 and 34 fall in two sets while 35 and 36 fall in all three sets, so the condition is met. Now, this means that the multiple of 6 and 7 must differ by 1.
Since 42 means the difference is 0, when you add/subtract 6 and 7, you will obtain the desired difference of 1, and similarly adding/subtracting 6 or 7 from 84 will also obtain the difference of 1. Thus there are four possible sets of
;
,
,
and
. Therefore the sum of the greatest elements of the possible sets
is
~KingRavi
Solution 3
In a solution that satisfies these constraints, the multiple of 6 must be adjacent to multiple of 7. The other two numbers must be on either side.
WLOG assume the set is . The student with numbers
,
, and
can think the set is
or
, and the students with number
,
, and
can think the set is
or
. Therefore, none of the students know the set for sure.
Playing around with the arrangement of the multiple of 6 and multiple of 7 shows that this is the only configuration viewed as ambiguous to all the students. (Therefore when they hear nobody else knows either, they can find out it is this configuration)
Considering as
,b is 2 mod 6 and 1 mod 7, so
is 8 mod 42. (since it is all 2-digit, the values are either 50 or 92).
Similarly, considering as
,
is 1 mod 6 and 2 mod 7, so
is 37 mod 42. The values that satisfy that are 37 and 79.
The total sum of all these values is therefore .
This solution will even work when the bounds (in this question, 2-digit so <100) are much larger and it is impractical to perform casework.
~balav123
Solution 4 (Logic)
Consider the tuple as a possible
. If one of the values in
is
or
, observe the student will be able to deduce
with no additional information. This is because, if a value is
and
contains a
, then the values of
must be
. Similarly, if we are given a
and we know that
is in
,
must be
Hence, the only possibility for
is
In either case, we are guaranteed there is a value in
. The difference comes down to if there is a
value or a
value. The person receiving such value will be able to determine all of
but the
people will not be able to differentiate the two cases ... yet.
Now consider which value among the consecutive integers is , if any. The person will know that
is either
or
to have a
value in
. Neither the
person can be
, else they can decipher what
is right off the bat by considering which set has
This translates to the possible
or
person cannot be
. We are given that
and
cannot be the same person. Hence we conclude one of the
or
must be the
person.
Let the person be
Then--hypothetical--
person is
After the first round, the
people realize that
is not in
else they would have deduced
by noting
was either
or
to have a
and choosing the former based on where
is. Hence they figure out
by knowing
So
and
(from
person being
).
Similarly, if person is
we find that
(so a
is in
) and
By CRT, the possibilities are The sum of the greatest values of
are the sum of
and so we get
~Aaryabhatta1
Video Solution
https://www.youtube.com/watch?v=7jKjilTRhs4
Animated Solution by Interstigation
~Interstigation
See Also
2021 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.