Let S = 1, 2, 3, 4. Then the number of elements in the set f : S × S → S : f is onto and f (a, b) = f (b, a) ≥ a ∀ (a, b) ∈ S × S is ______________.

Solution

Maths sir · 4 steps

Symmetry turns f(a,b) ≥ a into f(a,b) ≥ max(a,b). Then group the pairs by their max and count.

1. Use the symmetry. Since f(a,b) = f(b,a) ≥ b as well as ≥ a, we get f(a,b) ≥ max(a,b). Also f only needs a value for each unordered pair {a,b}, which gives 10 values to choose.

   Unordered pairs	Allowed values	Ways
   {1,1}	must be 1, the only pair that can give 1	1
   {1,2}, {2,2}	2, 3 or 4, and the only pairs that can give 2	at least one must be 2
   {1,3}, {2,3}, {3,3}	3 or 4	2³ = 8 if free
   {1,4}, {2,4}, {3,4}, {4,4}	4 only, so 4 is always hit	1

2. Hit the value 2. The two max-2 pairs have 3² = 9 assignments, and 2² = 4 of them avoid 2. That leaves 5: (2,2), (2,3), (3,2), (2,4), (4,2).
3. Hit the value 3. In the 2 cases that already use a 3, the max-3 pairs are free: 8 ways each. In the other 3 cases, the max-3 pairs must not all be 4: 8 - 1 = 7 ways each.

   2 × 8 + 3 × 7 = 16 + 21 = 37

4. So. The number of such onto functions is 37.

The common slip: 40. Forgetting that the value 3 must also be hit, and taking all 8 choices for the max-3 pairs every time, gives 5 × 8 = 40.

The idea to keep. For onto counts with lower bounds, ask which inputs can reach each small value. The smallest values have the fewest sources, so fix those first and count the rest.

Answer from the NTA final answer key. Solution by PrepWiser.