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.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.