stroller wrote:

Although your idea seems very fruitful as it gives a bound that shows the beautiful $\frac{{k\choose \lfloor \frac{k}{2} \rfloor}}{2^k} \cdot (n+1)$, I believe that your construction needs some adjustments. For example, you always put $n$ in $A$, but for $n=2^{k-1}-1$ this fails, as all the integers less than $n$ will be "contained" in it. Can anyone provide a full solution/complete this idea?

@above thanks for pointing out. My approach only guarantees that within each $S_i$ no two numbers "contain" each other but strangely the numbers seem to work out

Is the official solution available.

Start by writing $n+1$ in binary, so $n+1=2^{a_1}+\dotsb+2^{a_m}$ for $a_1 > \dotsb > a_m$. We'll use the example $n=154$, where $n+1$ in binary is $10011011$. For each $1$ in the binary representation, create a prefix by replacing that $1$ with a $0$ and keeping everything before that the same. Construct values $q_i$ according to the rule \[q_i=\min(q_{i-1}-1, \lceil a_i/2\rceil)\]and the initial value is $q_1=\lceil a_1/2\rceil$. For our example, we have the following values: \[\begin{array}{l|c|r} \text{prefix} & a_i & q_i \\ \hline 0\dots & 7 & 4 \\ 1000\dots & 4 & 2 \\ 10010\dots & 3 & 1 \\ 1001100\dots & 1 & 0 \\ 10011010 & 0 & -1 \end{array}\]For each $i$, let $S_i$ consist of all numbers whose binary representation consists of the $i$th prefix in the table followed by a string of $a_i$ digits, of which exactly $q_i$ are $1$. If $q_i$ is negative, then $S_i$ is empty. We claim $A_n=\bigcup S_i$ is a valid subset. By Lucas' theorem, this is equivalent to no binary representation of one number covering the binary representation of another. By the prefixes, if $y\in S_j$ and $x\in S_i$ are elements of $A$ in binary form, then $y$ can cover $x$ only if $j\geq i$. By construction, the number of $1$s of elements of $S_j$ is at most the number of $1$s of elements of $S_i$, so no covering occurs, as desired. Let $f(n)$ denote the size of the set $A_n$ obtained by this construction. It remains to show the lower bound \[f(n)=\sum_{i=1}^{m}\binom{a_i}{q_i}\geq \frac{\binom{k}{\lfloor k/2\rfloor}}{2^k}(n+1).\] We first resolve the case where $q_i=q_{i-1}-1$ always. The case $n+1=2^{a_1}$ is special, and equality holds for $k=a_1$. From now on, let $k=a_1+1$. We wish to show that \[\frac{f(n)}{n+1}=\frac{\sum_{i=1}^{m}\binom{a_i}{q_i}}{\sum_{i=1}^{m}2^{a_i}}\geq \frac{\binom{k}{\lfloor k/2\rfloor}}{2^k}.\][The goal is to reduce to the case $a_i=a_{i-1}-1$, but I made a mistake here. I need to fix this.] Then \[f(n)=\sum_{i=1}^{m}\binom{a_1+1-i}{q_1+1-i}=\sum_{i=1}^{m}\binom{a_1+1-i}{\lfloor a_i/2\rfloor}=\binom{a_1+1}{\lfloor a_1/2\rfloor+1}-\binom{a_1+1-m}{\lfloor a_1/2\rfloor+1}.\]Meanwhile, \[n+1=\sum_{i=1}^{m}2^{a_1+1-i}.\]Now we consider the effect of increasing $m$ by $1$. Then $f(n)$ increases by $\binom{a_1-m}{\lfloor a_1/2\rfloor}$ while $n+1$ increases by $2^{a_1-m}$. Since \[\frac{\binom{a_1-m}{\lfloor a_1/2\rfloor}}{2^{a_1-m}}\leq \frac{\binom{a_1}{\lfloor a_1/2\rfloor}}{2^{a_1}}\leq \frac{\binom{k}{\lfloor k/2\rfloor}}{2^k},\]we can assume the worst case scenario of $m=a_1+1$. In this case we have \[\frac{f(n)}{n+1}=\frac{\binom{a_1+1}{\lfloor a_1/2\rfloor+1}}{2^{a_1+1}-1} > \frac{\binom{a_1+1}{\lfloor a_1/2\rfloor+1}}{2^{a_1+1}}=\frac{\binom{k}{\lceil k/2\rceil}}{2^k}.\] We now deal with the remaining cases by strong induction. Suppose for some $i > 1$, we have $q_i=\lceil a_i/2\rceil$. Let $\ell+1=2^{a_i}+2^{a_{i+1}}+\dotsb+2^{a_{m}}$. Then the construction from step $i$ onward is the same as the construction for $\ell$, just with everything shifted, i.e. \[A_n=A_{n-\ell-1}\sqcup \Big((n-\ell)+A_{\ell}\Big).\]Therefore $f(n)=f(n-\ell-1)+f(\ell)$. By the inductive hypothesis, if $n < 2^k$ then \[f(n-\ell-1)+f(\ell)\geq \frac{\binom{k}{\lfloor k/2\rfloor}}{2^k}(n-\ell+\ell+1)=\frac{\binom{k}{\lfloor k/2\rfloor}}{2^k}(n+1)\]as desired.

