Difference between revisions of "2021 AIME II Problems/Problem 11"

(Solution 2 (Illustrations): Solution done.)
 
(29 intermediate revisions by one other user 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 (Text)==
+
==Solution 1==
Let's start by listing the multiples of 6 and 7:
+
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>
6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96;
 
7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, and 98. First of all, the multiples of 6 and 7 wouldn't work, so we can cross out 42 and 84.
 
Since the students said they didn't know the answer, it must be that the set has no distinct integers from the sets. Let's list out the possible sets. Since they are in lists of 4, we need multiples of 6 or 7. Let's list them out.
 
11, 12, 13, 14
 
12, 13, 14, 15
 
But if a student has 11 or 15, they would know. So that wouldn't work.
 
The second set would be this: <math>\{34,35,36,37\}</math> <math>\{47,48,49,50\}</math> <math>\{76,77,78,79\}</math> <math>\{89,90,91,92\}</math>
 
They couldn't know since the multiples of 7 is 35, and if you list it out, they wouldn't know about it since there are other sets such as 35, 36, 37, 38, and 33, 34, 35, 36. The people with these sets would say no, so the second set would WORK. The other sets are only 2 numbers, and since 2 numbers are sufficiently smaller than our 2nd set, we have concluded the answer is 37+50+79+92 = <math>\boxed{258}</math>.
 
~Arcticturn
 
 
 
==Solution 2 (Illustrations)==
 
Note that <math>\text{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>
 
 
 
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 write all possible maximum values of <math>S</math> in red.
 
  
 +
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);
  
for (real i=0.5; i<=2.5; ++i)
+
fill((5,0)--(6,0)--(6,2)--(5,2)--cycle,yellow);
{
+
fill((11,0)--(12,0)--(12,3)--(11,3)--cycle,yellow);
for (real j=5.5; j<41.5; j+=6)
+
fill((17,1)--(18,1)--(18,3)--(17,3)--cycle,yellow);
{
+
fill((23,1)--(24,1)--(24,3)--(23,3)--cycle,yellow);
fill((j+0.5,i+0.5)--(j-0.5,i+0.5)--(j-0.5,i-0.5)--(j+0.5,i-0.5)--cycle,yellow);
+
fill((29,1)--(30,1)--(30,3)--(29,3)--cycle,yellow);
}
+
fill((35,1)--(36,1)--(36,3)--(35,3)--cycle,yellow);
}
 
  
for (real i=0.5; i<=2.5; ++i)
+
fill((6,0)--(7,0)--(7,2)--(6,2)--cycle,green);
{
+
fill((13,0)--(14,0)--(14,3)--(13,3)--cycle,green);
for (real j=6.5; j<41.5; j+=7)
+
fill((20,1)--(21,1)--(21,3)--(20,3)--cycle,green);
{
+
fill((27,1)--(28,1)--(28,3)--(27,3)--cycle,green);
fill((j+0.5,i+0.5)--(j-0.5,i+0.5)--(j-0.5,i-0.5)--(j+0.5,i-0.5)--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 45: Line 29:
 
fill((42,3)--(42,2)--(41,2)--cycle,green);
 
fill((42,3)--(42,2)--(41,2)--cycle,green);
 
fill((42,2)--(42,1)--(41,1)--cycle,green);
 
fill((42,2)--(42,1)--(41,1)--cycle,green);
fill((9,3)--(0,3)--(0,2)--(9,2)--cycle,black);
 
fill((42,1)--(15,1)--(15,0)--(42,0)--cycle,black);
 
  
label("10",(9.5,2.5)); label("11",(10.5,2.5)); label("12",(11.5,2.5));
+
for (real i=9.5; i<=41.5; ++i) {
label("13",(12.5,2.5)); label("14",(13.5,2.5),red); label("15",(14.5,2.5),red);
+
  label("$"+string(i+0.5)+"$",(i,2.5),fontsize(9pt));
label("16",(15.5,2.5)); label("17",(16.5,2.5)); label("18",(17.5,2.5));
+
}
label("19",(18.5,2.5)); label("20",(19.5,2.5)); label("21",(20.5,2.5),red);
+
 
label("22",(21.5,2.5)); label("23",(22.5,2.5)); label("24",(23.5,2.5),red);
+
for (real i=0.5; i<=41.5; ++i) {
label("25",(24.5,2.5)); label("26",(25.5,2.5)); label("27",(26.5,2.5));
+
  label("$"+string(i+42.5)+"$",(i,1.5),fontsize(9pt));
label("28",(27.5,2.5)); label("29",(28.5,2.5)); label("30",(29.5,2.5),red);
+
}
label("31",(30.5,2.5),red); label("32",(31.5,2.5)); label("33",(32.5,2.5));
+
 
label("34",(33.5,2.5)); label("35",(34.5,2.5)); label("36",(35.5,2.5),red);
+
for (real i=0.5; i<=14.5; ++i) {
label("37",(36.5,2.5),red); label("38",(37.5,2.5),red); label("39",(38.5,2.5));
+
  label("$"+string(i+84.5)+"$",(i,0.5),fontsize(9pt));
label("40",(39.5,2.5)); label("41",(40.5,2.5)); label("42",(41.5,2.5));
+
}
label("43",(0.5,1.5)); label("44",(1.5,1.5)); label("45",(2.5,1.5));
 
label("46",(3.5,1.5)); label("47",(4.5,1.5)); label("48",(5.5,1.5));
 
label("49",(6.5,1.5),red); label("50",(7.5,1.5),red); label("51",(8.5,1.5),red);
 
label("52",(9.5,1.5)); label("53",(10.5,1.5)); label("54",(11.5,1.5));
 
label("55",(12.5,1.5)); label("56",(13.5,1.5),red); label("57",(14.5,1.5),red);
 
label("58",(15.5,1.5)); label("59",(16.5,1.5)); label("60",(17.5,1.5));
 
label("61",(18.5,1.5)); label("62",(19.5,1.5)); label("63",(20.5,1.5),red);
 
label("64",(21.5,1.5)); label("65",(22.5,1.5)); label("66",(23.5,1.5),red);
 
label("67",(24.5,1.5)); label("68",(25.5,1.5)); label("69",(26.5,1.5));
 
label("70",(27.5,1.5)); label("71",(28.5,1.5)); label("72",(29.5,1.5),red);
 
label("73",(30.5,1.5),red); label("74",(31.5,1.5)); label("75",(32.5,1.5));
 
label("76",(33.5,1.5)); label("77",(34.5,1.5)); label("78",(35.5,1.5),red);
 
label("79",(36.5,1.5),red); label("80",(37.5,1.5),red); label("81",(38.5,1.5));
 
label("82",(39.5,1.5)); label("83",(40.5,1.5)); label("84",(41.5,1.5));
 
label("85",(0.5,0.5)); label("86",(1.5,0.5)); label("87",(2.5,0.5));
 
label("88",(3.5,0.5)); label("89",(4.5,0.5)); label("90",(5.5,0.5));
 
label("91",(6.5,0.5),red); label("92",(7.5,0.5),red); label("93",(8.5,0.5),red);
 
label("94",(9.5,0.5)); label("95",(10.5,0.5)); label("96",(11.5,0.5));
 
label("97",(12.5,0.5)); label("98",(13.5,0.5),red); label("99",(14.5,0.5),red);
 
  
add(grid(42,3));
+
draw(circle((6.5,1.5),0.45)); draw(circle((6.5,0.5),0.45));
</asy>
+
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));
 +
}
  
From the second row of the table above, we perform casework on the maximum value of <math>S:</math>
+
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 102: 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>Remarks</b></u>
 
<u><b>Remarks</b></u>
 
+
<ol style="margin-left: 1.5em;">
We can reconstruct the second table in this solution as follows, where Y and N stand for replies of "yes" and "no", respectively. Notice that this table has some kind of symmetry!
+
  <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 123: Line 114:
 
}
 
}
  
 +
