Let A={1,2,3, …, 7} and let P(A) denote the power set of A. If the number of functions f: A → P(A) such that a ∈ f(a), ∀ a ∈ A is mⁿ, m and n ∈ N and m is least, then m+n is equal to _________.

Solution

Maths sir · 4 steps

Each f(a) must contain a, so only the other 6 elements are free: in or out, for every a.

1. One input. Fix one a ∈ A. The subset f(a) must contain a. Each of the remaining 6 elements can be in or out, so f(a) has 2⁶ = 64 choices.
2. All seven inputs. The choice for each of the 7 elements of A is independent. By the fundamental principle of counting, multiply the 7 counts together.

   (2⁶)⁷ = 2⁴²

3. Least base. The same number can be written as 64⁷, 8¹⁴, 4²¹ or 2⁴². The least possible natural base is m = 2, which gives n = 42.
4. So. m + n = 2 + 42 = 44.

The common slip: 71. Stopping at 64⁷ and taking m = 64, n = 7 gives 71. The question wants the least base, so rewrite it as 2⁴².

The idea to keep. When a function's output is a subset with a forced element, count the free elements only: each one is in or out. Then multiply over all inputs.

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