# 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.[email protected]. Please do not write to this address regarding general admissions or course queries.