fill((4,1)--(8,1)--(8,2)--(4,2)--cycle,mediumgray);
 +
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);
fill((0,3)--(0,0)--(5,0)--(5,1)--(4,1)--(4,2)--(3,2)--(3,3)--cycle,black);
 
fill((7,3)--(7,2)--(8,2)--(8,1)--(9,1)--(9,0)--(34,0)--(34,1)--(33,1)--(33,2)--(32,2)--(32,3)--(30,3)--(30,2)--(31,2)--(31,1)--(27,1)--(27,2)--(26,2)--(26,3)--(21,3)--(21,2)--(24,2)--(24,1)--(20,1)--(20,2)--(17,2)--(17,3)--(14,3)--(14,2)--(15,2)--(15,1)--(11,1)--(11,2)--(10,2)--(10,3)--cycle,black);
 
fill((36,3)--(36,2)--(37,2)--(37,1)--(38,1)--(38,0)--(42,0)--(42,3)--cycle,black);
 
  
label("43",(0.5,3.5)); label("44",(1.5,3.5)); label("45",(2.5,3.5));
+
for (real i=0.5; i<=41.5; ++i) {
label("46",(3.5,3.5)); label("47",(4.5,3.5)); label("48",(5.5,3.5));
+
  label("$"+string(i+42.5)+"$",(i,3.5),fontsize(9pt));
label("49",(6.5,3.5),red); label("50",(7.5,3.5),red); label("51",(8.5,3.5),red);
+
}
label("52",(9.5,3.5)); label("53",(10.5,3.5)); label("54",(11.5,3.5));
+
 
