Let `S = {1, 2, 3, 4).` The number of functions `f: S->S.`Such that `f(i) le 2i` for all `i in S` is

Options

A. 32
B. 64
C. 128
D. 256

Answer

To solve the problem, we need to determine the number of functions \( f: S \to S \) such that \( f(i) \leq 2i \) for all \( i \in S \), where \( S = \{1, 2, 3, 4\} \).

### Step-by-Step Solution:

1. **Identify the Set**:
The set \( S \) is defined as \( S = \{1, 2, 3, 4\} \).

2. **Determine the Constraints**:
We need to find the values of \( f(i) \) based on the condition \( f(i) \leq 2i \).

3. **Evaluate Each Element in the Set**:
- For \( i = 1 \):
\[ f(1) \leq 2 \times 1 = 2 \]
Possible values for \( f(1) \) are \( \{1, 2\} \). This gives us **2 choices**.

- For \( i = 2 \):
\[ f(2) \leq 2 \times 2 = 4 \]
Possible values for \( f(2) \) are \( \{1, 2, 3, 4\} \). This gives us **4 choices**.

- For \( i = 3 \):
\[ f(3) \leq 2 \times 3 = 6 \]
However, since \( f(3) \) must also be in \( S \), the possible values are \( \{1, 2, 3, 4\} \). This gives us **4 choices**.

- For \( i = 4 \):
\[ f(4) \leq 2 \times 4 = 8 \]
Again, since \( f(4) \) must be in \( S \), the possible values are \( \{1, 2, 3, 4\} \). This gives us **4 choices**.

4. **Calculate the Total Number of Functions**:
The total number of functions can be calculated by multiplying the number of choices for each \( i \):
\[ \text{Total functions} = \text{choices for } f(1) \times \text{choices for } f(2) \times \text{choices for } f(3) \times \text{choices for } f(4) \]
\[ = 2 \times 4 \times 4 \times 4 = 128 \]

5. **Conclusion**:
The total number of functions \( f: S \to S \) such that \( f(i) \leq 2i \) for all \( i \in S \) is **128**.