Combinatorics

11!/8

Each number appears in the \(i\)th place exactly \(4!\) times for \(i\in {1,\ldots,5}\). So the sum of numbers corresponding to each place is
\[ 4!(1+3+5+7+9) = 4!\times 25 = 600 \]
The total sum is therefore:
\[ 10^4\cdot 600 + 10^3\cdot 600 + 10^2\cdot 600 + 10^1\cdot 600 + 600 = 6666600 \]

Let the initial number of people in the party be \(n\). Suppose \(k\) people left the party before Mr. L arrived. The total number of handshakes is then given by:
\[ \binom{n}{2} + (n-k) = 100 \] \[ \binom{n}{2} < 100 < \binom{n+1}{2} \] So \(n=14\) and \(k=5\).

Let us split the students into three categories:

• A-members: Students who belong to one club.
• B-members: Students who belong to two clubs.
• C-members: Students who belong to three clubs.

Each club has 35 slots out of which C-members take up 10 slots. The remaining 25 slots in each club have be to filled with either A or B-members.

Maxima. In order to maximize the number of students we pick only A members. So 75 A-members fill up the remaining slots. The total number of students is then 85.

Minima. There are 75 remaining slots. Each B-student fills up two slots, so there must be at least one A-member. Notice that three B-members can fill up 2 slots of each club. So, 36 B-members can fill up 24 of the remaining slots in each club. The remaining empty slots can be filled up by one B-member and one A-member. So we have 10 C-members, 37 B-members and 1 A-member in all the clubs. In total there are 48 students.

\begin{align} 9S &= 9 + 999 + 99999 + \cdots + \underbrace{99 \cdots 9}_{2k+1} \\ &= (10-1) + (1000-1) + \cdots + (100^{2k+1}-1) \\ &= \frac{10(100^{k+1} - 1)}{99} - (k+1) \\ S&= \frac{ 10^{2k+3} - 99k - 109}{99\times 9} \end{align}

Let us add up the number of sides from each face and call this number T. It is given that there are 11 faces and each face has odd sides, so T is odd. However, in any solid each side is counted twice since two faces intersect to form a side. So T must be even, which is a contradiction. Hence such a solid cannot exist.

Suppose the infinite A.P. is given by

\[ a_0^2 < a_1^2 < a_3^2 < \cdots \]

Without loss of generality, assume that \(a_0>0\). Let the common difference be \(d\neq 0\).

The difference between any two consecutive squares in the A.P. is unbounded, hence at some point \( a_i^2 - a_{i-1}^2 > d \).

Another solution due to Th Ravi Singha: Fix an \(n\). Since the common difference is \(d\), the number \(nd\) has finite number of factors. If \(a^2\) and \(b^2\) are pairs of numbers in the sequence that are \(n\) terms apart, then \(a^2 - b^2 = (a+b)(a-b) = nd\). Since RHS has finite number of factors, there can only be finite number of such pairs.

1. \(36^{7}\).
2. \(36^{7} - 26^7 - 10^7 \).
3. Let \(V=5,C=21,D=10\) and \(S=12\).
   Notation. Let \(P(x_1,\ldots,x_k)\) denote the number \( (x_1+x_2+\ldots+x_k)^7 \) where \( x_i \in \{V,C,D,S\} \).
   By principle of inclusion/exclusion the answer is: \[ P(VCD) - \{P(VC)+P(VD)+P(CD)\} + P(V) + P(C) + P(D) \]
4. \begin{align*} P(VCDS) &- \{ P(VCD) + P(CDS) + P(VCS) + P(VDS) \} \\ &+\{ P(VC)+P(VD)+P(VS)+P(CD)+P(CS)+P(DS)\}\\ &- \{ P(V) + P(C) + P(D) + P(S) \} \end{align*}

(a) There are 6 numbers with one digit, \(6^2\) numbers with two digits and so on. We have \(6^5 < 10000 < 6^6\). So there are only \(10000-6^5=2332\) numbers of six digits.

The total numerals the program would have printed is:
\[ 1\times 6 + 2\times 6^2 + 3\times 6^3 + 4\times 6^4 + 5\times 6^5 + 6\times 2332 = 58782 \]

