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.

The Computer Laboratory

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