Maths Olympiad Prep

Library / /485 of 520

Combinatorics Difficulty 4.3 AIME Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

Note that lcm(6,7)=42.\operatorname{lcm}(6,7)=42. It is clear that 42∉S42\not\in S and 84∉S,84\not\in S, otherwise the three other elements in SS are divisible by neither 66 nor 7.7.
In the table below, the multiples of 66 are colored in yellow, and the multiples of 77 are colored in green. By the least common multiple, we obtain cycles: If nn is a possible maximum value of S,S, then n+42n+42 must be another possible maximum value of S,S, and vice versa. By observations, we circle all possible maximum values of S.S.

From the second row of the table above, we perform casework on the possible maximum value of S: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 SS are {34,35,36,37},{47,48,49,50},{76,77,78,79},\{34,35,36,37\}, \{47,48,49,50\}, \{76,77,78,79\}, and {89,90,91,92},\{89,90,91,92\}, from which the answer is 37+50+79+92=258.37+50+79+92=\boxed{258}.
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 SS is upon hearing the four replies of "no" in unison. For example, if S={47,48,49,50},S=\{47,48,49,50\}, then all students will know that no one gets 4646 or 51,51, otherwise that student will reply yes (as discussed). Therefore, all students will conclude that SS has only one possibility.

~MRENTHUSIASM

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.