be positive real numbers such that 
.
.
and 
Prove that
be a scalene triangle with circumcenter 
,
,
.
,
,
at points 
,
,
respectively. Let 
be the projection of 
.
intersects the circumcircle of 
.
and 
intersect 
and 
respectively. Prove that the lines 
,
,
are concurrent.
Y by centslordm, fattypiggy123, megarnie, jhu08, quirtt, PHSH, kiyoras_2001
Let 
be an integer, 
a finite set of integers (not necessarily positive) and 
subsets of . Suppose that, for every 
, the sum of the elements of 
is 
. Prove that contains at least 
elements.
be an integer, 
a finite set of integers (not necessarily positive) and 
subsets of . Suppose that, for every 
, the sum of the elements of 
is 
. Prove that contains at least 
elements.This post has been edited 1 time. Last edited by trying_to_solve_br, Jul 20, 2021, 8:49 PM
,
of integers such that for all integers 
with 
,
of 
.
such that every 
has cardinality at least 
.
.
as vectors 
in 
.
with small integer coefficients.
are vectors in 
where 
.
,
and all 
.
denote 
its coordinates. Then for each 
consider the ugly sum 
.
and less or equal to 
and we have 
different ways to pick 
and 
the ugly-sum will be the same. Let 
.
and 
and we have a linear combination of powers of 
and let 
if the 
biggest element of 
otherwise. Suppose that 
.
.
by 
,
by 
... and add the numbers we will get that 
where 
.
and 
.
,
for some 
.
,
for 
,![\[mx = \displaystyle\sum_{i=1}^{m}c_{i}m^{i} = \displaystyle\sum_{i=1}^{m}c_{i}\left(\displaystyle\sum_{j=1}^{k}b_{i,j}a_{j}\right) = \displaystyle\sum_{j=1}^{k}(\displaystyle\sum_{i=1}^{m}c_{i}b_{i,j})a_{j} = \displaystyle\sum_{j=1}^{k}d_{j}a_{j}\]](http://latex.artofproblemsolving.com/6/3/e/63ea7d8bf7e64f55a7b09856ce4ca3defcfc02ca.png)
for some integers 
.![\[m^{m} \le [m(m-1)+1]^{k} < m^{2k}\]](http://latex.artofproblemsolving.com/7/f/d/7fdf2e91a93722cacd0e86df21e809f578346134.png)
which immediately gives 
.
be the number of elements in 
in arbitrary order. Let 
be such that 
.
in 
we know that![\[\sum_{i=1}^{m}u_{1i}m^i\neq \sum_{i=1}^{m}u_{2i}m^i.\]](http://latex.artofproblemsolving.com/0/8/7/0879737edaf5d876443f91199f0a006946e95a82.png)
Therefore![\[\vec{u}_1^t V\vec{a}\neq \vec{u}_2^t V\vec{a}\]](http://latex.artofproblemsolving.com/4/2/6/426ce1ecaac0b6a1077fcd4952eef3d5b370e5fd.png)
where 
is a matrix such that the i-th row of 
.![\[\vec{u}_1^tV\neq \vec{u}_2^tV.\]](http://latex.artofproblemsolving.com/6/5/2/6527939288e0345ae54570437d1d37eb1ff61e82.png)
This shows that the map 
is injective for 
.
is 
.
can be defined as an injective map from 
,![\[m^m\leq (m^2)^d,\]](http://latex.artofproblemsolving.com/a/5/4/a548ef7d771cf74cc1446df52a05f846d6545eae.png)
showing that 
(note that 
)
-
such that 
.
satisfy some linear equations with small integral coefficients. In fact, no nontrivial linear equations have integral coefficients of absolute values all less than 
.
highly recommended!
can be improved to 
.
.
and consider the indicator vectors 
.
can be expressed as 
for nonnegative integers 
less than 
by applying concentration inequalities.
be i.i.d. random variables distributed as 
.
t
is the sum of 
is the number of sets among 
that 
is at most 
.
is at most 
.
nonnegative multiples of 
centered at the expectation of the corresponding coordinate of 
,
,
.
are vectors in 
,
not all equal to zero such that 
and 
,
are integers from 
.
such 
,
values that 
can obtain. Since 
when 
be the elements of 
be the vector adjoined to the subset 
for each 
.
be the integer 
.
and 
.
and 
equals 
which cannot be zero due to the bounds on 
(take the largest 
such that 
is nonzero, and then the remaining nonzero 
.
unconditionally.
.
,
,
such that 
,![\[T = c_{1}m + c_{2}m^{2} + \ldots + c_{m}m^{m}\]](http://latex.artofproblemsolving.com/7/a/6/7a6e956eb99b4d2ed0e4761789316b9d7c4c488b.png)
This is true by dividing both sides by 
,
will be included at most 
times (for each 
,
for 
ways to choose the total number of duplicates of element ![\[(m(m-1) + 1)^{|A|}\]](http://latex.artofproblemsolving.com/4/a/4/4a46fde0922135d2aa0bdc47966354dda5b51e00.png)
However, there are 
values of ![\[(m^{2})^{|A|} \geq (m(m-1) + 1)^{|A|} \geq m^{m} \Rightarrow m^{2|A|} \geq m^{m} \Rightarrow |A|\geq \frac{m}{2}\]](http://latex.artofproblemsolving.com/2/d/d/2dda20ef75e228fc50b81b440272d4070c37d499.png)
![$[0,m^{m+1}-m]$](http://latex.artofproblemsolving.com/5/2/1/5219a6acc47c151823bd9bf6428fd0e0e87421ec.png)
as pseudosums of ![\[S_{B}(m-1) = \{\sum_{k=1}^{m} e_k B_k: \forall k, e_k\in [0,m-1]\}\]](http://latex.artofproblemsolving.com/5/5/c/55c1ef0cff03a2f906597a49355b18458b944fb7.png)
Then, we have 
exactly covers all multiples of 
.![\[S_A(m^2-m) = \{\sum_{k=1}^{|A|}d_k a_k: \forall k, d_k\in [0,m^2-m]\}\]](http://latex.artofproblemsolving.com/e/6/b/e6bd7f1986f4ecc570e6955bb62d4d8ea58ee460.png)
![\[(m^2-m+1)^{|A|} \geq S_{A}(m^2) \geq S_{B}(m-1) =m^m\]](http://latex.artofproblemsolving.com/9/c/7/9c7ae3a47ef4cd4fa215e0810c72d42456d9f732.png)
Thus, 
and we're done.
of size 
and so on...
has 
elements then we are given each 
may be expressed in the form ![\[m^k=\varepsilon_{k1}a_1+\varepsilon_{k2}a_2+\cdots+\varepsilon_{kn}a_n\quad\text{where}\quad0\le\varepsilon_i\le1.\]](http://latex.artofproblemsolving.com/7/0/8/7086c3727d05ddd1b904c1f85ff0ed6dd2e59f3b.png)
nonnegative multiples of 
less than 
.
may be represented in base ![\[mj=d_m\cdot m^m+d_{m-1}\cdot m^{m-1}+\cdots+d_1\cdot m\quad\text{where}\quad0\le d_i\le m-1.\]](http://latex.artofproblemsolving.com/2/b/6/2b6a1348296fedd96ba3d4e20244e0da3be11cb8.png)
![\[w_j:=\sum_{i=1}^md_i\varepsilon_{ij}\le m(m-1),\]](http://latex.artofproblemsolving.com/5/9/5/59511bb462f05509c59f40ca37ef05022162cc93.png)
defined so that ![\[mj=w_1a_1+w_2a_2+\cdots+w_na_n\quad\text{where}\quad0\le w_i\le m(m-1).\]](http://latex.artofproblemsolving.com/9/1/2/912a71797cface6afd83304d53e20141c67cf619.png)
distinct numbers, so we have the inequality ![\[m^m\le(m^2-m+1)^n<m^{2n}.\]](http://latex.artofproblemsolving.com/a/6/1/a618e43631313a9f79b600453a114690b3a918a2.png)
from which it is clear 
.
elements. Or even slightly sharper: It contains at least 
elements, where 
is some absolute constant.
be 
dimensional binary vectors (their coordinates are only 
'
.
the vector 
can be represented as
The proof of this claim and more detailed discussion can be found 
are linearly independent and thus are basis vectors in 
.
the determinant which columns are the vectors 
in this order. Obviously 
since it is a non-zero integer. We can write
If 
we are done, so suppose 
for some 
Cramer's rule yields
hence
Note that the vectors
are also linearly independent, so 
can be written as some linear combination of them. If some of those coefficients has absolute value at least 
So, proceeding in this way for 
either we get a representation as in 
or we find a permutation of binary vectors with determinant in absolute value at least 
.
Indeed, the determinant of any 
matrix that consists only of 
(
hence 
which contradicts the imposed constraint of our claim.
and 
Let 
integers that can be written as
Where 
are integers between 
Each such integer has sum of its digits in base 
and its units digits is 
So it equals the sum of the sums of the elements of at most 
each of which encompasses distinct elements in 
so the desired linear combination exists.
,
if the 
otherwise. Henceforth suppose FTSOC that 
.
so that 
and 
for any 
,
,![\[(b_1 v_{11}+b_2 v_{21}+\ldots+b_m v_{m1})+(b_1 v_{12}+b_2 v_{22}+\ldots+b_m v_{m2})m^2+\ldots+(b_1 v_{1n}+b_2 v_{2n}+\ldots +b_m v_{mn})m^{2n-2}\]](http://latex.artofproblemsolving.com/7/d/a/7daf51b82ce8cb083847af635549007d3f4d3a27.png)
This sum is less than or equal to 
.
,![\[b_1v_{11}+b_2v_{21}+\ldots+b_mv_{m1}=b'_1v_{11}+b'_2v_{21}+\ldots+b'_mv_{m1},\]](http://latex.artofproblemsolving.com/5/1/b/51baffb5897e44f075523bade1cd954fe2bd7d9a.png)
and so on (because they are less than or equal to 
)
.
and the maximum value is 
.
.
.
for 
.
denotes sum of elements of 
(for 
)
system. On the other hand, all this numbers can be represented as 
for 
,
distinct numbers between them, contradiction.
.
.
vectors 
in 
,
it follows that 
has a nontrivial solution in 
,
nontrivial solutions in 
over all vectors.
has at most 
elements that get mapped to 
,
,
,
has a sum of 
,
is 
.
have 
elements, and let the vector ![$S=[s_1,\dots,s_l]$](http://latex.artofproblemsolving.com/9/c/e/9cee9045a78067b8942a07480b29d4b34008f285.png)
.
with 
if 
is used in the sum for 
and 
where 
for all 
can be expressed this way. However, looking at it from each 
individually, we get that each 
distinct values. Then, combine this with above to get 
which finishes.
.
where 
for all 
.
as![\[k=\frac{1}{m}\left(b_1m+b_2m^2+\dots+b_mm^m\right)\]](http://latex.artofproblemsolving.com/5/3/8/538bd9ae1e0c1c618f2712fbfaeaa5bc805644eb.png)
Where 
.![\[k=\frac{1}{m}\sum_{i=1}^{n}{a_i(b_1\varepsilon_{1i}+b_2\varepsilon_{2i}+\dots+b_m\varepsilon_{mi})}\]](http://latex.artofproblemsolving.com/4/5/d/45d695945696d286947ddfb739d861ee2d3696d5.png)
Note that 
.
ways to represent each coefficient. There are 
so 
as desired.
.
of ![\[mt=t_1a_1+t_2a_2+\cdots+t_na_n\]](http://latex.artofproblemsolving.com/e/6/a/e6a45dde526d0a78fcb55bf3a9fc9c7a576c8305.png)
where 
for each 
.
,
in base 
for 
.![\[mt = b_mm^m + b_{m-1}m^{m-1}+\cdots+b_1m+0 \]](http://latex.artofproblemsolving.com/0/f/8/0f869eb0edb7f65be7ead3a0431d0e74ae55c0b7.png)
![\[= b_m(\text{sum of elements of }B_m)+b_{m-1}(\text{sum of elements of }B_{m-1})+\cdots+b_1(\text{sum of elements of }B_1)\]](http://latex.artofproblemsolving.com/6/c/d/6cd677600f07a4de2bc56c21f6672025b23b1c0b.png)
Expanding out, we get that we can write 
.
follows from the fact that any element of 
,
are at most 
,
distinct sums possible which can be written as![\[\text{sum}=t_1a_1+t_2a_2+\cdots+t_na_n\]](http://latex.artofproblemsolving.com/d/4/8/d48dd6cf3b92f993e659efddce72ac171b49cbc4.png)
However, we have given a construction that there are at least 
and hence 
.
.
such that 
.
that is divisible by 
for some positive integer 
and some nonnegative integers 
.
and note that 
,
where 
are nonnegative integers that are not exceed 
,
,
,
and define![\[
\epsilon_{i, j} =
\begin{cases*}
1 & $a_j \in B_i$ \\
0 & $a_j \not\in B_i$
\end{cases*}
\]](http://latex.artofproblemsolving.com/e/d/6/ed6dcac55a36a197c06f2bbbf08f3f0a4a38f360.png)
We can therefore model 
By using base 
and 
such that 
can generate any number from 
.
such that 
can generate any value between 
must be at least 
.
so we have 
so 
and we are done.
,![$\mathbf B_i = [b_{1i}, b_{2i}, \dots, b_{ki}]$](http://latex.artofproblemsolving.com/a/2/d/a2d06bab0e2147aba948e8cbd0b78de955b71865.png)
be a vector for each 
if 
where 
are the elements of 
,
such that ![\[n = |d_1 \mathbf B_1 + d_2 \mathbf B_2 + \cdots + d_m \mathbf B_m| = |r_1 \mathbf e_1 + r_2 \mathbf e_2 + \cdots + r_k \mathbf e_k|\]](http://latex.artofproblemsolving.com/e/9/e/e9e12c2d9cb5566ab2a40327305dc2201d24dda6.png)
for digits 
,
are the standard basis vectors. We have the upper bound on the 
because the entries of 
are at most 
,
,
.
