AoPS Academy
be a positive integer that is not divisible by 
. Furthermore, let 
be a positive integer. Prove that none of the numbers of the form 
is a square number.
different bus lines in a city, each stopping at exactly 
stations and running in both directions. Nevertheless, for every two different stations there is always a bus line connecting these two stations. Determine the maximum number of stations in this city.
be an isosceles triangle with 
and circumcircle 
. The line through 
perpendicular to 
is denoted by 
. Furthermore, let 
be any point on . The circle 
with center and radius 
intersects 
once more at point 
and the circumcircle once more at point 
. Prove that the points 
and 
lie on a straight line.
be a positive integer. Furthermore, let ![$x_1, x_2,\ldots, x_n \in [0, 2]$](http://latex.artofproblemsolving.com/b/2/a/b2a6731961601353e26224c285a32923fbb54eb3.png)
be real numbers subject to 
. Prove the inequality
When does equality hold?
be an odd integer greater than 
Let 
be an 
symmetric matrix such that each row and column consists of some permutation of the integers 
Show that each of the integers 
must appear in the main diagonal of .
convergent?
and radius 
and the base of a hemisphere of radius 
This body is placed with the hemispherical end on a horizontal table, with the axis of the cylinder in a vertical position, and then slightly oscillated. It is intuitively evident that if 
is large as compared to , the equilibrium will be stable; but if is small compared to , the equilibrium will be unstable. What is the critical value of the ratio 
which enables the body to rest in neutral equilibrium in any position?
![\[ \begin{vmatrix} 0 & a_1 - x & a_2 - x \\ -a_1 - x & 0 & a_3 - x \\ -a_2 - x & -a_3 - x & 0\end{vmatrix} = 0 \qquad (a_i \neq 0) \]](http://latex.artofproblemsolving.com/7/2/1/721620c769b5622dc4172dd38b7a924b5d95e694.png)
shall have a multiple root.
by by inches (
and are integers). He paints the entire surface of the block, cuts the block into inch cubes, and notices that exactly half the cubes are completely unpainted. Prove that the number of essentially different blocks with this property is finite. (Do not attempt to enumerate them.)
South Latitude. The parallels of latitude are concentric circles with radii proportional to their co-latitudes. Australia is near the periphery of the map and is intersected by the parallel of latitude 
S.In the very close vicinity of this parallel how much are East and West distances exaggerated as compared to North and South distances?
and 
be relatively prime positive integers, even. For each positive integer 
, let 
be chosen so that
is a minimum. Prove that
be a permutation of the integers 
Call 
a big integer if 
for all 
Find the mean number of big integers over all permutations on the first postive integers.
be two complex matrices of the same rank, and let 
be a positive integer. Prove that 
if and only if 
.
. We want no pairs such that 
.
greedily and by induction. Firstly we choose 
.
be the first value such that 
for all ![$j \in [1, n]$](http://latex.artofproblemsolving.com/9/7/c/97c9a519a3453c51bdd4804d10c37a3c9154e90c.png)
. We can see that there are 
values of 
, and there are values of 
. Thus the number of values that cannot be obtained by 
is bounded above by 
. 
for all valid 
; in other words, 
for all valid 
and . There are up to 
distinct absolute differences between two elements of .
with common difference 
, where 
. The possible values of 
are 
; as varies from 
to 
, there must be some (in fact, at least 
) values of for which none of are the absolute difference between any two elements of , so we just pick to be any of those values.
be the largest size of such a set 
. Let 
be the numbers, and let 
be the numbers. Let be the number of numbers of the form 
, where 
. Then, we must have the inequality 
since if 
we have at least one more valid choice to add to . But, in turn, 
, which gives the desired inequality.
-element subset of 
such that, for any choice of 
numbers 
from 
, there exist indices 
and (
) such that 
and 
have at least one common element.
be the sets 
respectively. For each , the set 
can be expressed as 
.'s for 
:![\[ B = B_1 \cup B_2 \cup \ldots \cup B_{100} \]](http://latex.artofproblemsolving.com/9/3/e/93e422a9a40e45dff563a69a86b7329350ce9600.png)
, the union is essentially the set of all elements in that can be obtained by adding an element from to any of the chosen 
's. and () such that 
. This implies that there exists an element 
in such that 
, which means 
. numbers must yield distinct sets . Therefore, our assumption must be false, and there must be a -element subset with the desired property.
until we get stuck(we can't pick any more ) for some 
. This implies that for all 
, it has already been picked or that for some , , 
we have 
. So then there are at most 
( choices for and for ) values for , so 
as desired.
's greedily then for all , in , and 
we cannot pick 
, or 
in the list of 's in the future. So for every new added we eliminate at most 
more 's. So we can pick at least 
different 's before we could be forced to stop, finishing the problem.
to also be an absolute difference in 
distinct absolute differences in , at most 
elements get eliminated from as possibilities for other 
, then only at most elements get eliminated from the first time
, we can pick , as desired.
being the difference between two . Choose , for each we automatically eliminate out of candidacy for future all the numbers that are a different of two from , which is at most 
, where the 
is for positve/negative, and we also eliminate the chosen number itself, for a total for eliminations per chosen . Now any number not eliminated can be added to and the condition will still be satisfied, so add the first 
numbers and see that we have eliminated 
numbers, and there is one number remaining and we see that we can just add this and done.
. Note that and are disjoint if and only if![\[t_i-t_j \notin \{a_p-a_q\vert 1\le p \ne q \le 101\}.\]](http://latex.artofproblemsolving.com/0/a/4/0a472d7d6821c451015fb7852db17ae9b0e2d787.png)
elements in 
such that 
is as large as possible. That means every 
is either in or satisfies![\[i = t_i+b-a,\]](http://latex.artofproblemsolving.com/8/8/a/88a20f9ef2f6f0ef8339d90f6a38bc1f03ebee14.png)
and 
.
values of . Thus,![\[n+10100n \ge 10^6 \implies n>99,\]](http://latex.artofproblemsolving.com/5/a/7/5a77a3000be63f5d47a116472456b61b4186404e.png)
to have 
currently. Let 
. Let set 
denote the pair-wise differences of elements of set . to , then we must have: 
for some 
. Note that: 
. Thus: 
and we are done.
be 
and let the elements of be 
Since each 
is distinct, then clearly for all 
Set 
Clearly since there are at most pairwise differences among the elements of 
every time we add a number to the set we reduce the possible number of potential numbers to add to by at most 
(we account for both sides, and the number itself) Therefore, after choosing numbers, there are at least 
possible number to add to the set 
so thus it is possible to have elements in 
QED
.
satisfying the condition, then we can choose a 
such that the disjoint condition is satisfied. This will finish the problem.
and 
satisfying 
However, since 
, we have 
. Then, there are 
ways to choose the right-hand side of the equation 
. Since is not equal to any of 
, there are at most 
numbers that cannot be. However, 
so there always exists a .
, 
, 
are max such subsets.
has an element common with one of 
, 
, , 
. Hence for any 
, we have ![\[a_\ell+T=a_j+t_i\]](http://latex.artofproblemsolving.com/3/d/f/3dfcaa495584457f85fbd7f968b8401a36c203c0.png)
Fix RHS and see that 
takes 
values and so ![\[101k \ge \frac{10^6-k}{100} \implies k>99 \iff k \ge 100\]](http://latex.artofproblemsolving.com/3/a/4/3a41c5d60546635d95be6306d2d8235d1dee37c5.png)
And done.
be the elements which can be expressed as the difference of two elements in the list. Then 
since 
is over counted times. We now select each iteratively. Note that if is selected, then any subsequent selected can't be in 
for the sets to be pairwise disjoint, and furthermore this is sufficient. As such, we may select from 
while preserving the condition. For each , we have that
so we may choose as well to finish.
.
in ![\[ A_j=\{x+t_j\mid x\in A\},\qquad j=1,2,\ldots,100 \]](http://latex.artofproblemsolving.com/d/5/c/d5c2a7b943e8c7200361698f3eb6f83700ad68d6.png)
are pairwise disjoint.
and are searching for 
.
forbidden values of 
,
.
forbidden values, and at least 
.
are all 
,
.
such that the sets are parwise disjoint even when taken 
.
.
iff the sets 
and 
are disjoint . The graph will have 
vertices . For an arbitrary vertex 
, 
must not be one of the numbers 
, which are 
numbers . So the vertex 
.
edges. The problem asks to prove that there is an 
in the graph. But by Turan's theorem , there is a 
in a graph with 
.
.
and thus we are done.
.
and 
with distinct 
such that 
doesn't contain 1 and any element 
satisfying 
for any distinct 
Choose the smallest element from 
for 
such that 
doesn't contain 
for any distinct 
.
satisfy the condition and the interesting fact is for choosing all 
,
instead of 
.
where 
which implies 
and thus the strategy is optimized by two 
and 
such that 
.
(According to algorithm).
be the vertex of a graph where two vertices 
are connected by an edge if and only if the sets 
and 
are disjoint. Consider an arbitrary vertex 
.
the maximum number of vertices 
such that sets 
are not disjoint is 
.
Therefore the graph has at least 
edges. It suffices to show that this graph contains 
as a subgraph.
vertices that does not contain 
-
independent sets of size 
and 
independent set of size 
.
edges. But since 
we have the desired result.
satisfying the problem conditions for maximal 
and 
for some 
or 
for some integers 
and 
.
,
,
,
.