a1267ab wrote: We compute \[\frac{\binom{a_i}{q_i-1}}{2^{a_i}}\leq \frac{\binom{a_i}{\lceil a_i/2\rceil}}{2^{a_i}}\leq \frac{\binom{k}{\lceil k/2\rceil}}{2^{k}}.\] Isn't this false as $a_i < k$?

@above By definition of $a_i$, clearly, $a_i < k$ unless $n=2^k -1$ which is obvious.

bumjoooon wrote: @above By definition of $a_i$, clearly, $a_i < k$ unless $n=2^k -1$ which is obvious. No, post #8 makes a valid point as the second inequality is flipped. The gap in the solution seems difficult to fix, though I think the construction still works (by computational evidence).

a1267ab wrote: bumjoooon wrote: @above By definition of $a_i$, clearly, $a_i < k$ unless $n=2^k -1$ which is obvious. No, post #8 makes a valid point as the second inequality is flipped. The gap in the solution seems difficult to fix, though I think the construction still works (by computational evidence). Oh I understand the point. I misread by the post as asking the validity of $a_i <k$.

a1267ab wrote: bumjoooon wrote: @above By definition of $a_i$, clearly, $a_i < k$ unless $n=2^k -1$ which is obvious. No, post #8 makes a valid point as the second inequality is flipped. The gap in the solution seems difficult to fix, though I think the construction still works (by computational evidence). I agree; intuitively this is greedily picking sets that do not have sizes exceeding $n$ while making sure in each layer the number of $1$'s are the same so that no two numbers would contain each other... This seems like the only reasonable construction for a problem like this one to be on an olympiad, so it's probably just that the bounding needs a bit more work

I also strongly agree since it is even stronger than picking all possible natural numbers with its binary expression with $[k/2]$ ones. Let’s try more!

This is wrong.

joao1 wrote: If $n > 2^{k-1}$, then $T_n = 2^{k-1} + S_{2^{i_1} + ... + 2^{i_m}}$, so the elements of $T_n$ have at most $\left\lfloor \frac{i_{1}-3}{2} \right\rfloor+2 \le \left\lfloor \frac{k-5}{2} \right\rfloor+2 = \left\lfloor \frac{k-3}{2} \right\rfloor+1$ digits equal to $1$ in base 2. I think $k$ for $2^{i_1} + ... + 2^{i_m}$ is equal to $i_1 +1$ rather than $i_1$. This would change $\left\lfloor \frac{k-3}{2} \right\rfloor+1$ into $\left\lfloor \frac{k-2}{2} \right\rfloor+1= \left\lfloor \frac{k}{2} \right\rfloor$. If I’m wrong, plz let me know.