label("55",(12.5,3.5)); label("56",(13.5,3.5),red); label("57",(14.5,3.5),red);
+
draw(circle((6.5,3.5),0.45));
label("58",(15.5,3.5)); label("59",(16.5,3.5)); label("60",(17.5,3.5));
+
draw(circle((7.5,3.5),0.45));
label("61",(18.5,3.5)); label("62",(19.5,3.5)); label("63",(20.5,3.5),red);
+
draw(circle((8.5,3.5),0.45));
label("64",(21.5,3.5)); label("65",(22.5,3.5)); label("66",(23.5,3.5),red);
+
draw(circle((13.5,3.5),0.45));
label("67",(24.5,3.5)); label("68",(25.5,3.5)); label("69",(26.5,3.5));
+
draw(circle((14.5,3.5),0.45));
label("70",(27.5,3.5)); label("71",(28.5,3.5)); label("72",(29.5,3.5),red);
+
draw(circle((20.5,3.5),0.45));
label("73",(30.5,3.5),red); label("74",(31.5,3.5)); label("75",(32.5,3.5));
+
draw(circle((23.5,3.5),0.45));
label("76",(33.5,3.5)); label("77",(34.5,3.5)); label("78",(35.5,3.5),red);
+
draw(circle((29.5,3.5),0.45));
label("79",(36.5,3.5),red); label("80",(37.5,3.5),red); label("81",(38.5,3.5));
+
draw(circle((30.5,3.5),0.45));
label("82",(39.5,3.5)); label("83",(40.5,3.5)); label("84",(41.5,3.5));
+
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),heavycyan); label("N",(4.5,2.5),heavycyan);  
+
label("Y",(3.5,2.5),blue); label("N",(4.5,2.5),blue);  
label("N",(5.5,2.5),heavycyan); label("N",(6.5,2.5),heavycyan);  
+
label("N",(5.5,2.5),blue); label("N",(6.5,2.5),blue);  
label("N",(4.5,1.5),heavycyan); label("N",(5.5,1.5),heavycyan);  
+
label("N",(4.5,1.5),blue); label("N",(5.5,1.5),blue);  
label("N",(6.5,1.5),heavycyan); label("N",(7.5,1.5),heavycyan);  
+
label("N",(6.5,1.5),blue); label("N",(7.5,1.5),blue);  
label("N",(5.5,0.5),heavycyan); label("N",(6.5,0.5),heavycyan);  
+
label("N",(5.5,0.5),blue); label("N",(6.5,0.5),blue);  
label("N",(7.5,0.5),heavycyan); label("Y",(8.5,0.5),heavycyan);  
+
label("N",(7.5,0.5),blue); label("Y",(8.5,0.5),blue);  
label("Y",(10.5,2.5),heavycyan); label("N",(11.5,2.5),heavycyan);  
+
label("Y",(10.5,2.5),blue); label("N",(11.5,2.5),blue);  
label("N",(12.5,2.5),heavycyan); label("N",(13.5,2.5),heavycyan);  
+
label("N",(12.5,2.5),blue); label("N",(13.5,2.5),blue);  
label("N",(11.5,1.5),heavycyan); label("N",(12.5,1.5),heavycyan);  
+
label("N",(11.5,1.5),blue); label("N",(12.5,1.5),blue);  
label("N",(13.5,1.5),heavycyan); label("Y",(14.5,1.5),heavycyan);  
+
label("N",(13.5,1.5),blue); label("Y",(14.5,1.5),blue);  
label("Y",(17.5,2.5),heavycyan); label("Y",(18.5,2.5),heavycyan);  
+
label("Y",(17.5,2.5),blue); label("Y",(18.5,2.5),blue);  
label("Y",(19.5,2.5),heavycyan); label("N",(20.5,2.5),heavycyan);  
+
label("Y",(19.5,2.5),blue); label("N",(20.5,2.5),blue);  
label("N",(20.5,1.5),heavycyan); label("Y",(21.5,1.5),heavycyan);  
+
label("N",(20.5,1.5),blue); label("Y",(21.5,1.5),blue);  
label("Y",(22.5,1.5),heavycyan); label("Y",(23.5,1.5),heavycyan);  
+
label("Y",(22.5,1.5),blue); label("Y",(23.5,1.5),blue);  
label("Y",(26.5,2.5),heavycyan); label("N",(27.5,2.5),heavycyan);  
+
label("Y",(26.5,2.5),blue); label("N",(27.5,2.5),blue);  
label("N",(28.5,2.5),heavycyan); label("N",(29.5,2.5),heavycyan);  
+
label("N",(28.5,2.5),blue); label("N",(29.5,2.5),blue);  
label("N",(27.5,1.5),heavycyan); label("N",(28.5,1.5),heavycyan);  
+
label("N",(27.5,1.5),blue); label("N",(28.5,1.5),blue);  
label("N",(29.5,1.5),heavycyan); label("Y",(30.5,1.5),heavycyan);  
+
label("N",(29.5,1.5),blue); label("Y",(30.5,1.5),blue);  
label("Y",(32.5,2.5),heavycyan); label("N",(33.5,2.5),heavycyan);  
+
label("Y",(32.5,2.5),blue); label("N",(33.5,2.5),blue);  
label("N",(34.5,2.5),heavycyan); label("N",(35.5,2.5),heavycyan);  
+
label("N",(34.5,2.5),blue); label("N",(35.5,2.5),blue);  
label("N",(33.5,1.5),heavycyan); label("N",(34.5,1.5),heavycyan);  
+
label("N",(33.5,1.5),blue); label("N",(34.5,1.5),blue);  
label("N",(35.5,1.5),heavycyan); label("N",(36.5,1.5),heavycyan);  
+
label("N",(35.5,1.5),blue); label("N",(36.5,1.5),blue);  
label("N",(34.5,0.5),heavycyan); label("N",(35.5,0.5),heavycyan);  
+
label("N",(34.5,0.5),blue); label("N",(35.5,0.5),blue);  
label("N",(36.5,0.5),heavycyan); label("Y",(37.5,0.5),heavycyan);  
+
label("N",(36.5,0.5),blue); label("Y",(37.5,0.5),blue);  
  
