# Practice Paper 3 Question 5

How many functions \(g\) can be defined from set \(A = \{0,1, \cdots, 2^n - 1, 2^n\}\) to set \(B = \{0, \cdots, n\}\) such that \(g(2^x) = x\) for all \(x\) in \(B?\)

## Related topics

## Hints

- Hint 1Without any restriction, for each input \(x,\) how many possible output values \(g(x)\) are there?
- Hint 2How do we count the number of possible functions between two sets when we know the sets' cardinality?
- Hint 3How many output values could an input of the form \(2^x\) take if \(x\) is in \(B?\)
- Hint 4How many output values could an input of a different form take?

## Solution

To calculate the number of functions we count how many possible outputs there are for each input. In this case we also have a restriction. For each input of the form \(2^x,\) where \(x\) is in \(B,\) the output value is fixed to \(x;\) that is, every function we define must include these relationships, so the number of possible functions we can define is given only by the other inputs. This leaves only \(2^n-n\) "free" inputs, and for each of these the output could be any of the \(n+1\) elements in \(B.\) Therefore, the number of functions that can be defined is \((n+1)^{2^{n} - n}.\)

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.. Please do not write to this address regarding general admissions or course queries. tasc@sulp.ecitcarp