RankRizz
JEE MAIN 2022 · 29 JUL S1+4 / −1HARDTRANSCRIBED

JEE Main 2022 Mathematics question — Cartesian products and counting relations

Let S={4,6,9}S = \{4, 6, 9\} and T={9,10,11,…,1000}T = \{9, 10, 11, \ldots, 1000\}. If A={a1+a2+…+ak:k∈N,a1,a2,a3,…,ak∈S}A = \{a_1 + a_2 + \ldots + a_k : k \in \mathbb{N}, a_1, a_2, a_3, \ldots, a_k \in S\}, then the sum of all the elements in the set T−AT - A is equal to _______

SOLUTION

We have S={4,6,9}S = \{4, 6, 9\} and T={9,10,11,…,1000}T = \{9, 10, 11, \ldots, 1000\}. The set AA consists of all numbers that can be represented as a1+a2+⋯+aka_1 + a_2 + \cdots + a_k where each ai∈{4,6,9}a_i \in \{4, 6, 9\} and k∈Nk \in \mathbb{N}. We need to find the sum of all elements in T∖AT \setminus A, i.e., elements of TT that cannot be expressed as such sums.

We note that every element of AA is a non-negative integer combination of 4, 6, and 9 (with at least one term). The elements of AA starting from the smallest are: 4, 6, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, ... We need to find which numbers from 9 onwards are NOT in AA.

We systematically check small values. A number nn is in AA if n=4a+6b+9cn = 4a + 6b + 9c for non-negative integers a,b,ca, b, c with a+b+c≥1a + b + c \geq 1:

n=4n = 4: 4=4(1)4 = 4(1). Yes. n=6n = 6: 6=6(1)6 = 6(1). Yes. n=8n = 8: 8=4(2)8 = 4(2). Yes. n=9n = 9: 9=9(1)9 = 9(1). Yes. n=10n = 10: 10=4+610 = 4+6. Yes. n=12n = 12: 12=4(3)12 = 4(3) or 6(2)6(2). Yes. n=13n = 13: 13=4+913 = 4+9. Yes. n=14n = 14: 14=4+4+614 = 4+4+6. Yes. n=15n = 15: 15=6+915 = 6+9. Yes. n=16n = 16: 16=4(4)16 = 4(4). Yes. n=17n = 17: 17=4+4+917 = 4+4+9. Yes. n=18n = 18: 18=9(2)18 = 9(2) or 4(3)+64(3)+6. Yes.

Now, n=19n = 19: 19=4+6+919 = 4+6+9. Yes. n=20n = 20: 20=4(5)20 = 4(5). Yes. For n=21n = 21: 21=12+9=4(3)+921 = 12+9 = 4(3)+9. Yes. n=22n = 22: 22=4+9+9=4+1822 = 4+9+9 = 4+18. Yes. n=23n = 23: 23=4+4+6+9=14+923 = 4+4+6+9 = 14+9. Yes.

We observe that all integers ≥24\geq 24 can be written as sums: if n≡0(mod4)n \equiv 0 \pmod{4}, use 44's; if n≡1(mod4)n \equiv 1 \pmod{4}, use 9+49 + 4's (since n≥25n \geq 25 gives enough room, and n=9n = 9 works, n=13n = 13 works); if n≡2(mod4)n \equiv 2 \pmod{4}, use 6+46 + 4's; if n≡3(mod4)n \equiv 3 \pmod{4}, use 9+6+49 + 6 + 4's.

More precisely, for n≥24n \geq 24: n≡0(mod2)n \equiv 0 \pmod{2} can always be written as 4a+6b4a + 6b; nn odd and n≥9n \geq 9 can be written as 9+even number≥09 + \text{even number} \geq 0. Since n−9≥15n - 9 \geq 15 for n≥24n \geq 24, and n−9n - 9 is even, and any even number ≥4\geq 4 can be written as 4a+6b4a + 6b (and even numbers ≥4\geq 4: 4, 6, 8, 10, ... all work). Actually even number 0 also works (take nothing extra). So for odd n≥9n \geq 9: n−9n - 9 is even and ≥0\geq 0, and we need n−9≠2n - 9 \neq 2 (since 2 cannot be made from 4s and 6s). n−9=2⇒n=11n - 9 = 2 \Rightarrow n = 11. So n=11n = 11 is the concern.

Let us check n=11n = 11: Can we write 11=4a+6b+9c11 = 4a + 6b + 9c? With c=1c = 1: 2=4a+6b2 = 4a + 6b, no non-negative solution. With c=0c = 0: 11=4a+6b11 = 4a + 6b, impossible (parity: 4a+6b4a + 6b is even, 11 is odd). So n=11∉An = 11 \notin A.

We also need to check numbers less than 24 more carefully. From the set T={9,10,…,1000}T = \{9, 10, \ldots, 1000\}, which values from 9 to 23 are NOT in AA?

n=9n = 9: Yes (checked). n=10n = 10: Yes. n=11n = 11: No (shown above). n=12n = 12: Yes. n=13n = 13: Yes. n=14n = 14: Yes. n=15n = 15: Yes. n=16n = 16: Yes. n=17n = 17: Yes. n=18n = 18: Yes. n=19n = 19: Yes. n=20n = 20: Yes. n=21n = 21: Yes. n=22n = 22: Yes. n=23n = 23: Yes.

For n≥24n \geq 24, every number is representable as argued. So the only element of TT not in AA is n=11n = 11.

Therefore, the sum of all elements in T∖AT \setminus A is 11\boxed{11}.

Hence, the correct answer is 11.

Tagged Cartesian products and counting relations. Machine-assigned, so read it as a strong shortlist rather than a verdict.

TopicCartesian products and counting relations
TypeNumerical answer