@bumjoooon Thanks, you are correct. I could not fix that mistake.

joao1 wrote: Let $g(x) = \frac{{x\choose \lfloor \frac{x}{2} \rfloor}}{2^x}$. If $n > 2^{k-1}$, then $T_n = 2^{k-1} + S_{2^{i_1} + ... + 2^{i_m}}$, so the elements of $T_n$ have at most $\left\lfloor \frac{i_{1}-3}{2} \right\rfloor+2 \le \left\lfloor \frac{k-5}{2} \right\rfloor+2 = \left\lfloor \frac{k-3}{2} \right\rfloor+1$ digits equal to $1$ in base 2. What I meant was for the induction part, since $2^{i_1}\leq 2^{i_1} + ... + 2^{i_m} < 2^{i_1 +1}$ we get $\left\lfloor \frac{i_{1}-2}{2}\right\rfloor+2$ instead of $\left\lfloor \frac{i_{1}-3}{2}\right\rfloor+2$.

WLOG, $2^k\le 2n$. This is valid because $\frac{\binom{k}{\lfloor \frac k2 \rfloor}}{2^k}$ is strictly decreasing. The set $A$ must satisfy, for all $x\ne y\in A, y$ is not a supermask of $x$, i.e. if $x=\sum\limits_{i=1}^a 2^{x_i}$, then bits $x_1,\cdots,x_a$ are on for $y$. Call this (1).

Now we will give a formal constructive algorithm. Consider the binary representation of $n=\overline{d_{k-1}\cdots d_0}_2$. It must start with 1 at bit $k-1$. Suppose it has $m$ chunks of $1$'s, $[l_1,r_1), [l_2,r_2), \cdots, [l_m,r_m)$. Here, $l_1=k $ (units digit is 1) and $l_i> r_i\ge l_{i+1}$ We let $S_i$ be the set of numbers such that \bullet There are 1's at $[l_1,r_1), \cdots, [l_i,r_i)$ \bullet There exist at least one zero in $[l_{i+1},r_{i+1})$ \bullet There are $\min \{ \lfloor \frac{l_i}{2} \rfloor, \lfloor \frac k2 - \sum\limits_{j=1}^i (r_i-l_i+1)\}$ 1's. If $\lfloor \frac k2 - \sum\limits_{j=1}^i (l_i-r_i)$ is negative, $S_i$ is empty. It's clear that $\cup_{i\ge 0} S_i$ satisfies (1). Now we evaluate $\sum\limits_{i\ge 0} |S_i|.$ Note $|S_i|=\binom{l_i}{\min \{ \lfloor \frac{l_i}{2} \rfloor, \lfloor \frac k2 \rfloor - \sum\limits_{j=1}^m (l_j-r_j)\}}-\binom{r_i}{\min \{ \lfloor \frac{l_i}{2} \rfloor, \lfloor \frac k2 \rfloor - \sum\limits_{j=1}^m (l_j-r_j)\}}$ (Here, $\binom{i}{j} = 0$ if $j<0$)

