Let $a_1,a_2,\cdots ,a_9$ be $9$ positive integers (not necessarily distinct) satisfying: for all $1\le i<j<k\le 9$, there exists $l (1\le l\le 9)$ distinct from $i,j$ and $j$ such that $a_i+a_j+a_k+a_l=100$. Find the number of $9$-tuples $(a_1,a_2,\cdots ,a_9)$ satisfying the above conditions.
Problem
Source: CWMI 2017 Q5
Tags: algebra, combinatorics
17.08.2017 15:12
Denote $n_1, n_2, \cdots n_k$ be the numbers that appear in $a_1, \cdots a_9$. Denote $c_1, c_2 \cdots c_k$ be the number of times that $n_i$ appear in $a_1, \cdots, a_9$. I think(?) I proved the following claim. Kinda bashy but it was doable. After this, the bash seems easier to do. Claim: If $k \ge 3$, then at most two $i$s satisfy $c_i > 1$. You can prove this by there are more than $k$ numbers you can "make" by adding three integers from $a_1, \cdots a_9$. I will try to add details later.
04.12.2017 21:06
Solution Denote $A$ is the set of value of $(a_n)$ Case 1: if $|A|>=4$,denote by $a>b>c>d$ Then $100-(a+b+c),100-(a+b+d),100-(b+c+d),100-(a+c+d)$ =>$a+b-d,a+b-c,c+d-b,c+d-a \in (a_n)$ =>$100-2a-b\in (a_n)$ so $2a+b-d-c \in (a_n)$,and $2a+b-d-c<a+b-d$ we get $2a+b-d<a+b-d<a+b-c<a,b<c<d<c+d-b,c+d-a \in (a_n)$ solve this get no solution Case 2:: if $|A|$=1,then it is easy follow that $a_i=25$ with $i=1,9$ Case 3::if $|A|$=2,call $a,b$,assume $a$ apear 3 times,then 100-3a=b and 100-(2a+b)=a Solve this get no solution Case 4::if $|A|$=3,call $a<b<c$, if $c$ apear 3 times,consider $100-3c<100-2c-b<100-a-b-c$,solve this get no solution if$a$ apear 3 times,consider$100-c-b-a<100-c-2a<100-3a$,solve this get no solution if $b$ apear 3 times,consider $100-c-2b<100-3b<100-2b-a$,solve this get $b=25$,$a+c=50$ we can prove that number of a appear equal to number of b appear,that mean they can appear 1 times,there are 24.9.8,the other case is they appear 2 times,there are 24.$C^2_9.C^2_8$ So answer:24.9.8+24.$C^2_9.C^2_8$+1