symmetric 2 variable function

Suppose $S = \{1,2,\dots,n\}$ and $f: S \times S \to R$ satisfies the following: $$f(i,j) + f(j,i) = 0 \forall i,j \in S$$ Now for any two number $i,j$, we say that $i$ is superior to $j$ if there exists a $k$ (not necessarily distinct from $i,j$) such that $f(i,k) + f(k,j) \geq 0$. Show that there exists a number $x \in S$ such that $x$ is superior to all elements of $S$.

Combinatorial Proof

Give a combinatorial proof of this identity: $$n(n+1)2^{n-2} = \sum_{k=1}^n k^2 {n \choose k}$$ Solution

Let's say in a class there are $n$ students and you are asked to select one or more students, with the caveat that Joe must be selected. For each student that is selected, the whole class gets 1 dollar. So what is the expected value of the class' income?

Or if you want a non-probabilistic way to think about it, then over all the possible ways to select students, what is the sum of class income in all of those scenarios?

First way to count: Say there are $k \geq 1$ students who are selected (including Joe). There are $n-1 \choose k-1$ ways to choose the students (because Joe must be selected). So this particular way of selecting the students has $k {n-1 \choose k-1} = \frac{k^2}{n} {n \choose k}$ income. So the sum of all income over all scenarios is $\sum_{k=1}^n \frac{k^2}{n} {n \choose k}$

Second way to count: Consider a student, not Joe. How many dollars does he contribute to the total class income? He contributes 1 dollar everytime he is selected, which is $2^{n-2}$ times (because both he and Joe must be selected for him to contribute, so the other $n-2$ students can be chosen freely, selected or not selected). There are $(n-1)2^{n-2}$ contributions from these, because there are $n-1$ students that are not Joe.

But how many dollars did Joe contribute? He ALWAYS contributes 1 dollar for every selection, and there are $2^{n-1}$ selections total. So there are $2^{n-1}$ contributions from Joe.

So the total contribution is $(n-1)2^{n-2} + 2^{n-1} = (n+1)2^{n-2}$

Coloring polygon vertices

The vertices of a regular $n$-gon ($n \geq 3$) are to be colored with one of the $k$ colors such that no two adjacent vertices may have the same color. Let $f(n)$ be the number of legal coloring. Find a closed formula for $f(n)$.

Solution:

Suppose we sever one of the edges temporarily, so that we're left with a "string" of length $n$ where the first and last vertices are not connected. In order to color this string, we may color the first vertex $k$ ways, but each of the subsequent vertices may only be colored $k-1$ ways, avoiding the color of the previous vertex. Suppose $g(n)$ is the number of ways to color a string of length $n$, then $g(n) = k(k-1)^{n-1}$

Now, take one of these colored strings of length $n$ and join the first and last vertices. The resulting polygon may or may not be a valid coloring. It is not a valid coloring if and only if the first and last vertices have the same color. The number of such invalid coloring is the same as $f(n-1)$. There is a bijection between the invalid coloring where the first and last vertices have the same color and a valid coloring of an $(n-1)$-gon.

So: $$f(n) = g(n) - f(n-1)$$ Now, $f(3) = k(k-1)(k-2)$. So: $$f(4) = k(k-1)^3 - f(3) = k(k-1)(k^2 -3k+3) =(k-1)((k-1)^3+1)$$ $$f(5) = k(k-1)^4 - f(4) = k(k-1)(k^3-4k^2+6k-4) = (k-1)((k-1)^4-1)$$ $$f(6) = k(k-1)^5 - f(5) = (k-1)((k-1)^5+1)$$ So we can see a pattern, which we can prove via induction easily.

$$f(n) = (k-1)((k-1)^{n-1}+(-1)^n)$$

ODE discrete version

If $f$ is a function that is defined over natural numbers ($f:N \to R$), let $f^*$ denote the function $f^*(n) = f(n) - f(n-1)$. Find all functions such that $$n(f^*)^*(n) + (n-1)f^*(n) = f(n)$$ for all $n > 2$

Solution We can check that $f(n) = A(n-1) + B/2^n$ for any constant $A,B$ satisfies the given equation. Now we show that there's nothing else.

Define $g = f^*+f$. The equation is identical to: $$n(f^*+f)^*(n) =(f^*+f)(n)$$ $$ n(g(n) - g(n-1)) = ng^*(n) = g(n)$$ $$\frac{g(n)}{n} = \frac{g(n-1)}{n-1}$$ for all $n>2$, therefore $g(n)/n$ must be a constant. Remember that $g(1)$ is not defined because $f$ is only defined for $n \geq 1$ thus $g$ is only defined for $n \geq 2$. Furthermore, the value $g(2)$ depends on $f(1)$ and $f(2)$.

