The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

# 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:

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

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

## Warm-up Questions

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

## Hints

• Hint 1
Try expressing constraint (2) in simple words.
• Hint 2
What can one say about an interval from $$2^x$$ to $$2^{x+1}$$ for an arbitrary $$x \in B?$$
• Hint 3
Since $$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 4
Notice 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 . Please do not write to this address regarding general admissions or course queries.