CAT 2019 Slot 1 DILR Q10
- Data Interpretation and Logical Reasoning
- Logical Reasoning › Math Puzzles
- Medium
- Type in the answer (TITA)
- CAT_2019_SLOT1_DILR_Q10
Data set · questions 9–12
A new game show on TV has 100 boxes numbered 1, 2,..., 100 in a row, each containing a mystery prize. The prizes are items of different types, a, b, c, ..., in decreasing order of value. The most expensive item is of type a, a diamond ring, and there is exactly one of these. You are told that the number of items at least doubles as you move to the next type. For example, there would be at least twice as many items of type b as of type a, at least twice as many items of type c as of type b and so on. There is no particular order in which the prizes are placed in the boxes.
Question 10
What is the maximum possible number of different types of prizes?
Type-in-the-answer (TITA) question: no options are given; enter the value.
Show answer and solution
Answer:
6
Solution
Concept: Greedy Minimum Allocation & Maximum Cardinality Bound
Master State Table
| Prize Tier | Value Rank | Recurrence Inequality | Min Count | Cumulative Min | Feasibility () |
|---|---|---|---|---|---|
| Type a | Rank 1 (Highest) | Passage invariant: | 1 | 1 | Baseline diamond ring |
| Type b | Rank 2 | 2 | 3 | Feasible () | |
| Type c | Rank 3 | 4 | 7 | Feasible () | |
| Type d | Rank 4 | 8 | 15 | Feasible () | |
| Type e | Rank 5 | 16 | 31 | Feasible () | |
| Type f | Rank 6 | 32 | 63 | Feasible () | |
| Type g | Rank 7 | 64 | 127 | Infeasible () | |
| Total Pool | Up to | 100 | Box order arbitrary |
Question Deduction
• Greedy Minimization Strategy:
• To maximize distinct prize types summing to 100, we minimize the count of each type.
• Minimizing earlier type counts maximizes the residual capacity to introduce additional types.
• Generating Minimum Type Quantities:
• Starting with , applying sequentially yields:
• Type $a$: $n(a) = 1$.
• Type $b$: $\min n(b) = 2(1) = 2$.
• Type $c$: $\min n(c) = 2(2) = 4$.
• Type $d$: $\min n(d) = 2(4) = 8$.
• Type $e$: $\min n(e) = 2(8) = 16$.
• Type $f$: $\min n(f) = 2(16) = 32$.
• Type $g$: $\min n(g) = 2(32) = 64$.
• Bounding Cumulative Sums and Ruling Out :
• For 6 types ( through ):
$$\sum_{i=1}^6 \min n(x_i) = 1 + 2 + 4 + 8 + 16 + 32 = 63 \le 100$$
• For 7 types ( through ):
$$\sum_{i=1}^7 \min n(x_i) = 63 + 64 = 127 > 100$$
• Even the absolute minimum allocation for 7 types exceeds 100 boxes by 27. Thus, .
• Constructive Feasibility for 6 Types ():
• Assign minimal counts to the first 5 types (, sum = 31).
• Allocate the remaining boxes to type : .
• Doubling check: , which holds comfortably.
• Hence, the maximum possible number of different types of prizes is 6.
• Numerical Answer:
• 6.
Topper Take
• Binary Power Shortcut: The minimum sum for types is . For , ; for , . This mental calculation establishes the upper bound of 6 types in under 15 seconds.
Other questions in this set
- Q9. What is the minimum possible number of different types of prizes?
- Q11. Which of the following is not possible?
- Q12. You ask for the type of item in box 45. Instead of being given a direct answer, you are told that there are 31 items…
Math Puzzles questions from other CAT papers
- CAT 2025 Slot 1 DILR Q9
- CAT 2025 Slot 1 DILR Q10
- CAT 2025 Slot 1 DILR Q11
- CAT 2025 Slot 1 DILR Q12
- CAT 2025 Slot 1 DILR Q13
Practise this question with timing, notes and your mistake notebook.
Practise in PrepSoc