Option (D) is correct.
Explanation: Count the different sets C×D, not the different choices of (C,D).
Menus that are not empty. If C=ϕ and D=ϕ, then C×D=ϕ, and the menu tells us C and D back: C is the set of first entries of its pairs and D is the set of second entries. So different choices of non-empty C and D give different menus. There are 23−1=7 non-empty sets C and 24−1=15 non-empty sets D, so
7×15=105
different non-empty menus.
The empty menu. If C=ϕ or D=ϕ, then C×D=ϕ. All these choices give the same set ϕ, which adds just one more menu.
| choice of (C,D) | number of choices | different menus |
|---|
| C=ϕ, D=ϕ | 105 | 105 |
| C=ϕ or D=ϕ | 128−105=23 | 1 |
So a grid menu can offer 105+1=106 different sets of sandwiches.
Why the other options are wrong
- (A) 4096=212 counts every subset of A×B. Most subsets are not of the form C×D: if the breads b1=b2 and the fillings f1=f2, then {(b1,f1),(b2,f2)} is not a grid menu, because a product containing both pairs must also contain (b1,f2).
- (B) 105 leaves out the empty menu ϕ, which is offered whenever C=ϕ or D=ϕ.
- (C) 128=23×24 counts the choices of the pair (C,D). But the 23 choices with an empty factor all give the same set ϕ, so they are one menu, not 23.