Let $n \ge 2$ be an integer and $M= \{1,2,\ldots,n\}.$ For each $k \in \{1,2,\ldots,n-1\}$ we define $$x_k= \frac{1}{n+1} \sum_{\substack{A \subset M \\ |A|=k}} (\min A + \max A).$$Prove that the numbers $x_k$ are integers and not all of them are divisible by $4.$
HIDE: Notations $|A|$ is the cardinal of $A$ $\min A$ is the smallest element in $A$ $\max A$ is the largest element in $A$Problem
Source: Romanian National Olympiad 1998 - Grade 10 - Problem 1
Tags: algebra, Integers, combinatorics
17.01.2025 00:12
$x_k=\binom{n}{k}$ Take randomly a set $A$ with $|A|=k$. The expected value of $\max A$ can be found using the expecting value of $\min A$. $\mathbb{E}[\max A]=n+1-\mathbb{E}[\min A]$ Because given any set $A$ consider the set $A'$ obtained by chainging $1$ with $n$, $2$ with $n-1$... If $n$ is even $n/2$ with $n/2+1$ else $(n+1)/2$ remain alone. Then $\max A'=n+1-\min A$ And the function that send $A$ to $A'$ is a bigection. So $\mathbb{E}[\max A +\min A]=n+1$. And so we have from definition of expected value that $$\sum_{\substack{A \subset M \\ |A|=k}} (\min A + \max A)=(n+1)\binom{n}{k}$$Because $\binom{n}{k}$ is the total number of possible sets $A$. So $x_k=\binom{n}{k}$. This is obviusly and integer. Now let $d=v_2(n)$; then for $k=2^d$ we have that $\binom{n}{k}$ is not multiple of $4$ (in particular it's odd). So if $n$ isn't a power of $2$ exist $k$ such that $4\not|x_k$. If $n$ is a power of $2$ take $k=n/2$ and $\binom{n}{k}$ will be $2$ modulo $4$ and $4\not|x_k$.
17.01.2025 05:07
$\sum_{\substack{A \subset M \\ |A|=k}} \min A =1*\binom{n-1}{k-1}+2* \binom{n-2}{k-1}+...+(n+1-k) *\binom {k-1}{k-1}$ $\sum_{\substack{A \subset M \\ |A|=k}} \max A =n*\binom{n-1}{k-1}+(n-1)* \binom{n-2}{k-1}+...+k *\binom {k-1}{k-1}$ So $x_k=\binom{n-1}{k-1}+\binom{n-2}{k-1}+...+\binom{k-1}{k-1}= \binom{n}{k}$ $x_1+x_2+...+x_{n-1}= \binom{n}{1}+...+\binom{n}{n-1}=2^n-2 \equiv 2 \pmod{4}$ so not all of $x_k$ are divisible by $4$
17.01.2025 13:39
Filipjack wrote: Let $n \ge 2$ be an integer and $M= \{1,2,\ldots,n\}.$ For each $k \in \{1,2,\ldots,n-1\}$ we define $$x_k= \frac{1}{n+1} \sum_{\substack{A \subset M \\ |A|=k}} (\min A + \max A).$$Prove that the numbers $x_k$ are integers and not all of them are divisible by $4.$
The map $f(A)=\{n+1-x \mid x \in A \}$ is a bijection from the set of $k$-subsets of $\{1, ..., n\}$ to itself. We also have $\max(f(A))=n+1-\min(A)$ So $\sum_{\substack{A \subset M \\ |A|=k}}\max(A)=\sum_{\substack{A \subset M \\ |A|=k}}\max(f(A))=(n+1)\binom{n}{k}-\sum_{\substack{A \subset M \\ |A|=k}}\min(A)$. Therefore $x_k=\binom{n}{k}$. Since $\sum_{k=1}^{n-1}x_k=2^n-2$, they can not all be divisible by 4