# Practice Paper 3 Question 19

Let \(A=\{0, 1, \dots, 2^n-1, 2^n\}\) and \(B = \{0, \dots, n\}\). How many functions \(g\) can be defined from \(A\) to \(B\) such that both of the following conditions hold:

- for all \(x \in B\) we have \(g(2^x) = x,\)
- for all \(y, z \in A\) with \(y \leq z\) we have \(g(y) \leq g(z).\)

## Related topics

## Warm-up Questions

- How many functions \(f\) can be defined from \(\{0,1, \ldots, n\}\) to \(\{1,2,3\}?\)

## Hints

- Hint 1Try expressing constraint (2) in simple words.
- Hint 2What can one say about an interval from \(2^x\) to \(2^{x+1}\) for an arbitrary \(x \in B?\)
- Hint 3Since \(g(2^x)=x,\) \(g(2^{x+1})=x+1\) and \(g\) is a non-decreasing function, what values could inputs \(2^x, \ldots, 2^{x+1}\) take?
- Hint 4Notice that input values in the interval \(2^x\) to \(2^{x+1}\) have output values \(x\) or \(x+1\) and \(g\) is a non-decreasing function. There must be a value at which the output is incremented. How many such values are there?

## Solution

To calculate the number of functions, we should consider how many ways there are to choose an output for each input. First, notice that the second condition means that \(g\) needs to be a non-decreasing function. Now, let's focus on the interval from \(2^x\) to \(2^{x+1}.\) Since \(g(2^x) = x,\) and \(g(2^{x+1}) = x+1\) there is exactly one value at which the output is incremented. There are \(2^x\) input values in this interval at which this could happen. To obtain the final answer we need to multiply the number of possiblities over all the intervals, which is: \[\prod_{i=0}^{n-1} 2^i = 2^{\sum_{i=0}^{n-1} i} = 2^{\frac{n(n-1)}{2}}.\]

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.