Case 1: $g(2) = 0$ In this case then $g(n) = 0 \forall n$. $$(f^*+f)(n) = 0$$ $$f(n) = f(n-1)/2$$ so we easily get $f(n) = k/2^n$ for some constant $k$.

Case 1: $g(2) \neq 0$ Note that if $f$ is a solution to the problem then $kf$ is also a solution to the problem, for all $k$ real numbers. If we replace $f$ by $kf$, then $g$ is also replaced by $kg$. So WLOG, we may assume that $g(2) = 2$

Because $g(n) / n$ is a constant then $$g(n) / n = g(2) / 2 = 1$$ so $g(n) = n \forall n >2$ $$f(n) = \frac{f(n-1) + n}{2}$$ for all $n > 2$.

Because $g(2) = 2 = 2f(2) - f(1)$ then $f(2) = 1+ f(1)/2$ Now notice this pattern: $$f(3) = \frac{f(2) + 3}{2} = 2 + f(1)/4$$ $$f(4) = \frac{f(3) + 4}{2} = 3 + f(1)/8$$ Easy to prove by induction that $f(n) = n-1 + f(1)2^{1-n}$.

From the two cases above, it's clear that any solution of the equation must be in the form of $f(n) = A(n-1) + B/2^n$ for any constant $A,B$

Polynomial and divisibility

Find an integer polynomial $P(x)$ with the lowest degree that satisfies the following:

$P(x)$ is divisible by $x^2+x+1$

$P(x)+3$ is divisible by $x^{2017} -1$

Solution

Let $Q(x) = x^2+x+1$ and $R(x) = x^{2016} + \dots + 1$. It's easy to show that $Q$ and $R$ are relatively prime.

The LCM for both divisors is thus $(x-1)Q(x)R(x)$ which has degree 2019.

Now if $P$ and $P'$ both satisfy the problem statement, then $P-P'$ must be divisible by $(x-1)Q(x)R(x)$.

On the other hand, if $P$ satisfies the problem statement, then $P + A(x).(x-1)Q(x)R(x)$ also satisfies the problem statement for any integer polynomial $A(x)$.

Therefore, we can find at most one $P(x)$ with degree less than 2019, because if there were two such polynomials, their difference must be divisible by $(x-1)Q(x)R(x)$ but that difference has degree less than 2019, so the difference must be zero. That one polynomial is our answer.

To find it: let $t$ be the root of $Q(x)$. We want to find $P(x)$ such that:

$$P(x)+3 = S(x).(x-1).R(x)$$ for some $S(x)$, with $S(x) = ax+b$. We know that it's possible for $S$ to be a linear function because we've established that there exists a $P$ with degree less than 2019, and $R$ has degree 2016.

$$P(t) + 3 = (at+b).(t-1).R(t)$$

$P(t) = 0$ because $P(x)$ is divisible by $Q(x)$ and $Q(t) = 0$.

$R(t) = t^{2016} + \dots + t + 1 = 1$ because every 3 consecutive terms in $t^{2016} + \dots + t$ sum to zero (because $Q(t) = 0$).

So: $$ 3 = (at+b)(t-1)$$ $$at^2 + (b-a)t - b-3 = 0$$ $$a(-t-1) + (b-a)t - b-3 = 0$$ $$ (b-2a)t=a+b+3$$

Solving for the system:$b-2a = 0, a+b+3 = 0$ gives us: $a = -1, b= -2$ so $S(x) = -(x+2)$

Plugging in to the equations, we find:

$$P(x) = -(x+2)(x^{2017}-1) - 3 = -x^{2018} - 2x^{2017} + x -1 = -x^2(x^{2016}-1) -2x(x^{2016}-1) -( x^2+x+1) $$

Each term in the right-most expression is divisible by $Q(x)$ because $(x^{2016}-1)$ is divisible by $x^3-1$ so $P(x)$ is also divisible by $Q(x)$

Spanning set

Let $S = \{0,1,2,\dots,10\}$.

A set of numbers $A \subset S$ is called "spanning" if the set $\{ x, x+1, x+2, x+3 \mod 11 | x \in A \} = S$.

And a set of numbers $B \subset S$ is called "potentially spanning" if there is an integer $k$ such that the set $\{kb \mod 11 | b \in B \}$ is spanning.

Prove that every subset of $S$ with four elements are potentially spanning, and prove that there exists a subset of $S$ with three elements that is not potentially spanning.

Solution First, we show that there is a subset of three elements that is not potentially spanning.