(b) The given condition translates to : \[ c + 6b + 6^2a = a + 9b + 9^2 c \] which means:
\[ 35a - 3b - 80c = 0 \] Since \(a\) is a digit between 1 and 9, \(35a-80c\) is a multiple of 5, so \(b=5\). This means: \[ 35a - 15 = 80c \] The only digits that satisfy are \(a=5\) and \(b=2\). Hence the number is \(552\).

(a) \(2 \times 8 ! \times 7 !\) (The factor of 2 arises because the two blocks of boys and girls can switch positions.)

(b) \(8 ! \times 7 !\) (There is no factor of 2 because there must be a boy at each end.)

(c) \(\left(\begin{array}{c}15 \\ 6\end{array}\right)\)

(d) \(\left(\begin{array}{c}15 \\ 6\end{array}\right)-\left(\begin{array}{l}8 \\ 3\end{array}\right)\left(\begin{array}{l}7 \\ 3\end{array}\right)=\left(\begin{array}{l}8 \\ 6\end{array}\right)+\left(\begin{array}{l}8 \\ 5\end{array}\right)\left(\begin{array}{l}7 \\ 1\end{array}\right)+\left(\begin{array}{l}8 \\ 4\end{array}\right)\left(\begin{array}{l}7 \\ 2\end{array}\right)+\left(\begin{array}{l}8 \\ 2\end{array}\right)\left(\begin{array}{l}7 \\ 4\end{array}\right)+\left(\begin{array}{l}8 \\ 1\end{array}\right)\left(\begin{array}{l}7 \\ 5\end{array}\right)+\left(\begin{array}{l}7 \\ 6\end{array}\right)\)

From the definition it follows that \( (a,a) \notin R \). For any unordered pair \( \{a,b\} \) there are three possibilities:

• \( (a,b) \in R \)
• \( (b,a) \in R \)
• \( (a,b) \notin R \)

• Type I: \( (S_{k}, T_{n-1}) \) is an edge. There are \(f(k,n-1)\) such arrangements.

  

• Type II: Both \( (S_{k}, T_{n-1}) \) and \( (S_{k-1},T_{n}) \) are not edges. There are \(f(k-1,n-1)\) such arrangements.

  

• Type III: \( (S_{k-1}, T_{n}) \) is an edge. There are \(f(k-1,n-1)\) such arrangements.

  

For the base cases, both \( f(1,n)=1 \) and \( f(k,1)=1 \). For, \(n,k>1\), recurrence is given by: \[ f(k,n) = f(k,n-1) + f(k-1,n-1) + f(k-1,n) \]

Notice that \(f(2,2)=3\). Using the recurrence in part (ii): \begin{align} f(2,n) &= f(2,n-1) + f(1,n-1) + f(1,n) \\ &= f(2,n-1) + 2 \\ &= f(2,2) + 2(n-2) \\ &= 2n-1 \end{align} \begin{align} f(3,n) &= f(3,n-1) + f(2,n-1) + f(2,n) \\ &= f(3,n-1) + 2n-3 + 2n-1\\ &= f(3,n-1) + 4(n-1) \\ &= f(3,n-1) + 4(n-1) \\ &= f(3,n-2) + 4[ (n-2) + (n-1)] \\ &\;\; \vdots \\ &= f(3,1) + 4\cdot \frac{n(n-1)}{2} \\ &= 2n^2-2n+1 \end{align}

(i) As there are \(n\) choices each for the values of \(f(1), \ldots, f(k)\) and as all these choices are independent of each other, the number of functions is \(n^{k}\).

(ii) Note that \(f(A)=\max \{f(\{j\}) \mid j \in A\}\), so the function \(f\) is completely decided by its values on the empty set \(\phi\) and on the one element subsets \(\{1\},\{2\}, \ldots,\{k\} .\) If \(f(\phi)=i,\) then each of \(f(\{1\}), f(\{2\}), \ldots, f(\{k\})\) can be chosen to be any of the numbers \(i, i+1, \ldots, n\) Thus there are \(k\) independent choices for each of which there are \(n-i+1\) options. So the number of desired functions for which \(f(\phi)=i\) is \((n-i+1)^{k} .\) Now we sum over all values of \(i=1,2, \ldots, n\) to get the total number to be \(1^{k}+2^{k}+\cdots+n^{k} .\) (When \(k=3\) and \(n=4\) we get \(1^{3}+2^{3}+3^{3}+4^{3}=100,\) as mentioned in the problem.)