I think I've found a complete solution. We propose the following construction. Let $n+1=2^{a_1}+\dots+2^{a_m}$ for $a_1 > \dots > a_m.$ Define a sequence $b_i$ alongside $a_1, \dots , a_m$ such that $b_i$ is the greatest integer less than or equal to both $b_{i-1}-1, \lceil a_i/2\rceil$. Let $S_{(p,q)}$ be the set of all numbers not exceeding $2^p$ with $q$ $1$'s in their binary representation, defined as empty if $q$ is negative. For $1 \le j \le m,$ we let $T_j$ be the set $S_{a_{1},b_1 }$ if $j = 1,$ or the set gotten by adding the sum $\sum_{t=1}^{j-1} 2^{a_t}$ to any element in $S_{a_{j},b_{j}}$ if $j \ne 1.$ The union $U_n$ of all such sets $T_j$ gives a subset of $\{0,1, \dots n \}$ fitting the condition. This can be seen by Lucas' theorem - no binary representation of one number in $U_n$ can completely "cover" another which can be seen through some pigeonhole arguments. For any $n,$ let $f(n)$ be the cardinality of $U_n.$ It suffices to prove $f(n)$ fits the bound for $2^{k-1} \le n < 2^k.$ We do so inductively, the base case is trivial. If $n = 2^k-1,$ proving the inequality is trivial as well (always equality case), so we'll assume $n \le 2^k-2$ from here. Furthermore, all sets $T_j$ have been defined such that they are disjoint, and thus it suffices to sum $|T_j|$ over all $1 \le j \le m.$ If $k$ is even, then $a_1 = k-1$ and $\lceil a_1/2 \rceil -1 \ge \lceil a_{2}/2 \rceil.$ So $$f(n) = \binom{k-1}{\frac{k}{2} - 1} + f(n - 2^{k-1}) \ge \binom{k-1}{\frac{k}{2} - 1}+ \frac{\binom{k-1}{\frac{k}{2} - 1}(n-2^{k-1}+1)}{2^{k-1}} = \frac{\binom{k}{\frac{k}{2}}(n+1)}{2^k}.$$ If $k$ is odd, then either $a_2 \le k-3$ or $a_2 = k-2.$ In the former case, $\lceil a_1/2 \rceil -1 \ge \lceil a_{2}/2 \rceil$ so $$f(n) = \binom{k-1}{\frac{k-1}{2}} + f(n - 2^{k-1}) \ge\binom{k-1}{\frac{k-1}{2}}+ \frac{\binom{k-1}{\frac{k-1}{2}}(n-2^{k-1}+1)}{2^{k-1}} > \frac{\binom{k}{\frac{k-1}{2}}(n+1)}{2^k}.$$ Otherwise, $a_2 = k-2.$ Note that for all $3 \le j \le m,$ $$| T_{j} | \ge \binom{a_{j}}{\lfloor a_{1}/2 \rfloor} = \binom{a_{j}}{\frac{k-1}{2}}$$if $\frac{k-1}{2} \le a_{k}.$ Otherwise we just know $T_j \ge 0.$ Either way, denote this particular lower bound for $|T_j|$ as $g(j).$ It suffices to show $$\binom{k-1}{\frac{k-1}{2}} + \binom{k-2}{\frac{k-1}{2}} + \sum_{j=3}^{m} g(j)$$is still at least the desired lower bound. For all $j \ge 3,$ we may show $g(j) \le 2^{a_j} \cdot \frac{{k\choose \frac{k-1}{2}}}{2^k}$ with an AM-GM argument. So given that $a_2 = k-2,$ the quantity $$\binom{k-1}{\frac{k-1}{2}} + \binom{k-2}{\frac{k-1}{2}} + \sum_{j=3}^{m} g(j) - \frac{{k\choose \frac{k-1}{2} }}{2^k} \cdot (n+1)$$has to be minimized when $n+1$ has all possible digits in binary from $2^0$ to $2^{k-1}$ (when $n = 2^{k}-2$), otherwise we could just put in another binary digit which does not increase the quantity. Its easy to verify that this quantity is still nonnegative in this case using the Hockey Stick identity, finishing the problem. $\square$