add(grid(42,4));
+
for (real i=0; i<=42; ++i)
</asy>
+
{
 +
    draw((i,4)--(i,3));
 +
}
 +
 
 +
draw((0,4)--(42,4));
 +
draw((0,3)--(42,3));
 +
</asy></li>
 +
  <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 above. But where to go from here?
 +
 +
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
  
 
==Video Solution==
 
==Video Solution==

Latest revision as of 00:55, 25 November 2021

Problem

A teacher was leading a class of four perfectly logical students. The teacher chose a set $S$ of four integers and gave a different number in $S$ to each student. Then the teacher announced to the class that the numbers in $S$ were four consecutive two-digit positive integers, that some number in $S$ was divisible by $6$, and a different number in $S$ was divisible by $7$. The teacher then asked if any of the students could deduce what $S$ 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 $S$. Find the sum of all possible values of the greatest element of $S$.

Solution 1

Note that $\operatorname{lcm}(6,7)=42.$ It is clear that $42\not\in S$ and $84\not\in S,$ otherwise the three other elements in $S$ are divisible by neither $6$ nor $7.$

In the table below, the multiples of $6$ are colored in yellow, and the multiples of $7$ are colored in green. By the least common multiple, we obtain cycles: If $n$ is a possible maximum value of $S,$ then $n+42$ must be another possible maximum value of $S,$ and vice versa. By observations, we circle all possible maximum values of $S.$ [asy] /* Made by MRENTHUSIASM */ 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,2)--(41,2)--(41,1)--cycle,yellow); fill((42,3)--(42,2)--(41,2)--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)); }  for (real i=0.5; i<=41.5; ++i) {    label("$"+string(i+42.5)+"$",(i,1.5),fontsize(9pt)); }  for (real i=0.5; i<=14.5; ++i) {    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 $S:$ \[\begin{array}{c||c|c|l} & & & \\ [-2.5ex] \textbf{Max Value} & \boldsymbol{S} & \textbf{Valid?} & \hspace{16.25mm}\textbf{Reasoning/Conclusion} \\ [0.5ex] \hline & & & \\ [-2ex] 49 & \{46,47,48,49\} & & \text{The student who gets } 46 \text{ will reply yes.} \\ 50 & \{47,48,49,50\} & \checkmark & \text{Another possibility is } S=\{89,90,91,92\}. \\ 51 & \{48,49,50,51\} & & \text{The student who gets } 51 \text{ will reply yes.} \\ 56 & \{53,54,55,56\} & & \text{The student who gets } 53 \text{ will reply yes.} \\ 57 & \{54,55,56,57\} & & \text{The student who gets } 57 \text{ will reply yes.} \\ 63 & \{60,61,62,63\} & & \text{The students who get } 60,61,62 \text{ will reply yes.} \\ 66 & \{63,64,65,66\} & & \text{The students who get } 64,65,66 \text{ will reply yes.} \\ 72 & \{69,70,71,72\} & & \text{The student who gets } 69 \text{ will reply yes.} \\ 73 & \{70,71,72,73\} & & \text{The student who gets } 73 \text{ will reply yes.} \\ 78 & \{75,76,77,78\} & & \text{The student who gets } 75 \text{ will reply yes.} \\ 79 & \{76,77,78,79\} & \checkmark & \text{Another possibility is } S=\{34,35,36,37\}. \\ 80 & \{77,78,79,80\} & & \text{The student who gets } 80 \text{ will reply yes.} \end{array}\] Finally, all possibilities for $S$ are $\{34,35,36,37\}, \{47,48,49,50\}, \{76,77,78,79\},$ and $\{89,90,91,92\},$ from which the answer is $37+50+79+92=\boxed{258}.$

Remarks

  1. 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] /* Made by MRENTHUSIASM */ size(20cm);  for (real j=5.5; j<41.5; j+=6)  { 	fill((j+0.5,4)--(j-0.5,4)--(j-0.5,3)--(j+0.5,3)--cycle,yellow); }  for (real j=6.5; j<41.5; j+=7)  { 	fill((j+0.5,4)--(j-0.5,4)--(j-0.5,3)--(j+0.5,3)--cycle,green); }  fill((4,1)--(8,1)--(8,2)--(4,2)--cycle,mediumgray); fill((33,1)--(37,1)--(37,2)--(33,2)--cycle,mediumgray); fill((42,4)--(41,4)--(41,3)--cycle,yellow); fill((42,4)--(42,3)--(41,3)--cycle,green);  for (real i=0.5; i<=41.5; ++i) {    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),blue); label("N",(4.5,2.5),blue);  label("N",(5.5,2.5),blue); label("N",(6.5,2.5),blue);  label("N",(4.5,1.5),blue); label("N",(5.5,1.5),blue);  label("N",(6.5,1.5),blue); label("N",(7.5,1.5),blue);  label("N",(5.5,0.5),blue); label("N",(6.5,0.5),blue);  label("N",(7.5,0.5),blue); label("Y",(8.5,0.5),blue);  label("Y",(10.5,2.5),blue); label("N",(11.5,2.5),blue);  label("N",(12.5,2.5),blue); label("N",(13.5,2.5),blue);  label("N",(11.5,1.5),blue); label("N",(12.5,1.5),blue);  label("N",(13.5,1.5),blue); label("Y",(14.5,1.5),blue);  label("Y",(17.5,2.5),blue); label("Y",(18.5,2.5),blue);  label("Y",(19.5,2.5),blue); label("N",(20.5,2.5),blue);  label("N",(20.5,1.5),blue); label("Y",(21.5,1.5),blue);  label("Y",(22.5,1.5),blue); label("Y",(23.5,1.5),blue);  label("Y",(26.5,2.5),blue); label("N",(27.5,2.5),blue);  label("N",(28.5,2.5),blue); label("N",(29.5,2.5),blue);  label("N",(27.5,1.5),blue); label("N",(28.5,1.5),blue);  label("N",(29.5,1.5),blue); label("Y",(30.5,1.5),blue);  label("Y",(32.5,2.5),blue); label("N",(33.5,2.5),blue);  label("N",(34.5,2.5),blue); label("N",(35.5,2.5),blue);  label("N",(33.5,1.5),blue); label("N",(34.5,1.5),blue);  label("N",(35.5,1.5),blue); label("N",(36.5,1.5),blue);  label("N",(34.5,0.5),blue); label("N",(35.5,0.5),blue);  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]
  2. As a confirmation, we can verify that each student will be able to deduce what $S$ is upon hearing the four replies of "no" in unison. For example, if $S=\{47,48,49,50\},$ then all students will know that no one gets $46$ or $51,$ otherwise that student will reply yes (as discussed). Therefore, all students will conclude that $S$ has only one possibility.

~MRENTHUSIASM

Solution 2

We know right away that $42\not\in S$ and $84\not\in S$ as stated above. But where to go from here?

To get a feel for the problem, let’s write out some possible values of $S$ 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; $\{11,12,13,14\}$ and $\{12,13,14,15\}$. 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 $S$ 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 $S$ 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 $\{11,12,13,14\}$ and $\{12,13,14,15\}$. 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 $\{33,34,35,36\}$, $\{34,35,36,37\}$, and $\{35,36,37,38\}$. 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 $S$; $\{34,35,36,37\}$, $\{47,48,49,50\}$, $\{76,77,78,79\}$ and $\{89,90,91,92.\}$. Therefore the sum of the greatest elements of the possible sets $S$ is $37+50+79+92=\boxed{258}$

~KingRavi

Video Solution

https://www.youtube.com/watch?v=7jKjilTRhs4

See Also

2021 AIME II (ProblemsAnswer KeyResources)
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

Invalid username
Login to AoPS