(a) Let \(f(f(x))=f(x)\) and substitute \(y=f(x)\). Then we get \(f(y)=y\), a contradiction.

(b) The above implies that each \(x\) has to map to a fixed point of \(f\), that is, a \(y\) such that \(f(y)=y\). So in order to count the number of such functions we first need to decide the number of fixed points. The number functions that have exactly \(k\) fixed points is \(\left(\begin{array}{l}n \\ k\end{array}\right) k^{n-k}\). In order to get the total number, sum the previous quantity over \(1 \leq k \leq n\).

True. Append A to \(w\).

True. B, AB, AAB, AAAB, ...

False. There are infinitely many such strings e.g. A, AA, AAA, AAAA,

(i) \(10^{2} \times 5^{3}=12500\).

(ii) \(10^{2} \times 4^{3}\) plates without vowel \(\mathrm{O}+9^{2} \times\left(5^{3}-4^{3}\right)\) plates with vowel O but without 0. This gives \(6400+4941=11341\).

(i) Let there be \(a\) steps to the right (east), b steps north-west and c steps southwest. The total number of steps is \(a+b+c .\) The key idea is to think of the northwest step as a move in the complex plane along \(\omega,\) the complex cube root of unity, the southwest step as a move in the complex plane along \(\omega^{2}\) and the step to the right as a move along \(\omega^{3}=1\) From the hypothesis we then have \(a+b \omega+c \omega^{2}=1 .\) Using \(1+\omega+\omega^{2}=0\) we see that \(a-1=b=c .\) This then rules out \(a+b+c=6,\) so the number of 6 step paths is zero.

(ii) A 7 step path is possible only with \(a=3, b=2, c=2\). The number of such paths is the multinomial coefficient \(\left(\begin{array}{c}7 \\ 3,2,2\end{array}\right)=210\).