liekkas wrote: Given positive integer $n,k$ such that $2 \le n <2^k$. Prove that there exist a subset $A$ of $\{0,1,\cdots,n\}$ such that for any $x \neq y \in A$, ${y\choose x}$ is even, and $$|A| \ge \frac{{k\choose \lfloor \frac{k}{2} \rfloor}}{2^k} \cdot (n+1)$$ We have two cases(odd and even $k$) to check:- $\text{i)}$ $k$ is even:- So suppose that $k=2l$.Also for any $j \in \{2,2^{2l}\}$ we have functions $f_1(j),………,f_{\text{log}_2(j)}(j)$ satisfying $j=\sum_{i=1}^{\text{log}_2(j)} 2^if_i(j)$. So in other words $(j)_2=f_1(j)………..f_{\text{log}_2(j)}(j)$.Now note that by Lucas’s Theorem we have $$\binom{m}{n} \equiv \prod_{i=1}^{\text{log}_2(j)} \binom{f_i(m)}{f_i(n)} \pmod 2$$Now it remains to show that $2$ divides it.So $2$ must divide one of the $\binom{f_i(m)}{f_i(n)}$.Call $f_j(m)$ and $f_j(n)$ good if $f_j(m)-f_j(n)>0$ and bad otherwise.If good $f_j(m)$ and $f_j(n)$ exist then clearly when we $f_j(m)$ to this then clearly we get a carry.However there is another possibility also;the Carry’s from the $j-1$th line but that implies that $j-1$ and $j$ are good so atleast one of them gives a carry. Now we can construct an indicator variable $g(f_j(m),f_j(n))\in [-1,1]$ which gives $1$ if the expression is good and $(-1)$ otherwise.It is easily seen that:- $\bullet)$ $g(m,n)=g(n,m)$ $\bullet)$ $g(m+2^d,n)=g(m,n)$ whenever $d>\text{log}_2(m)$ so which is verified by Kummer’s Theorem. If there is no good $f_j(m)$ and $f_j(n)$ then we can eliminate atleast one of them. We can use the second bullet point to show that for any two $m,n$ with $g(m,n)=1$ there are $\left\lfloor \frac{m-n}{2^{\text{log}_2(m)+1}} \right\rfloor$ values satisfying $g(m',n)=$.Summing this up suppose that there are $h(n)$ such values. Now comes the hard part;we need to prove this number is $\ge \frac{{k\choose \lfloor \frac{k}{2} \rfloor}}{2^k} \cdot (n+1)$ Also it is seen that $h(n)$ increases when the smallest element in $A$ is decreased and $n$ is increased so we will choose $n=2^k-1$ and $X_1=1$.Now we will bound $\frac{{k\choose \lfloor \frac{k}{2} \rfloor}}{2^k} \cdot (n+1)<2^{\lfloor \frac{k}{2} \rfloor}$ so we need to show that $h(k)>2^{\lfloor \frac{k}{2} \rfloor}$. We will use induction to prove this.The base cases are trival;now notice that in the $n=k+1$th step we need to show that $h(k+1)>2^{\lfloor \frac{k}{2} \rfloor}$ Since we had assumed that $k$ is even so $k+1$ is odd so $2^{\lfloor \frac{k}{2} \rfloor}=2^{\lfloor \frac{k+1}{2} \rfloor}$ so since $h(k)$ is increasing we are done. $\text{i)}$ $k$ is odd It suffices to show that $\sum_{m,n;\min(m,n)=(1,2)} \left\lfloor \frac{m-n}{2^{\text{log}_2(m)+1}} \right\rfloor>\binom{2l+1}{l}$ which is true by a similar trick as before.

Preparations: We will work in base $2$ for this question. Say that $a$ dominates $b$ if $a=\overline{a_ta_{t-1}\ldots a_0}_2$ and $b=\overline{b_t\ldots b_0}_2$ and $a_i\geq b_i$ for every $0\leq i\leq t$. By expansion of Legendre's p-adic evaluation of factorials, we see that ${y\choose x}$ is even if and only if $y$ and $x$ do not dominate each other. Thus, for every positive integer $x\leq n<2^k$, we can describe it using a subset $T_x\subseteq \{0,1,\ldots, k-1\}$ where $i\in T_x$ if and only if $a_i=1$, where $x=\overline{a_{k-1}\ldots a_0}_2$. Let $f(n,k)=\frac{n+1}{2^k}{k\choose \left\lfloor \frac{k}{2}\right\rfloor}$. It therefore suffices to find a subset $A$ with $\lvert A\rvert \geq f(n,k)$ such that for any $x,y\in A$, we have that $T_x$ and $T_y$ do not contain one another - say that $A$ is special if it satisfies this condition. We easily see that $f(n,k)$ is non-increasing in $k$, so assume that $2^{k-1}\leq n<2^k$. Main proof: We proceed with induction on $k$ ($k=2$ is trivial) to prove that there exists special $A$ with $\lvert A\rvert \geq f(n,k)$ such that for all $x\in A$ we have $\lvert T_x\rvert =\left\lfloor \frac{k}{2}\right\rfloor$, and that there also exists special $A$ with $\lvert T_x\rvert =\left\lceil \frac{k}{2} \right\rceil$. But if we take the complement of every $x\in A$ with $\lvert T_x\rvert =\left\lfloor \frac{k}{2}\right\rfloor$ (inverting each digit in binary) to form $A'$, then $A'$ is still special but now $\lvert T_x\rvert =\left\lceil \frac{k}{2} \right\rceil$ for every $x\in A'$. It thus suffice to prove it for $\lvert T_x\rvert =\left\lfloor \frac{k}{2}\right\rfloor$ only in the inductive step. If $n=2^k -1$, we can take every $T_x$ with exactly $\left\lfloor \frac{k}{2}\right\rfloor$ and no two $T_x$'s contain one another, as desired. If $n<2^k-1$ then write $n=2^{k-1} + m$. Case 1: $k=2a$. Then, we simply choose $f(m,k-1)\geq f(m,k)$ numbers that work (since $f(n,k)$ is non-increasing in $k$), with exactly $\left\lfloor \frac{k-1}{2}\right\rfloor =a-1$ ones, and add $2^{k-1}$ to them so they have $a$ ones and no two dominate one another. We also take $f(2^{k-1}-1, k-1)\geq f(2^{k-1}-1, k)$ numbers with exactly $\left\lceil \frac{k-1}{2}\right\rceil = a$ ones, no two of which dominate one another. Since these two groups of numbers each have exactly $a$ ones, and the first group are greater or equal to $2^k$ while the second group are less than $2^k$, we have no overlaps and hence at least: $$f(m,k)+f(2^{k-1}-1,k)=\frac{m+1+2^{k-1}-1+1}{2^k}{k\choose \left\lfloor \frac{k}{2}\right\rfloor}=\frac{n+1}{2^k}{k\choose \left\lfloor \frac{k}{2}\right\rfloor}=f(n,k)$$$x$'s. Thus, we have a special set $A$ with all members $x$ satisfying $T_x=\left\lfloor \frac{k}{2}\right\rfloor=a$, completing the inductive step. Case 2: $k=2a+1$. Then $$\frac{n}{2}=\frac{2^{k-1}+m}{2}\geq \frac{m+2+m}{2}=m+1$$Thus, if $n=\overline{b_{k-1}\ldots b_0}_2$ , then if we consider the $f(m,k-1)\geq f(m,k)$ numbers $x$ that have exactly $\left\lfloor \frac{k-1}{2}\right\rfloor=a$ ones, then if we append a $0$ to the rightmost side of their binary representation, then $2x\leq 2m\leq n$ as needed. Now, take the $f(2^{k-1}-1, k-1)\geq f(2^{k-1}-1, k)$ numbers with exactly $\left\lfloor \frac{k-1}{2}\right\rfloor = a$ ones, and both groups once again have no overlaps as they have the same number of ones yet one group are greater than $2^k$ and the other is less, completing the inductive step similarly. This concludes the proof. EDIT: The above proof has issues regarding the value of $m$ in the inductive step. Will be fixed later

there are $\left\lfloor \frac{m-n}{2^{\text{log}_2(m)+1}} \right\rfloor$ values satisfying $g(m',n)=$.Summing this up suppose that there are $h(n)$ such values. Would somebody explain this I FOUND it really hard

$g(m',n$)is equal what???

I think that this is an educationl site Why nobody answer about that knowing that All people understand it