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