Note that for a set to be spanning, it has to be $\{c,c+4, c+8\}$ for some $c$ (here we assume everything is modulo 11, so we don't write it for notational simplicity). This is because the maximum distance between two adjacent element is 4, so the distances between 3 elements must be 4+4+3 (or its rotation).

Now we claim that a set $\{x,y,z\}$ is potentially spanning if and only if there exists $r \neq 0$ and $s$ such that $\{x,y,z\} = \{r+s, 2r+s, 3r+s \mod 11\}$. First, clearly if a set is spanning, then all of its "rotations" are also spanning sets. Likewise, if a set is potentially spanning, then all of its rotations are also potentially spanning. So wlog we may assume that $s=0$. Then the set $\{r,2r,3r\}$ is potentially spanning because we can always take $k = 4r^{-1} \mod 11$ so that $\{kr,2kr,3kr\} = \{4,8,12=1\}$ a spanning set. The inverse modulo is guaranteed to exist because 11 is prime and $r \neq 0$.

Now the other direction. Suppose $\{x,y,z\}$ is potentially spanning, such that $\{kx,ky,kz\}$ is spanning. As we've established above, it must have form $\{c,c+4, c+8\}$ for some $c$. Thus we can take $r = 4k^{-1} \mod 11$ and $s = (c-4)k^{-1} \mod 11$ so that $\{k(r+s),2kr,3kr\} = \{4+ks,8+ks,12+ks\} = \{c,c+4,c+8\}$.

So we have shown that the potentially spanning sets are generated by (and only by) the number of $(r,s)$ pairs we can choose. There are 10 choices for $r$ and 11 for $s$, so there are at most 110 potentially spanning sets. We say at most because some choices of $r$ and $s$ may "collide" (result in the same spanning triplet). However, there are ${11 \choose 3} = 165$ possible triplets, so there are some triplets that are not generated by the $(r,s)$ construction above and thus not potentially spanning.

Now we show that a subset $B = \{b_1,b_2,b_3,b_4\}$ is always potentially spanning. Note that if any three of $b_i$s form a potentially spanning triplet then $B$ is potentially spanning. In particular, if $B$ contains an arithmetic sequence modulo 11 then $B$ is potentially spanning. So we assume that $B$ is free from arithmetic progression.

Now let $d_i = b_{i+1} - b_i$ (of course we mean $b_5 = b_1$. Then among all four $d_i$s, let $d$ be the maximal distance. If the maximal distance is 4, then we are done because $B$ itself is spanning. So we assume that the maximal distance is at least 5. Wlog, we may assume that this maximal distance is $d_4$ and that $b_1 = 0$. So this means $0=b_1 < b_2 < b_3 < b_4 = 11-d$ and $b_i$ must not contain arithmetic sequence. It's easy to see that the only possible combinations are:

Case 1: $d=5$, so $0=b_1 < b_2 < b_3 < b_4 = 6$. The only combinations are $\{0,1,4,6\}, \{0,1,5,6\},\{0,2,5,6\}$. All the other combinations contain an arithmetic sequence. But in the first two cases, we can take $k=8$ to get: $\{0,4,8,10\}, \{0,4,7,8\}$ which contains arithmetic sequence thus potentially spanning, and for the third case we can take $k=3$ to get $\{0,4,6,7\}$ which is spanning.

Case 2: $d=6$, so $0=b_1 < b_2 < b_3 < b_4 = 5$. The only combinations are $\{0,1,4,5\}$ and $\{0,2,3,5\}$. We can take $k=4$ to get $\{0,4,5,9\}$ and $k=2$ to get $\{0,4,6,10\}, both spanning sets.

Case 3: $d=7$, so $0=b_1 < b_2 < b_3 < b_4 = 5$. The only combination is $\{0,1,3,4\}$. We can take $k=5$ to get $\{0,4,5,9\}$, a spanning set.

And there is no way to have $d > 7$ and still fitting $b_2$ and $b_3$ without getting an arithmetic progression. So our proof is complete.

Various double counting problems

These problems can all be solved by the double counting principle, that is, to count the same object two different ways and assert that those must match.

Suppose $n > 4$. Let $A_1, A_2, \dots ,A_k$ each be a set of $n$ integers, where $k \leq 4^{n-1} / 3^n$. Show that we can color each integer with one of the four colors so that each set contains integers of 4 different colors.

In a party attended by $n$ people, there were a number of handshakes. A group of 10 persons is called "tight" if each person shook hands with the other 9. It is known that we cannot add another handshake (two people who didn't shake hands now shaking hands) without increasing the number of tight groups. Prove that the number of handshakes is at least $8n-36$

In a class with many students, we choose 2016 committees among them. Each committee has 11 students, and each student may belong to multiple committees. Prove that there is a way to choose some of the students so that each committee has at least one chosen and one unchosen student.