If K comes second, then L was third (one correct answer for R). But then R would also need to be second (one correct answer for M, a contradiction. So K cannot be second. So M must have won, etc. The order is M R L K.

(a) The following \(2 n-1\) numbers in \(A+A\) are distinct: \(a_{1}+a_{1}< a_{1}+a_{2}<\cdots< a_{1}+a_{n}< a_{2}+a_{n}< \ldots< a_{n}+a_{n}\).

A way to visualize is to write \(a_{i}+a_{j}\) at point \((i, j)\) in the XY-plane. Any step to the right or up increases the number. To reach from \(2 a_{1}\) to \(2 a_{n}\) needs \(2 n-1\) such steps. The given example is the path along bottom row and then rightmost column.

(b) Suppose the \(a_{i}\) form an arithmetic progression. Then for a fixed \(k\), the value of \(a_{i}+a_{k-i}\) is constant for all possible \(i,\) where \(2 \leq k \leq 2 n\). For the converse, we use induction.
There is nothing to prove for \(n=1,2\).
For \(n>2,\) remove \(a_{n}\) from \(A\) to get a set \(B .\) Now \(|A+A|-|B+B| \geq 2,\) because the two distinct numbers \(a_{n-1}+a_{n}\) and \(2 a_{n}\) in \(A+A\) are greater than all numbers in \(B+B\).

So for \(|A+A|=2 n-1\) to happen, one must have \(|B+B|=2 n-3,\) which by induction forces \(a_{1}, \ldots, a_{n-1}\) to be in an arithmetic progression. Moreover \(a_{n-2}+a_{n}\) must be in \(B+B\) and it can only be the largest number \(2 a_{n-1}\) (because all others are smaller than \(a_{n-2}+a_{n}\) ). This shows that \(a_{n}\) is the next term of the same arithmetic progression.

(c) \(0,1,2,3,4,5,6,7,8,10.\)
Can you prove that the answer is unique?

From the five distinct boxes, there are 10 ways to pick the two boxes that will have 2 oranges each. We need to distribute the remaining 6 oranges in the remaining three boxes such that none of the three boxes gets exactly 2 oranges. The possible distributions are \(6+0+0\) (which can be done in 3 ways) or \(5+1+0\) (6 ways) or \(4+1+1\) (3 ways) or \(3+3+0(3\) ways \() .\) Thus the required answer is \(10 \times(3+6+3+3)=150\)

\(9,\) there are exactly two sequences, for example, \(BBBBBBABB\).

\(\left(\begin{array}{l}n \\ k\end{array}\right)(n-k) !-\left(\begin{array}{c}n \\ k+1\end{array}\right)(n-k-1) !\)

(a) If a set \(A\) is in such a collection \(\mathcal{C},\) then the complement of \(A\) cannot be in \(\mathcal{C}\).
Therefore \(|\mathcal{C}| \leq \frac{1}{2}(\) total number of subsets of \(\{1,2, \ldots, n\})=\frac{1}{2} 2^{n}=2^{n-1}\)

(b) Solution 1. Take all \(2^{n-1}\) subsets of \(\{1,2, \ldots, n\}\) containing \(1\), remove the singleton set \(\{1\}\) and instead include its complement.

(b) Solution 2. For \(n=3,\) the four sets \(\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\) give a unique solution. For \(n>3\) take the union of each of these 4 sets with all \(2^{n-3}\) subsets of \(\{4, \ldots, n\}\).

1. If \(t_j\leq 0\), a card from A is removed. The maximum value of a card in A is \(m\) so \(t_j\) can at most be \(m\). Similarly, a card from B is subtracted when the value of \(t_j \geq 1\). Hence, the smallest value it can take is \(1-n\).
2. From (1) we see that the \(t\)-sequence can take at most \(n\) distinct non-positive values and at most \(m\) distinct positive values. We consider two ways in which the game can end:
   
   Case 1: Cards in stack B are empty.
   Suppose the game ended after using up \(m\) cards from B and \(p\leq n\) cards from A. Since the game has ended the value of \(t_{m+p}\) must be positive. In addition, the value of \(t\) before every card in B was added must have been positive (by the game's rule). So the sequence \(t_1,t_2,t_3,\ldots,t_{m+p}\) contains \(m+1\) positive numbers. But since the sequence contains \(m\) distinct positive numbers, two \(t\)s must have the same value by pigeon-hole principle.
   
   Case 2: Cards in stack A are empty.
   We use a similar argument. Suppose the game ended after using up \(n\) cards from A and \(p\leq n\) cards from B. Since the game has ended the value of \(t_{n+p}\) must be non-positive. In addition, the value of \(t\) before every card in A was added must have been non-positive. So the sequence \(t_0,t_1,t_2,t_3,\ldots,t_{m+p}\) contains \(n+1\) non-positive numbers. But since the sequence contains \(n\) distinct non-positive numbers, two \(t\)s must have the same value by pigeon-hole principle.
3. From (2), some \(t_i=t_j\). The sequence of cards added between \(t_i\) and \(t_j\) sums to zero. So some proper subset of \(A\) and \(B\) have equal sums.

(a) Suppose an integer \(n\) is colored white. Then \((n+n)=2 n\) is black, so \(-2 n\) is white, so \(-2 n+n=-n\) is black. Thus, the negative of a white number must be colored black.

(b) Now suppose the integers \(n\) and \(m\) are both colored black. Then \(-n\) and \(-m\) are both white, so \(-n-m\) is back, so \(n+m\) is white. Thus, the sum of two black numbers must be colored white.

(c) One possible coloring has all the integers colored red, since there are no conditions on red numbers. If that is not the case, let \(n\) be the smallest positive integer that is not colored red. Suppose the number \(n\) is colored black. Then we claim the remaining colors are all fully determined. Namely, the numbers of the form \((3 k+1) n\) will be black, the numbers of the form \((3k+2) n\) will be white, and the numbers of the form \((3k)n\) will be red, for all integers \(k\). And all remaining colors will be red. On the other hand, if the number \(n\) is colored white to begin with, then the remaining numbers will be determined by the same rules, but with black and white switched.

Thus we have listed all possible colorings. In order to prove the above claim, we first prove one more rule the colors must obey. Namely, that

Lemma. The sum of a black number and a white number must be colored red.

Proof. Suppose \(n\) is black and \(m\) is white, and that \(n+m\) is black. But then \((n+m)+(-m)\) is the sum of two black numbers, and must be colored white, which is a contradiction. Similarly, the sum of \(n\) and \(m\) cannot be white. Therefore it must be red.\(\:\square \)

Using this rule, we deduce that the numbers of the form \((3k+1)n\) will be black, the numbers of the form \((3k+2) n\) will be white, and the numbers of the form \((3k)n\) will be red, for all integers \(k\).

Lemma. All the numbers that are not multiples of \(n\) are colored red.

We can prove this by contradiction. As before \(n\) is the smallest positive integer that is not red, and it is colored black. Suppose \(m\) is the smallest positive integer that is neither red nor a multiple of \(n\).

Then \(m=qn+r\), where \(0 < r< n\) is the remainder when \(m\) is divided by \(n\).

We know this remainder is nonzero, since \(m\) is not a multiple of \(n .\) We also know that \(q > 0,\) since \(m > n\). Suppose \(m\) is white. Then, because \(-n\) is white, we know \(m-n=(q-1) n+r\) is black, which gives us a smaller non-red positive integer that is not a multiple of \(n\). On the other hand, suppose \(m\) is colored black. Then \(-2 n\) is black, so \(m-2 n=(q-2) n+r\) is white. If \(q<1,\) this gives us a smaller positive non-red integer that \(^{\prime}\) s not a multiple of \(n_{1}\) which is a contradiction, provided \(q>1 .\) But if \(q=1,\) and \(m-2 n=-n+r\) is white, that means that \(n-r\) is black, a contradiction. \(\:\square\)

(a) Break up the terms in the definition of \(f_{k}(n)\) into two groups: the terms in which \(i_{k}=n\) add up to \(n f_{k-1}(n-1)\) and the remaining terms, i.e., the ones in which \(i_{k} \leq n-1,\) add up to \(f_{k}(n-1) .\) So we get \(f_{k}(n)=n f_{k-1}(n-1)+f_{k}(n-1)\)

(b) We prove the statement by induction on \(k .\) First \(f_{1}(n)=\sum_{i=1}^{n} i=\frac{n(n+1)}{2},\) a polynomial of degree 2 as desired. For \(k>1,\) we have by part a the equation \(f_{k}(n)-f_{k}(n-1)=\) \(n f_{k-1}(n-1) .\) The right hand side is a polynomial of degree \(1+2(k-1)=2 k-1,\) where \(2(k-1)\) is the degree of \(f_{k-1}(n-1)\) by induction and the added 1 comes from the factor n. since successive differences in the values of \(f_{k}\) are given by a polynomial of degree \(2 k-1,\) the function \(f_{k}\) on positive integers is given by a polynomial of degree 1 more, i.e., of degree \(2 k\) Note: The previous statement is a standard fact, which can be explained as follows. If we assume that \(f_{k}(n)\) is a polynomial, then its degree is easily found, because for any polynomial \(f\) of degree \(m,\) its "successive difference" function \(f(x)-f(x-1)\) is a polynomial of degree \(m-1 .\) (Reason: If the leading term of \(f(x)\) is \(a x^{m},\) then the leading term in \(f(x)-f(x-1)\) is \(a m x^{m-1},\) as seen by expanding the power of \(x-1\) in \(a x^{m}-a(x-1)^{m}\) The remaining terms in \(f(x)-f(x-1)\) do not matter because by expanding powers of \(x-1\) in them and simplifying, we only get monomials of degree \(< m-1 .)\) (2) In fact, based on the difference equation, \(f_{k}(n)\) must be a polynomial in the variable \(n .\) This is a consequence of the following well-known fact.

c) By part a we have \(f_{2}(n)-f_{2}(n-1)=n f_{1}(n-1)=n \times \frac{n(n-1)}{2}=\frac{1}{2}\left(n^{3}-n^{2}\right)\). Similarly \(f_{2}(n-1)-f_{2}(n-2)=\frac{1}{2}\left((n-1)^{3}-(n-1)^{2}\right)\) and so on up to \(f_{2}(2)-f_{2}(1)=\frac{1}{2}\left(2^{3}-2^{2}\right)\) Note that \(f_{2}(1)=0,\) which we may also write as \(\frac{1}{2}\left(1^{3}-1^{2}\right) .\) Adding up, we get for any \(n \geq 1, f_{2}(n)=\sum_{j=1}^{j=n} \frac{1}{2}\left(j^{3}-j^{2}\right)=\frac{1}{2}\left(\frac{n^{2}(n+1)^{2}}{4}-\frac{n(n+1)(2 n+1)}{6}\right),\) where we have used standard formulas for the sum of first \(n\) cubes and of first \(n\) squares.

Claim. Given a polynomial \(h(x)\) of degree \(d\), there is a polynomial \(g(x)\) of degree \(d+1\) such that \(g(x)-g(x-1)=h(x)\).

Proof: Induction on \(d,\) the degree of \(h .\) If \(h(x)=c\) a constant, then \(g(x)=c x\) works. Now for \(d>1,\) it is enough to find a polynomial \(g(x)\) such that \(g(x)-g(x-1)=x^{d}\) (because if \(h(x)=c x^{d}+\tilde{h}(x),\) where \(\tilde{h}\) has degree \(< d\), by induction we find \(\tilde{g}\) for \(h\) and then \(c g(x)+\tilde{g}(x)\) works for \(h(x)) .\) To find such \(g(x)\), notice that for \(g_{1}(x)=x^{d+1},\) we have \(h_{1}(x)=g_{1}(x)-g_{1}(x-1)=(d+1) x^{d}+h_{2}(x),\) where \(h_{2}(x)\) is a polynomial of degree \(d-1 .\) By induction \(h_{2}(x)=g_{2}(x)-g_{2}(x-1)\) for a polynomial \(g_{2}(x)\) of degree \(d .\) Now \(g(x)=\frac{1}{d+1}\left(g_{1}(x)-g_{2}(x)\right)\) works. \(\:\square\).

Let \(P(n)\) denote LHS.

Base case \(n=2\).

\(\frac{2}{0 !+1 !+2 !}=1-\frac{1}{2 !} \quad\) hence \(P(2)\) is true.

Inductive step: Assume \(P(n)\) to be true.

\begin{align} P(n+1) &=P(n)+\frac{n+1 !}{n-1 !+n !+n+1 !} \\ &=1+\left(\frac{n+1}{n-1 !+n !+n+1 !}-\frac{1}{n !}\right) \\ &=1+\frac{1}{(n+1) !}\left[\frac{(n+1)}{\left[\frac{1}{n(n+1)}+\frac{1}{n+1}+1\right]}-(n+1)\right]\\ &= 1+\frac{1}{(n+1) !}\left[\frac{(n+1) \cdot n \cdot(n+1)}{1+n+n(n+1)}-(n+1)\right] \\ &= 1+\frac{1}{(n+1) !}[n-(n+1)] \\ &=1-\frac{1}{(n+1)!} \end{align}

Hence \(P(n+1) \quad\) holds.

Note that \[ \begin{aligned} \frac{k+2}{k !+(k+1) !+(k+2) !} &=\frac{k+2}{k ![1+k+1+(k+1)(k+2)]} \\ &=\frac{1}{k !(k+2)} \\ &=\frac{k+1}{(k+2) !} \\ &=\frac{(k+2)-1}{(k+2) !} \\ &=\frac{1}{(k+1) !}-\frac{1}{(k+2) !} \end{aligned} \]

Telescoping the sum gives the desired value.

Verify that 1 and 2 are not stable. Number 3 is stable since:

\[ \frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1 \]

\[ \frac{1}{2} + \frac{1}{2}\left( \frac{1}{2} + \frac{1}{3} + \frac{1}{6} \right) = 1 \]

This gives the general idea. If \(k \geq 3\) is stable, then there are \(a_{1}, \ldots, a_{k}\) all distinct and \(\sum \frac{1}{a_{i}}=1 .\) This implies that \(\frac{1}{2}+\sum \frac{1}{2 a_{i}}=1 .\) Hence all numbers except 1 and 2 are stable.

(a) Suppose \(f(0)=0\) then \(f(1)=1\) and \(f(2)=f(f(1))=f(1)=1\). It implies that \(f(3)=1+1=2\) and \(f(4)=f(1)=1\). The pattern continues and we get that if \(2 k+1 \geq 3\) then \(f(2 k+1)=2 .\) On the other hand if \(2 k \geq 4\) then \(f(2 k)=1\)

(b) Suppose \(f(0)=1 .\) We have \(f(0)=f(2 \cdot 0)=f(f(0))=f(1)\). But we also have \(f(1)=f(0)+1,\) a contradiction.

(c) Suppose \(f(0)=2^{k} .\) Then, \(2^{k}=f(2 \cdot 0)=f(f(0))=f\left(2^{k}\right),\) and \(f\left(2^{k}+1\right)=f\left(2^{k}\right)+\) \(1=2^{k}+1 .\) Notice that \(f(1)=f(0)+1=2^{k}+1,\) and \(f(2)=f(f(1))=2^{k}+1\)

In this way, we see that for any \(n, f\left(2^{n}\right)=2^{k}+1 .\) This contradicts the fact that \(f\left(2^{k}\right)=2^{k}\)

Let \(f(n)=0 .\) If \(n>0,\) then \(n-1\) is in the domain of \(f\) and \(f(f(f(n-1)))< f(n)=0\) which is a contradiction, since 0 is the smallest possible value of \(f .\)

We use induction on \(n\).

If \(n=1,\) then this is just part a. Assuming the statement up to \(n\) we need to prove that if \(f(x)< n+1,\) then \(x< n+1 \). If \(f(x)< n,\) then by induction \(x< n,\) so \(x< n+1 \). So let \(f(x)=n \). If \(x=0,\) we are done. Otherwise \(f(f(f(x-1)))< f(x)=n\) and by using induction thrice we get in succession \(f(f(x-1))< n,\) then \(f(x-1)< n\) and then \(x-1< n,\) i.e., \(x< n+1\) as desired.

Apply part b to \(f(f(f(m)))< f(m+1)\) (with \(x=f(f(m))\) and \(n=f(m+1))\) to get

\(f(f(m))< f(m+1) .\) Apply part \(b\) to this with \(x=f(m)\) and \(n=f(m+1)\) to get \(f(m)< f(m+1) .\) Again apply part b to get \(m< f(m+1)\)

By part c, \(f\) is increasing and \(f(n) \geq n .\) If \(f(n)>n,\) then \(f(f(n))>f(n)\) (since \(f\) is increasing) and so \(f(f(n))>n,\) i.e., \(f(f(n)) \geq n+1 .\) Again, since \(f\) is increasing, \(f(f(f(n))) \geq f(n+1),\) a contradiction.

(a) We will count the sacred words starting with \(b_{1}\). since \(b_{1}\) is chosen \(b_{n}\) and \(b_{2}\) are out of the picture. In order to fill the remaining \(k-1\) positions we have to choose non-consecutive \(b_{i}\)s. Note that, specifying these \(b_{i}\)s is same as specifying the gaps between them. For example, let \(n=7, k=3\) and we would like to choose \(b_{1}, b_{3}, b_{6}\).

Then the triple (1,2,1) specifies that leave one alphabet after \(b_{1},\) drop two aft er \(b_{3}\) and drop one aft er \(b_{6}\).

Hence, in general let \(x_{1}, x_{2}, \ldots, x_{k}\) be these gaps.

It is clear that each of this gap is at least 1 and they add up to \(n-k\).

So our counting problem can be reformulated as: "In how many different ways can we choose \(k\) natural numbers, each of which is at least \(1,\) that add up to \(n-k\)?"

The answer is \(\left(\begin{array}{c}n-k-1 \\ k-1\end{array}\right)\).

However, we have not assigned positions to these letters yet. This can be done in \((k-1) !\) ways. Hence the number of ways is

\[ (k-1) !\left(\begin{array}{c} n-k-1 \\ k-1 \end{array}\right) \]

In order to count the total number of sacred words we just need to multiply the above number by \(n .\) The final answer is

\[n(k-1) !\left(\begin{array}{c}n-k-1 \\ k-1\end{array}\right)\]

(b) For \(n=10\) and \(k=4\) the above count is \(\displaystyle 10\times 3! \times \binom{5}{3} = 600 \).

You and your friend are playing a game where there are 2 stacks of cards:
Stack A has \(n\) cards and each card has a number from the set \( \{1,2,...,m\} \).
Stack B has \(m\) cards and each card has a number from the set \( \{1,2,...,n\} \).
You start with \(t_0=0\) and note down the following sequence \(t_1,t_2,t_3,\ldots\). The game proceeds in steps as follows:
If \(t_j \leq 0\), pick out the topmost card from stack A and set \[t_{j+1}=t_j + \text{number on the topmost card drawn from Stack A}\] If \(t_j> 0\), pick out the topmost card from stack B and set \[t_{j+1}=t_j - \text{number on the topmost card drawn from stack B}\] The game ends when a player has to draw a card from an empty stack.
Prove that

1. \(1-n \leq t_j \leq m \) for all \(j\)
2. There exists distinct indices \(i\) and \(j\) such that \(t_i=t_j\)
3. Prove that there exists a non empty subset in stack A and another in B such that the sum of the numbers on those cards are equal.