More combinatorics...
by yayups, Nov 16, 2017, 6:42 AM
USAMO 2009 wrote:
Let 
be a positive integer. Determine the size of the largest subset of 
which does not contain three elements 
, 
, 
(not necessarily distinct) satisfying 
.
be a positive integer. Determine the size of the largest subset of 
which does not contain three elements 
, 
, 
(not necessarily distinct) satisfying 
.
for 
be the set of positive numbers in our subset, and 
be the set of negative numbers (note that 
is not in our subset since 
)
are disjoint. Note that![\[P+N = \{p+n : p\in P, n\in N\}.\]](http://latex.artofproblemsolving.com/c/f/1/cf11e115c266431a0cb78ede848b484013f46177.png)
.
and let 
.
:![\[x_1+y_1<x_2+y_1<\cdots<x_m+y_1<x_m+y_2<\cdots<x_m+y_n.\]](http://latex.artofproblemsolving.com/6/6/e/66e665e18efc8f829f123a2b7d0bc409b684e6c1.png)
This proves the claim. Now, since ![\[|-P|+|-N|+|P+N|\le 2n+1\implies |P|+|N|+|P|+|N|-1\le 2n+1\implies |P|+|N|\le n+1.\]](http://latex.artofproblemsolving.com/5/9/e/59e5c002887643506b9226af4a531dc0a4c65b23.png)
This completes the proof for the odd case, but this is not strong enough for the even case.
if 
,
.
,
,
and 
.
.
.
,
.
.
,
of them can be in 
since 
)
elements in 
.Taiwan TST 2014 wrote:
Positive integers 
(
) are arranged in a circle such that each 
divides the sum of the neighbors; that is ![\[ \frac{x_{i-1}+x_{i+1}}{x_i} = k_i \]](//latex.artofproblemsolving.com/6/1/4/614c1ed73a3f522f8b49052d30f83a51990d7000.png)
is an integer for each 
, where 
, 
. Prove that ![\[ 2n \le k_1 + k_2 + \dots + k_n < 3n. \]](//latex.artofproblemsolving.com/2/0/b/20b958efb33e616cd105317242b09b2f215059cd.png)
(
) are arranged in a circle such that each 
divides the sum of the neighbors; that is ![\[ \frac{x_{i-1}+x_{i+1}}{x_i} = k_i \]](http://latex.artofproblemsolving.com/6/1/4/614c1ed73a3f522f8b49052d30f83a51990d7000.png)
is an integer for each 
, where 
, 
. Prove that ![\[ 2n \le k_1 + k_2 + \dots + k_n < 3n. \]](http://latex.artofproblemsolving.com/2/0/b/20b958efb33e616cd105317242b09b2f215059cd.png)
![\[\sum_{i=1}^n k_i = \sum_{i=1}^n\left(\frac{x_{i+1}}{x_i}+\frac{x_{i-1}}{x_i}\right)\ge (2n)\sqrt[2n]{1}=2n,\]](http://latex.artofproblemsolving.com/5/c/f/5cff0052690a40fb97da0ee3f1907085749ca31b.png)
where the inequality is AM-GM.
.
.
,
.
and 
,
and 
,
.
,
,
.
be the maximum element. There are three cases.
.
.
.
.
.
s
,
.
.
where the inequality follows from the inductive hypothesis. Therefore, our induction, and our proof is complete.IMO 1995 wrote:
Let 
be an odd prime number. How many -element subsets 
of 
are there, the sum of whose elements is divisible by
be an odd prime number. How many -element subsets 
of 
are there, the sum of whose elements is divisible by 
to be the sum of the elements of some set 
.![\[f(x,y) = (1+xy)(1+x^2y)\cdots (1+x^{2p}y) = \sum_{A\subseteq[2p]}x^{s(A)}y^{|A|}.\]](http://latex.artofproblemsolving.com/d/2/0/d20e003b06b471a3cc111f5ba1d59d86361e7503.png)
We want![\[T:= -2 + \sum_{A\subseteq[2p]}\mathbf{1}_{p\mid s(A)}\mathbf{1}_{p\mid |A|}.\]](http://latex.artofproblemsolving.com/b/5/c/b5cc15fe501519c6eecfc2abd9285c4dada35283.png)
Let 
.![\[2+T = \frac{1}{p^2}\sum_{j=0}^{p-1}\sum_{k=0}^{p-1}f(\omega^j,\omega^k).\]](http://latex.artofproblemsolving.com/0/9/0/090f85d03be15ce61438312ca0ff813189e6de06.png)
If 
,
,
.
Thus, the answer is 
.
April 2021
September 2020