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 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?\)

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

Hints

  • Hint 1
    Without any restriction, for each input \(x,\) how many possible output values \(g(x)\) are there?
  • Hint 2
    How do we count the number of possible functions between two sets when we know the sets' cardinality?
  • Hint 3
    How many output values could an input of the form \(2^x\) take if \(x\) is in \(B?\)
  • Hint 4
    How 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.foo[email protected]. Please do not write to this address regarding general admissions or course queries.