combinatorics
IMO
IMO 2005
graph theory
IMO Shortlist
Dan Schwarz
evan orz

In a mathematical competition, in which $6$ problems were posed to the participants, every two of these problems were solved by more than $\frac 25$ of the contestants. Moreover, no contestant solved all the $6$ problems. Show that there are at least $2$ contestants who solved exactly $5$ problems each.

[i]Radu Gologan and Dan Schwartz[/i]

Hiho!

Let n be the number of participant with [tex]n=5k+r, r\in\{0,1,2,3,4\}[/tex]. Then, let [tex]a_i\in\{0,1,2,3,4,5,6\}, i=1,2,...,n[/tex] be the number of problems solved by the participant i. Further, let x be the number of triples (i,j,k), for which the ikth participant has solved the i-th and j-th problem. [EDITED]
Then, by assumption, we get [tex]x\geq{6\choose 2}\lceil\frac{2n}{5}\rceil[/tex] if [tex]n[/tex] is not divisible by 5 or [tex]x\geq{6\choose 2}\left(\frac{2n}{5}+1\right)[/tex] if n is. On the other hand, we get the exact value by [tex]\sum {a_i\choose 2}[/tex]. Assuming that at most one particpant has solved 5 problems, we get [tex]x\leq (n-1){4\choose 2}+{5\choose 2}=6n+4=30k+6r+4[/tex]. If r=0,1,2, we have [tex]x\geq {6\choose 2}(2k+1)=30k+15[/tex] , whence [tex]6r\geq 11[/tex], which is a contradiction if [tex]r\neq 2[/tex]. If [tex]r=3,4[/tex], we have [tex]x\geq {6\choose 2 }(2k+2)=30k+30[/tex], whence [tex]6r\geq 26[/tex], which is a contradiction.

So what's left is the case when [tex]n\equiv 2\pmod{5}[/tex]. Perhaps somebody finds a nice conclusion of this proof.

Hanno

Maybe I made some stupid mistake, but it seems to be straightforward. Wlog, we assume that, say, Fedja solved problems 1,2,3,4,5 and other $N$ participants have solved 4 problems each (if not, we tell to some of them solutions of some problems which they did not going to solve for satisfying this condition). For any two indecies $1\le i<j\le 6$ we know that the total number of participants who has solved problems $i$ and $j$ is not less than $(2N+3)/5$ (since it is integral and is more than $2(N+1)/5$). Sum up by all 15 pairs of indecies. Fedja will be counted 10 times, each other will be counted 6 times. So, we get $6N+10\ge 3(2N+3)=6N+9$. It is right inequality indeed, but the difference between LHS and RHS is exactly 1. It means that

1) $2N+3$ is divisible by 5. Indeed, if not, we have $\ge (2N+4)/5$ instead $(2N+3)/5$ in our estimates, and ge wrong inequality $6N+10\ge 3(2n+4)$.

2) for all pairs of problems except 1 the number of participants which solved both problems from this pair is exactly $k=(2N+3)/5$, while for one pair of problems this number equals $k+1$.  There are two principal cases: this exceptional pair contains problem 6 or not.

a) exceptional pair contains problem 6, say, it is 61. Sum up numbers of participants, which solved 61,62,63,64,65. Every counted participant was counted 3 times, hence $5k+1$ is divisible by 3. On the other hand, sum up numbers of participants, which solved 12,13,14,15,16. Fedja will be counted 4 times, each other 3 times, hence $5k+1$ is congruent to 4 modulo 3. A contradiction.

a) exceptional pair does not contain problem 6, say, it is 34. Do the same thing, just with $5k$ instead $5k+1$.

[quote="mozilla"]I think this problem appears in IMO 1998 problem 2, exactly the same problem.

IMO 2005 is too easy, I'm sure more than 60 contestants score 42 points, China, Russia, USA, Bulgaria, Vietnam, Korea score a total of 252 points.[/quote]

An interesting prognose..

Imo 1998 problem 2: In a competition there are a contestants and b judges, where $b\geq3$ is
an odd integer. Each judge rates each contestant as either “pass” or “fail”.
Suppose k is a number such that for any two judges their ratings coincide
for at most k contestants. Prove $\frac{k}{a}\geq \frac{b-1}{2b}$.

I agree with the IMO 98 #2 observation. When I did this problem, I initially approached it using the techniques I remembered from that problem (basically counting in two ways), and it just fell right out. In fact, while $n \equiv 2 {\pmod 5}$ is the only case we have to deal with (where n is the number of contestants), it doesn't even really matter. The contradiction from counting in two ways is direct and does not depend on the modular value of n.

(I first thought that a nicer solution could be achived by considering a bip. graph with one partition being the problems and the other the n contestants and then achieve a contradiction like that, but i wasn't lucky that way, so i think it would be the same thing but just reinterpreting the problem in graphs terms)
Well, here goes an ungly but a complete and correct  ( i hope!) solution:

Let $c$ be the number of students who solved at most 4 problems and let $k$ be the number of students who solved exactly 5 and $n=c+k$ the total number of students.  A "[i]trio[/i]" is a pair of problems and a particular contestant who solved the pair. So we  have $ {4\choose 2}c + {5\choose 2}k=6n+4k$ trios.
We also know that for each of the 15 pairs we have more than $\frac{2n}{5}$ trios.

[b]Case 1[/b] $n=5p$
For each of the 15 pairs we have at least $\frac{2n}{5} +1$ trios. So a total of at least $6n+15$ pairs so from this we have $6n+4k \geq 6n+15$ so $k \geq 4$
[b]Case 2[/b]$n=5p+1$
Doing the same thing as in case 1 we obtain $k \geq 3$
[b]Case 3[/b] $n=5p+3$
Doing the same thing as in cases 1 and 2 we obtain $k \geq 3$
[b]Case 4[/b] $n=5p+4$
Doing the same as in the above cases we obtain $k \geq 2$
[b]Case 5[/b]$n=5p+2$
Doing the same as in the above cases we obtain $k \geq 1$ but we have to show that $k \geq 2$
So suppose not, that is there are $5p+1=c$ contestants with at most 4 solved problems and $k=1$ that solved exactly 5 problems.WLOG assume each of the $c$ contestans solved 4 problems. Let 1,2,3,4,5,6 be the 6 different problems. WLOG assume that the contestant who solved 5 problems, solved problems 1,2,3,4,5.
The total number of trios is $6(5p+1)+10=30p +16$ For each pair of problems the number of trios is at least $\lceil \frac{2n}{5} \rceil = 2p+1$. So we have  14 pairs with $2p+1$ trios and one pair with $2p+2$ . Now lets count for every problems the numbers of trios in which that problem is included. For 4 of the problems, this number must be
$5(2p+1) = 10p+5$. For 2 of the problems this number must
be $4(2p+1)+(2p+2) = 10p+6$

Let $a_1,...,a_n$ be the contestants. If we start with the contestant $a_m$ who has solved the 5 problems
1,2,3,4,5, the number of triosper problem is given by
the following table:

problem:.1 - 2 - 3 - 4 - 5 - 6
- - - - - - - - - - - - - - - - - - - - - - - - - - -
trios $a_m$ :    4 -  4 - 4 - 4 - 4 - 0
......... $a_j$:    3 -   3  - 3 - 3 - 0 - 0

Now imagine that we add the contestants that have solved 4 problems, one by one. Each contestant will increase the number of trios for each of the problems he has solved by 3, whilst the number of trios for the two problems he has not solved stays the same. In the end, the table must have 4 columns with each summing to a value $10p+5$ and 2 columns each summing to a value $10p+6$. This means that among the first five columns, there must be one with entries summing to $10p+5$ and one with entrie summing to $10p+6$. However, the value of each of the first 5 columns is of the form $4+3i$ for some $i$, hence it is impossible that two of the first 5 columns differ only by 1 in the end. Therefore, our assumption that such a counterexample exists must have been wrong. This shows that $k \geq 2$ must hold also for $n=5p+2$

Here's my partial solution:

Let there be $n$ students.  Make a grid with $n$ rows and 15 columns.  Each column represents a PAIR of problems, and each row represents a student.  Mark a square if the student for its row solved the pair of problems for its column.  Since the number of marked squares in each row is at least $\frac{2}{5}n+\frac{1}{5}$, the total number of marked squares in the grid is at least $\frac{2}{5}$ of the total number of squares plus three more--that is, at least $6n+3$.

Now look at each row.  If a student solves 4 problems, he/she solves 6 pairs.  If a student solves 5 problems, he/she solves 10 pairs.  If at most one student solves 5 problems, then the maximal number of marked squares is $6n+4$.  I think from here a contradiction can probably be derived, but I don't know how yet.

Ofcourse, the idea of the solution it is preaty obvious... but why don't you all write a clear solution ?
I'll write mine and i hope that i'm right.
Let $n$ be the number of the contestants and $a_n$ the problems the $n$th contestant solved. Then, by counting the number of triples (problem,problem,contestant) such that both two problems were solved by the contestant, we easily get that $6n=\frac{2}{5} \cdot n \cdot {6\choose 2} < \sum_{i=1}^n \frac{a_i \cdot (a_i -1)}{2} $.
If noone solved 5 problems, then $a_i \leq 4$ for all $i$. So $6n < \sum_{i=1}^n \frac{a_i \cdot (a_i -1)}{2} \leq \sum_{i=1}^n 2 \cdot (a_i -1)$. But since both sides are even we get : $ 6n +2 \leq \sum_{i=1}^n 2 \cdot (a_i -1)$ or $ 4n +1 \leq \sum_{i=1}^n a_i \leq 4n $ . Contradiction.
If only one solved 5, let her be $a_n$. Then, similarly, $6n +1 \leq 5+ \sum_{i=1}^{n-1} \frac{a_i \cdot (a_i -1)}{2} \leq 5+ \frac{3}{2} \cdot  \sum_{i=1}^{n-1} (a_i) \leq 5 + \frac{3}{2} \cdot 4 \cdot (n-1)$ so $ 6n +1 \leq 6n -1$. Contradiction.
The result follows.

Anto, your solution is wrong, because $a(a-1)/2$ for $a=5$ equals 10, not 5.

:oops:  :oops:  Ofcourse it is!
What a stupidity! It couldn't be that simple! Althgought it's not that hard either.
Anyway, I know how to fix the gap, but i'm not posting it, because it is similar to manuel's approach, so no reason for writting it.
Thanks, Fedor.

Hola!
I am in Merida, Mexico now.
I would just like to say that showing that n is congruent to 2 mod 5 is not worth anything.
I thought it should have been worth something, but...
In any case, once you get this part the IOs come naturally, so you could say it IS worth something, if you just mention a few more things. But not worth a lot in total anyway.

Singapore has coordinated 3 Qs so far, and we tried to get 6 done, but apparently they are still scrutinising our scripts, so I am free till after lunch. *grumble* Rats. I cannot type well on this keyboard. For one I cannot find the apostrophe key.

Well, I believe that Singapore can get more points for Q6 than for Q1, which is really strange! In fact, Q1 is probably our HARDEST problem. 4 is the easiest, followed by Q3, for us. Ugh. This is a really strange IMO for us. Well, we all have Chichen Itza to look forward to tomorrow, barring hurricanes. That is, Hurricane Emily.

Um, okay, some last thoughts.

After obtaining the congruent to 2 mod 5 thing, I do a contradiction argument. I consider the special column that the 5-problems solver did not solve, and count problem pairs. That gets rid of one case. Then I consider the column with the least solutions, then count pairs again. This finishes the other case.

This is the approach one of our contestants used, so I am going to try to push for more marks. He used the same approach as I did, but stops 2-3 lines short of the solution. What a pity. And those 2-3 lines are not even difficult. I have it written down in my notes and I hope the coordinators will agree it is easy to complete when they see what he has done.

Hi once again!

[quote]Let n be the number of participant with n=5k+r, r\in\{0,1,2,3,4\}. Then, let a_i\in\{0,1,2,3,4,5,6\}, i=1,2,...,n be the number of problems solved by the participant i. Further, let x be the number of triples (i,j,k), for which the ikth participant has solved the i-th and j-th problem. [EDITED]
Then, by assumption, we get x\geq{6\choose 2}\lceil\frac{2n}{5}\rceil if n is not divisible by 5 or x\geq{6\choose 2}\left(\frac{2n}{5}+1\right) if n is. On the other hand, we get the exact value by \sum {a_i\choose 2}. Assuming that at most one particpant has solved 5 problems, we get x\leq (n-1){4\choose 2}+{5\choose 2}=6n+10=30k+6r+4. If r=0,1,2, we have x\geq {6\choose 2}(2k+1)=30k+15 , whence 6r\geq 11, which is a contradiction if r\neq 2. If r=3,4, we have x\geq {6\choose 2 }(2k+2)=30k+30, whence 6r\geq 26, which is a contradiction.

So what's left is the case when n\equiv 2\pmod{5}. Perhaps somebody finds a nice conclusion of this proof. [/quote]

Let's check when the case [tex]n\equiv 2\pmod {5}[/tex] does not lead immediately to a contradiction. In fact, if our inequalities become equalities, that is, if [tex]{4\choose 2}(n-1)+{5\choose 2}={6\choose 2}\frac{2(n+3)}{5}[/tex]. But this is a contradiction since the LHS is congruent to 1 modulo 5 and the RHS is congruent to 0 mod 5. But, if we want to change the estimation on the LHS, we have to replace one of the binomial coefficients by a lower value; but, whatever we do, we get LHS which is at least 2 smaller as the old one, which leads to a contradiction since we must have [tex]6r\geq 11[/tex]. On the other side, we can assume that the RHS is 1 bigger than the old one - then we get [tex]{4\choose 2}(n-1)+{5\choose 2}={6\choose 2}\frac{2(n+3)}{5}+1[/tex], which is also a contradiction since the LHS is congruent to 4 modulo 6 and the RHS is congruent to 1 modulo 6. Other cases cannot occur and we're done.

Hanno

[quote="Hanno"]
In fact, if our inequalities become equalities, that is, if [tex]{4\choose 2}(n-1)+{5\choose 2}={6\choose 2}\frac{2(n+3)}{5}[/tex].[/quote]

Hi, this is wrong. It should be $\binom{4}{2}(n-1)+\binom{5}{2} \geq \binom{6}{2}\frac{2n+1}{5}$.

By the way Fedor Petrov already proved the case for $n\equiv 2 \pmod{5}$, he assumes that one contestant solves 1,2,3,4,5. Then he counts:
1) number of contestants who solve 16,26,36,46,56
2) number of contestants who solve 16,15,14,13,12.
These two countings have equal values but they are different mod 3, contradiction.

Suppose not. Suppose there are $n$ contestants, and that the $i$th contestant solves $c_i$ problems. Then, the $i$'th contestant solves $\binom{c_i}{2}$ pairs. Since there is at most one contestant who solves $5$ problems, the remaining contestants may solve at most $4$ problems each. Therefore, the total number of pairs solved is
\begin{align*}
	\sum_{i = 1}^n \binom{c_i}{2} \leq \binom{4}{2}(n - 1) + \binom{5}{2} = 6n + 4.
\end{align*}

Now, we take cases on $n$ modulo $5$. Suppose $n = 5k$, for a positive integer $k$. Then, each pair of problems must be solved by at least $2k + 1$ people. Hence, we have
\begin{align*}
	6n + 4 = 30k + 4 &\geq 15(2k + 1),
\end{align*}
which is false. Hence, $n \not\equiv 0 \pmod{5}$.

Suppose $n = 5k + 1$, for a positive integer $k$. Then, each pair of problems must be solved by at least $2k + 1$ people. Hence, we have
\begin{align*}
	6n + 4 = 30k + 10 &\geq 15(2k + 1),
\end{align*}
which is false. Hence, $n \not\equiv 1 \pmod{5}$.

Suppose $n = 5k + 3$, for a positive integer $k$. Then, each pair of problems must be solved by at least $2k + 2$ people. Hence, we have
\begin{align*}
	6n + 4 = 30k + 22 &\geq 15(2k + 2),
\end{align*}
which is false. Hence, $n \not\equiv 3 \pmod{5}$.

Suppose $n = 5k + 4$, for a positive integer $k$. Then, each pair of problems must be solved by at least $2k + 2$ people. Hence, we have
\begin{align*}
	6n + 4 = 30k + 28 &\geq 15(2k + 2),
\end{align*}
which is false. Hence, $n \not\equiv 4 \pmod{5}$.

Therefore, $n = 5k + 2$, for a positive integer $k$. In this case, each pair of problems is solved by at least $2k + 1$ people, so we have
\begin{align*}
	6n + 4 = 30k + 16 \geq \sum_{i = 1}^n \binom{c_i}{2} \geq 15(2k + 1) = 30k + 15.
\end{align*}
If any of the $c_i$'s are less than $4$, we have
\begin{align*}
	\sum_{i = 1}^n \binom{c_i}{2} \geq \binom{5}{2} + \binom{4}{2}(n - 2) + \binom{3}{2} = 6n + 1 = 30k + 13 < 30k + 15,
\end{align*}
contradiction. Thus, each $c_i$ is at least $4$, so $1$ person solves $5$ problems while the other $5k + 1$ people solve $4$ problems each; in particular, $\sum_{i = 1}^n \binom{c_i}{2} = 30k + 16$.

Now, suppose $s(i, j)$ people solve both problems $i, j$. We have
\begin{align*}
	\sum_{i = 1}^n \binom{c_i}{2} = \sum_{1 \leq i < j \leq 6} s(i, j) &= 30k + 16
\end{align*}
Since each $s(i, j)$ is at least $2k + 1$, $14$ of these $s(i, j)$'s must be equal to $2k + 1$, and the last must be equal to $2k + 2$ (since each $s(i, j)$ is an integer). WLOG, suppose $s(1, 4) = 2k + 2$, and that $s(i, j) = 2k + 1$ for every other $(i, j)$.

Now, suppose the person who solves $5$ problems misses one of $1, 4$. WLOG, suppose he misses $1$. Then, the number of people who solved $4$ problems and who solved $1$ is equal to
\begin{align*}
	\frac{\sum_{1 \leq i \leq 6, i \neq 1} s(1, i)}{3} = \frac{(2k + 2) + 4(2k + 1)}{3} = \frac{10k + 6}{3}
\end{align*}
(each person who solved $1$ solved $3$ others as well, and so accounts for $3$ solves of pairs including $1$). By similar reasoning, the number of people who solved $4$ problems and who solved $4$ is equal to
\begin{align*}
	\frac{\sum_{1 \leq i \leq 6, i \neq 4} s(4, i) - 4}{3} = \frac{(2k + 2) + 4(2k + 1) - 4}{3} = \frac{10k + 2}{3}
\end{align*}
(we must subtract the number of pairs including $4$ which are solved by the person who solves $5$ problems). As the number of people who solve a given problem is an integer, both $\frac{10k + 6}{3}$ and $\frac{10k + 2}{3}$ are integers; but this is impossible, as they differ by $\frac{4}{3}$.

Therefore, the person who solves $5$ problems misses one of $2, 3, 5, 6$. WLOG, suppose he misses $6$. By identical logic as above, the number of people who solve $4$ problems and who solved $6$ is equal to
\begin{align*}
	\frac{\sum_{1 \leq i \leq 6, i \neq 6} s(6, i)}{3} = \frac{5(2k + 1)}{3} = \frac{10k + 5}{3},
\end{align*}
while the number of people who solved $4$ problems and who solved $3$ is equal to
\begin{align*}
	\frac{\sum_{1 \leq i \leq 6, i \neq 3} s(3, i) - 4}{3} = \frac{5(2k + 1) - 4}{3} = \frac{10k + 1}{3}.
\end{align*}
Hence, both $\frac{10k + 5}{3}$ and $\frac{10k + 1}{3}$ are integers, again impossible as the two differ by $\frac{4}{3}$.

Therefore, as we have exhausted all cases, we have reached a contradiction. Thus, at least $2$ people solved $5$ problems, as desired. $\Box$

Suppose there are $n$ contestants. Let $N$ be the number of triples $(C, P_i, P_j)$ where $i<j$ and contestant $C$ solves both problems $P_i$ and $P_j$. Note
\[ N > \binom{6}{2} \cdot \left\lceil \frac{2n}{5} \right\rceil. \]
Suppose $n_i$ contestants solved $i$ problems. We know $n_6=0$, and assume $n_5 \le 1$. Then
\begin{align*}
    N &=\binom{2}{2}n_2 + \binom{3}{2}n_3 + \binom{4}{2}n_4 + \binom{5}{2}n_5 \le n_2+3n_3+6n_4+10.
\end{align*}
If $n_5=0$, then $N=n_2+3n_3+6n_4 \le 6n$. If $n_5=1$, then the above is at most $6(n-1)+10=6n+4$. In all cases, $N\le 6n+4$. Let $n=5q+r$, for $r \in [0,4]$. Then
\[ 6n+4=30q+6r+4\ge N  > 15 \left \lceil \frac25(5q+r) \right \rceil = 30q + 15\lceil 2r/5 \rceil,\]
so $6r+4 > 15\lceil 2r/5 \rceil$. This only happens if $r=2$, so $n\equiv 2 \pmod5$. Since $n=5q+2$ and $N > 30q+15$, the only possible case is where $n_4=n-1,n_5=1$ and every other $n_i=0$ (any other case has $N$ smaller than $30q+15$), where we get $N=30q+16=6n+4$.

Suppose $a_{ij} > 2q+1$ is the number of people who solve problem $P_i$ and $P_j$. Since $a_{11}+\cdots+a_{56}=N=30q+16$, we must have 14 of the $a_{ij}$ be $2q+1$ and the last be $a_{y,z}=2q+2$ for some $y,z$. Call the 1 kid who solved 5 problems Pogal. Say Pogal missed P6, and say $M_i$ people solved Problem $i$. The expression $a_{16}+a_{26}+\cdots+a_{56}$ counts each person who solved P6 in 3 terms, based on the other 3 problems they solved. So
\[ 3M_6 = a_{16}+a_{26}+a_{36}+a_{46}+a_{56}=10q+6. \]
But for any $x\not \in \{y,z,6\}$,
\[ 3M_x + 1 = a_{1x} + a_{2x}+ \cdots +  a_{x6} = 10q+6 \]
since Pogal now falls into 4 of the terms instead of just 3. The firs equations says that $10q+6$ is 0 mod 3, while the second says $10q+6$ is 2 mod 3, contradiction.

[hide=Remarks]The first double counting argument eliminates most cases, and tells all the information about the remaining case of $n\equiv 2 \pmod5$. The rest is easy by analyzing the problem that Pogal missed. [/hide]

[hide=note]pogal is absolutely unreal  :gleam:[/hide]

[hide=Solution]Let $S$ be the number of pairs $((x,y),a)$ where contestant $a$ solved problems $x,y$. If there is at most one person who solved 5 problems, then
\[10 + 6(n-1) \ge S \ge  15m\]
where $m$ denotes the smallest integer larger than $2n/5$. Casework on $n\pmod{5}$ gives that the only possible case is $n = 5k+2$. In this case, exactly one person (this person we call $A$) solved 5 problems (WLOG problems 1, 2, 3, 4, 5) and everyone else solved 4 problems, and exactly one pair of problems gets solved by $2k+2$ people and the rest gets solved by $2k+1$ people.

[b]Case 1:[/b] $(u,6)$ is the unique pair of problems which gets solved by $2k+2$ people. Let $X$ be the number of non-$A$ contestants who solved problem 6, and let $Y$ be the number of non-A contestants who solved problem $u$. Then $3X = 10k+6$ and $3Y = 10k+2$, so $3\mid 10k+6$ and $3\mid 10k+2$, which is impossible.

[b]Case 2:[/b] $(u,v)$ is the unique pair of problems solved by $2k+2$ people where $u,v\neq 6$. Then similar to above we get $3 \mid 10k+2$ and $3\mid 10k+1$, impossible.[/hide]

Let the contestants be $C_1,C_2,...,C_n$ and the problems be $P_1,P_2,...,P_6$
Let $N$ be the number of pairs $(C_i,(P_j,P_k))$ such that contestant $C_i$ solves both $P_j$ and $P_k$, where $j<k$. Now suppose contest $C_i$ solves $q_i$ problems, then we have
$$N=\sum_{m=1}^n\binom{q_m}{2}\qquad (1)$$
Meanwhile, for each $P_j,P_k$ there are at least $\frac{2n+1}{5}$ corresponding values of $i$ from the condition, hence
$$N\geq \binom{6}{2}\frac{2n+1}{5}=6n+3$$
Notice that $\binom{5}{2}+(n-1)\binom{4}{2}=6n+4$, therefore if no 2 contestants solve exactly $5$ problems then the only possibility is that exactly one contestant,say $C_1$ solves $5$ problems, and others all solve $4$ problems. Moreover, we must have $n=5p+2$ for some $p\in\mathbb N$ there is exactly one pair say $(1,2)$ such that $P_i$ and $P_j$ are solved by $2p+2$ contestants and others are solved by $2p+1$ contestants. Now for each $1\leq m\leq 6$, let $N_m$ be the number of pairs such that one of $i$ and $j$ equals $m$. Then we have $N_3=N_4=N_5=N_6=6(2n+1)$, and in particular is divisible by $3$. Now if $P_m$, where $3\leq m\leq 6$ are solved by $C_1$, then $i=1$ contributes $4$ to the number $N_m$, and other values of $i$ contributes either $3$ or $0$ to $N_m$, this shows that $N_m$ is not divisible by $3$, contradiction. Therefore $P_3,P_4,P_5,P_6$ are not solved by $C_1$, which contradicts the assumption that $C_1$ solves $5$ problems, this completes the proof.

Let's just bash this.

Assume otherwise.
We introduce some notations :
[list]
[*]Let the contestants be $C_1,C_2,\dots,C_n$.
[*]Let the problems be $P_1,P_2,\dots,P_6$.
[*]Let $a_i$ denote the number of problems solved by $C_i$.
[*]Let $b_i$ denote the number of contestants who solved $P_i$
[*]Let $x_{ij}$ denote the number of contestants who solved both $P_i$ and $P_j$.
[/list]
By assumption, we have $x_{ij}\geq \frac {2n+1}{5}$.
Wlog we have $a_1\leq 5$ and $4\geq a_2\geq a_3\geq \dots \geq a_n$.
---------------------
Let $S$ denote the number of triples $(C_i,P_j,P_k)$ such that $C_i$ solved both $P_i,P_j$. On one hand we have :
$$\vert S \vert = \sum_{1\leq i <j \leq 6}x_{ij} \geq \binom 62 \cdot \frac {2n+1}{5} = 6n+3$$
We also have :
$$\vert S \vert = \sum_{1\leq i \leq n}\binom {a_i}{2} $$

Assume $a_1<5$ , then we have from the above expression :
$$\vert S \vert = \sum_{1\leq i \leq n}\binom {a_i}{2} \leq \binom 42 \cdot n =6n<6n+3 $$
So $a_1=5$. Next suppose, $a_n<4$. Then we have :
$$\vert S \vert = \sum_{1\leq i \leq n}\binom {a_i}{2}\leq 5+\tbinom 42 \cdot (n-2)+ 3=6n+1<6n+3$$

Hence we conclude that $a_1=5$ and $4=a_2=a_3=\cdots a_n$.
WLOG , $C_1$ doesnt solve $P6$.

Next note that we have :
$$\sum_{i=1}^{6}b_i = \sum_{j=1} a_j = 5+4(n-1)=4n+1$$

We will now consider the sum :

$$\sum_{j=2}^{6} x_{1j} \geq 5\cdot \frac {2n+1}5=2n+1$$

Note that since every contestant except $C_1$ solving $P_1$ also solves exactly three other problems whereas $P_1$ solves $4$ other problems. This gives :

$$\sum_{j=2}^{6} x_{1j}=4+3(b_i-1)=3b_i+1\geq 2n+1$$

This gives $b_i \geq \frac {2n}3$ for all $1\leq i\leq5$.
We also have in a similar way :
$$\sum_{j=1}^{5} x_{6j}=3b_6\geq 2n+1$$

Assume $n\neq 0\pmod 3$. Then we have $b_i\geq \frac {2n+1}3$ for all $1\leq i\leq5$.
So $\displaystyle \sum_{i=1}^{6}b_i\geq 6\cdot \frac {2n+1}3 = 4n+2 (\rightarrow \leftarrow)$.

Thus we have $3\mid n \implies b_6 \geq \frac {2n}3+1$.

Now we have $\displaystyle \sum_{i=1}^{6}b_i\geq 5\cdot \frac {2n}3+ \frac {2n}3+1 = 4n+1$

Thus since equality holds everywhere, we must have : $b_i=\frac {2n}3$ for all $1\leq i\leq5$ and $b_6=\frac {2n}3+1$.

We will now compute  $\displaystyle \sum_{1\leq i<j\leq 5}x_{ij}$. Note that it is atleast $\tbinom 52 \cdot \tfrac {2n+1}5=4n+2$.

We will count it in another way. Note that $C_1$ solves everything, so he contributes a total of $\tbinom 52$ to the score. The contestants who solved $P6$ solve some $3$ other problems amongst the first five and the contestants who are not $C_1$ and didnt solve $P_6$ solve $4$ amongst the first five problems. So we have :

$$\sum_{1\leq i<j\leq 5}x_{ij}= \binom 52 + \binom 42 \cdot (n-1-b_6) + \binom 32 \cdot b_6=4n+1<4n+2$$

Hence we have the desired contradiction and we are done. $\blacksquare$.

[b]Remark :[/b] Unsurprisingly, this just breaks if pushed hard enough. YUH.

Completely agree with @above's remark.

Let $n$ be the number of contestants, and suppose $2n\equiv r\pmod{5},$ where $r\in\{0,1,2,3,4\}.$ Let $x_i$ be the number of contestants who solved $i$ problems. Assume, for the sake of contradiction, that $x_5<2.$\\\\Let $N$ the number of unordered triples $(P_1,P_2,C)$ such that contestant $C$ solved problems $P_1$ and $P_2.$ If we fix $C$ and then choose $C_1,C_2,$ it is easy to see that $$N=\binom{2}{2}x_2+\binom{3}{2}x_3+\binom{4}{2}x_4+\binom{5}{2}x_5.$$ On the other hand, if we choose $P_1,P_2$ first, then by the given condition, we have $$N\ge \binom{6}{2}\left(\frac{2n-r}{5}+1\right).$$ Therefore, $$x_2+3x_3+6x_4+10x_5\ge 6n-3r+15.$$ If $x_5=0,$ then the LHS is clearly less than $6n,$ which is impossible. Hence, $x_5=1,$ so $$x_2+3x_3+6x_4+10\ge 6n-3r+15$$$$\iff 3r-15\ge 6x_0+6x_1+5x_2+3x_3-4$$$$\iff r=4,x_0=x_1=x_2=x_3=0.$$ Thus, $1$ contestant solved five problems (say $2,3,4,5,6$) and $n-1$ contestants solved four problems.
-----
Call the contestants who solved four problems $\emph{average}$ and let $S_{ab}$ with $a<b$ denote the number of average contestants who solved problems $a$ and $b.$ Observe the following:\\\\ (1) Since $\binom{3}{2}$ and $\binom{4}{2}$ are both divisible by $3,$ we have $3\mid S_{ab}$ for all $a,b.$\\\\ (2) By the given condition, $S_{ab}\ge\frac{2n+1}{5}$ if $a=1$ and $S_{ab}\ge\frac{2n-4}{5}$ if $a\ne 1.$\\\\ (3) Since $\sum_{1\le a<b\le 6}S_{ab}=\binom{4}{2}(n-1)=6n-6$ and $5(\frac{2n+1}{5})+10(\frac{2n-4}{5})=6n-7,$ equality is achieved in all but one of the above inequalities.\\\\ Now note that $$\sum_{a=1,2\le b\le 6}S_{ab}\ge 5\left(\frac{2n+1}{5}\right)=2n+1,$$$$\sum_{2\le a<b\le 6}S_{ab}\ge 5\left(\frac{2n-4}{5}\right)=2n-4.$$ Therefore, either $2n+2\equiv 2n-4\equiv 0\pmod{3}$ or $2n+1\equiv 2n-3\pmod{3}.$ Since the latter is clearly impossible, we must have $n\equiv 2\pmod{3}.$ But $$S_{12}+S_{23}+S_{24}+S_{25}+S_{26}\ge \frac{2n+1}{5}+4\left(\frac{2n-4}{5}\right)=2n-3\equiv 1\pmod{3}.$$ Hence, the sum on the LHS is congruent to either $1$ or $2$ modulo $3,$ contradiction.

[i]A different Solution:[/i]

Basically, following is the quick outline of solution:
[list]
[*] Of course, first we assume contrary and by adding solves WLOG assume that $5$ problems were solved by exactly $1$ contestant and other contestants solves $4$ problems each.
[*] Then we look at problems which have $\le \left\lfloor \frac{2n}{3} \right\rfloor$ solves and conclude using them (by double counting) that each pair of problems was solved by exactly $\left\lfloor \frac{2n}{5} \right\rfloor + 1$ students. Moreover we get that $n = 15k-3$ for some $k \in \mathbb{N}$.
[*]  Finally, we just double count the cardinality of set $T := \{(\{P_i,P_j\},C_k): \text{contestant } C_k \text{ solved both the problems } P_i,P_j \}$ in order to get our desired contradiction.
[/list]
[b]Below are the full details:[/b]

Assume contrary. Suppose there were $n$ contestants $C_1,C_2,\dots,C_n$ and $P_1,P_2,\dots,P_6$ were the six problems. By adding in solves, We may assume WLOG that one contestant solved exactly $5$ problems and all other solved exactly $4$ problems. We will call a problem [i]less solved[/i] if it had at most $\left\lfloor \frac{2n}{3} \right\rfloor$ solves. Also, for different problems $p_1,p_2,\dots,p_l$, denote by $f(p_1,p_2,\dots,p_l)$ the number of contestants who solved all the problem $p_1,p_2,\dots,p_l$.

[color=#f00][b]Claim[/b](Key Claim): [/color] For Any less solved problem $p$, $f(p) = \left\lfloor \frac{2n}{3} \right\rfloor$. Also, for any problem $q \ne p$, $f(p,q)= \left\lfloor \frac{2n}{5} \right\rfloor + 1$. Moreover, $n= 15k-3$ for some $k \in \mathbb{N}$.

[i]proof:[/i] Let $f(p) = t$. We bound the value $\sum_{q \ne p} f(p,q)$ in two different ways. Because each contestant (other than one who solved $5$ problems) solved $4$ problems each, so
$$\sum_{q \ne p} f(p,q) \le 3(t-1) + 4 = 3t+1 \le 3 \cdot \left\lfloor \frac{2n}{3} \right\rfloor + 1 \le 2n+1$$
with equality iff $3 \mid n$ and $t = \left\lfloor \frac{2n}{3} \right\rfloor$. \\
Now, since each pair of problems was solved by at least $\left\lfloor \frac{2n}{5} \right\rfloor + 1$ contestants, so
$$\sum_{q \ne p} f(p,q) \ge 5 \cdot \left( \left\lfloor \frac{2n}{5} \right\rfloor + 1 \right) \ge 5 \cdot \frac{2n+1}{5} \ge 2n+1$$
with equality iff $n \equiv 2 \pmod{5}$ and $f(q,p) = \left\lfloor \frac{2n}{5} \right\rfloor + 1 ~ \forall ~ q \ne p$. \\
This implies our claim as equality must hold everywhere.  $\square$

Now, we know that $f(P_i) \ge \left\lfloor \frac{2n}{3} \right\rfloor = 10k-2 ~ \forall ~ i = 1,2,\dots,6$ and $\sum_{i=1}^6 f(P_i) = 60k-11$. It follows that $5$ of the problem were solved by exactly $10k-2$ contestants and the other was solved by $10k-1$ contestants. So there are $5$ less solved problems. So by our claim it follows that $f(P_i,P_j) = \left\lfloor \frac{2n}{5} \right\rfloor + 1 ~ \forall ~ i \ne j$ as at least of the problems $P_i,P_j$ must be less solved. Now consider the set
$$T := \{(\{P_i,P_j\},C_k): \text{contestant } C_k \text{ solved both the problems } P_i,P_j \}$$
If we fix $\{P_i,P_j\}$, then we get
$$|T| = 15 \cdot (6k-1) = 90k - 15$$
On the other hand, if we fix $C_k$, then we get
$$|T| = \binom{5}{2} + (15k-4) \cdot \binom{4}{2} = 90k - 14$$
This gives us a contradiction and hence [b]completes the proof of the problem[/b].

Here's a terrible writeup of a weird solution:

Assume FTSOC that there is at most one person who solved $5$ problems. Let $k$ be a person, and let $a$ and $b$ be problems. We count the number of triples $(k,a,b)$ such that $k$ solved both $a$ and $b$. On one hand, the number of triples is bounded above by $\binom{5}{2}+\binom{4}{2}(n-1)=6n+4$. On the other hand, the number of triples is bounded below by $\binom{6}{2}\frac{2n+1}{5}=6n+3$. Thus, the bound is strong enough that we can deduce some equality cases:
1. The number of people is congruent to $2 \pmod{5}$.
2. One person solved $5$ problems and everyone else solved $4$ problems.
3. One pair of problems was solved by exactly $\frac{2n+6}{5}$ people, and the other pairs were solved by exactly $\frac{2n+1}{5}$.

Let $S$ be a set of $5$ problems. We count the number of triples $(k,a,b)$ such that $a,b \in S$ and $k$ solved $a$ and $b$. Notice that this number must either be $4n+2$ or $4n+3$ by statement 3. Now, suppose $S$ is the set of the five problems that one person solved. Then, we have that $S \equiv 1 \pmod{3}$ by summing the contributions of each person. Now, suppose $S$ is any other set of size $5$. Then, we have that $S \equiv 0 \pmod{3}$ similarly. Thus, $4n+2 \equiv 0 \pmod{3}$, so $n \equiv 1 \pmod{3}$. Therefore, we have that $\frac{2n+1}{5} \equiv 0 \pmod{3}$.

Now, let's count the number of $5$-element sets of problems such that the number of triples is $1 \pmod{3}$. On one hand, we proved that only one set works. On the other hand, the number of solves of each pair of problems is a multiple of $3$ except one pair, so the number of sets is $4$, a contradiction. Thus, we are done.

Case bash

We can assume that WLOG one contestant has solved 5 problems, namely problems 1,2,3,4 and 5; and every other student has solved 4 problems. Now I'll prove that this is impossible. Let $A$ be the number of pairs of problems that need to be solved; and $B$ the number of pairs of problems that the students combined have solved. We need to have $B\geq A$

If $n=5k+1$ we have that $A=15(2k+1)=30k+15$ and $B=10+5k.6=30k+10$, impossible.

If $n=5k+2$ we have that $A=15(2k+1)=30k+15$ and $B=10+(5k+1).6=30k+16$, which is possible(for now).

If $n=5k+3$ we have that $A=15(2k+2)=30k+30$ and $B=10+(5k+2).6=30k+22$, impossible.

If $n=5k+4$ we have that $A=15(2k+2)=30k+30$ and $B=10+(5k+3).6=30k+28$, impossible.

If $n=5k+5$ we have that $A=15(2k+3)=30k+45$ and $B=10+(5k+4).6=30k+34$, impossible.

So we got that [b]$n=5k+2$[/b]. Now let's check the possibilities mod 3.

If [b]$n=15k+2$[/b] we have that the total number of problems solved is $5+4(15k+1)=60k+9$, thus one problem has been solved by at most $10k+1$ students. This problem is in $5$ problem pairs, which need to be solved at least $5(6k+1)=30k+5$ times, but these problems pair are solved at most $4+3.10k=30k+4$ times by watching all the students who solved this problem, impossible.

If [b]$n=15k+7$[/b] we have that the total number of problems solved is $5+4(15k+6)=60k+29$, thus one problem has been solved by at most $10k+4$ students. This problem is in $5$ problem pairs, which need to be solved at least $5(6k+3)=30k+15$ times, but these problems pair are solved at most $4+3.(10k+3)=30k+13$ times by watching all the students who solved this least solved problem, impossible.

Now the hardest case, if  [b]$n=15k+12$[/b]. Problem $6$ is in $5$ problem pairs and each of these pairs is solved by at least$\frac{2}{5} n= 6k+5$ students, thus these $5$ problem pairs need to be solved in total at least $30k+25$ times. Only students with $4$ problems solved have done problem $6$, thus one student can cover at most $3$ of those $30k+25$ problem pairs, i.e we need $10k+9$ students to have solved problem 6. But we see that in the case $n=5k+2$ we have $B-A$ is at most $1$, i.e we could have at most one pair of problems solved more than enough times. But the $10k+9$ students that have solved problem $6$ cover the $5$ problem pairs with problem $6$ $30k+27$ times, but they need to be covered only $30k+25$ times, i.e there are two extra pairs of problems solved, which we can't happen, so there is no solution in this case as well and we get a contradiction!

Is this right?

Suppose we have $n$ students, and at most one of them solved (exactly) $5$ problems. We count the number of ways we can assign any student to two problems that they solved. On one hand, counting by students, this quantity is at most $\tbinom{5}{2}+\tbinom{4}{2}(n-1)=6n+4$. Suppose that $n \not \equiv 2 \pmod{5}$, and count the quantity by pairs of problems. Since $\lceil \tfrac{2n}{5} \rceil \geq \tfrac{2n+2}{5}$ in this scenario, it follows that the desired quantity is at least $\tbinom{6}{2}\tfrac{2n+2}{5}=6n+6$: contradiction. Hence $n \equiv 2 \pmod{5}$, so let $n=5a+2$.
In this case, the desired quantity is at least $\tbinom{6}{2}\tfrac{2n+1}{5}=6n+3$, so it must be in $\{6n+3,6n+4\}$. However, note that
[list]
[*] There must be at least one student who solved exactly $5$ problems, else the quantity is at most $6n$, so there is exactly one student who solved exactly $5$ problems.
[*] If at least one student solved less than $4$ problems, the quantity is at most $\tbinom{5}{2}+\tbinom{4}{2}(n-2)+\tbinom{3}{2}=6n+1$, which is impossible,
[/list]
hence we need exactly $n-1$ students who solved exactly $4$ problems and a single student who solved exactly $5$ problems. This means that the only possibility is for the quantity to equal $6n+4$. As such, it also follows that there is exactly one special pair of problems $P$ such that $\tfrac{2n+1}{5}+1=2a+2$ students solved it, and every other pair of problems is solved by exactly $2a+1$ students.
WLOG, number the problems $1,\ldots,6$, and assume that the student who solved $5$ problems solved $\{1,2,3,4,5\}$. The idea is to count the number of students who solved exactly four problems, with a fixed arbitrary problem $i \in \{1,2,3,4,5\}$ being one of them. Since our special pair $P$ contains at least one member of $\{1,2,3,4,5\}$, WLOG assume that $1 \in P$. Further assume that either $2 \in P$ or $6 \in P$ (that is, either $P=\{1,2\}$ or $P=\{1,6\}$), which by symmetry covers every possible case.
Let $i=1$, we consider the pairs $\{1,2\},\ldots,\{1,6\}$. There are $4(2a+1)+(2a+2)=10a+6$ student-problem pair assignments in this case, counting over pairs. Since the student who solved $\{1,2,3,4,5\}$ accounts for $4$ of these, there are $10a+2$ assignments for students who solved $4$ problems. Since every such student contributes to exactly $3$ assignments, it follows that there are exactly $\tfrac{10a+2}{3}$ students who solved exactly $4$ problems, problem $1$ being one of them. In particular, this expression must be an integer. However, repeating the same process with $i=3$, we find that there are also exactly $\tfrac{10a+1}{3}$ students who solved exactly $4$ problems, problem $3$ being one of them, so $\tfrac{10a+1}{3}$ must be an integer. But this implies $\tfrac{1}{3}$ is an integer as well, which is absurd. It follows that our initial supposition cannot possibly hold, so we are done. $\blacksquare$

Suppose that there are $n$ contestants, and let contestant $i$ solve $a_i$ problems. Double counting pairs $(c, \{i, j\})$ where $\{i, j\}$ is a pair of problems solved by contestant $c$, we have the inequality $$\sum_{i=1}^n {a_i \choose 2} \geq \left \lceil \frac 25 n \right \rceil {6 \choose 2}.$$ If $n \not \equiv 2 \pmod 5$, the RHS is of the form $6n + c$ for some $c \geq 5$, which implies that there must exist at least two $a_i \geq 5$ on the left. If $n \equiv 2 \pmod 5$, then we must have $6n+3$ or $6n+4$ pairs of solves. Notice that if we have $6n+3$, as ${4 \choose 2} - {2 \choose 2} = 5$ and ${4 \choose 2} - {3 \choose 2} = 3$, some combination of $3$ and $5$ must add up to $1$, which is obviously absurd.

Proving that $6n+4$ solves fails is by far the most difficult part of the problem. Set $n = 5a+2$, and notice that each pair of the problems must be solved by $2a+1$ contestants, apart from one pair which is solved by $2a+2$.

Double count pairs $(C, \{k, i\})$ where $C$ is a contestant and $k$ is the index of the problem which was not solved by the person who solved five problems. Fixing $\{k, i\}$, there are either $2a+1$ or $2a+2$ pairs, and fixing $C$, the number of pairs is $3$ times the number of contestants who solved $C$, which is in particular a multiple of $3$.

Similarly, double counting pairs $(C, \{k, i\})$ as above but where $k$ is an index that was solved by the person who solved five problems and also not one of the two problems in the larger pair, we may fix $\{k, i\}$ again to get $2a+1$ pairs, but upon fixing $C$, there are $3$ times the number of contestants who solved $C$ plus one pairs because of the extra person. This implies that $3 \mid a$, which contradicts our earlier condition. $\blacksquare$

We will double count the number of solve pairs in total, by contestant and by pair of problems. Let the number of contestants be $n$.

[b]Claim.[/b] There exists at least one contestant that solved exactly $5$ problems.
[b]Proof.[/b] Assume otherwise. Then the number of solve pairs in total is at most $\binom42 \cdot n=6n$. But the number of solve pairs in total is strictly greater than $15\cdot\left(\frac25 n\right)=6n$, contradiction. $\blacksquare$

Now assume FTSOC that there is exactly one contestant that solved exactly $5$ problems. Call that contestant [i]the orz contestant[/i].

[b]Claim.[/b] $n\equiv 2\pmod 5$.
[b]Proof.[/b] Simply note how the number of solve pairs in total is at most $6n+4$, but is at least $15\left(\left\lfloor\frac25 n\right\rfloor+1\right)$. Caseworking on $n$ mod $5$ suffices. $\blacksquare$

Now let $n=5k+2$. Then each pair of problems has been solved by at least $2k+1$ contestants. Also note that $15\left(\left\lfloor\frac25 n\right\rfloor+1\right)=6n+3$, so the number of solve pairs has to be $6n+3$ or $6n+4$, so each contestant besides the orz contestant solved $4$ problems. Now assume WLOG that the orz contestant solved problems $1,2,3,4,5$.

Call $P$ the set of problem pairs that don't contain problem $1$, and $Q$ the problem pairs that do contain problem $1$. Also, let $p$ be the number of pair solves with pairs in $P$ and define $q$ similarly. Note that $|P|=2|Q|$, so $p-2q\in\{1,-2\}$. However, this difference starts at $\binom42-2\cdot 4=-2$ from the orz contestant, and either decreases by $3$ or increases by $6$ from the other contestants. Therefore, $n-1$ cannot be $1$ mod $3$, so $n$ cannot be $2$ mod $3$, so $3\nmid k$.

Now consider the number of solves pairs involving problem $6$. Each of them must have $2k+1$ or $2k+2$, and their total must be $10k+5$ or $10k+6$. However, since these can only be satisfied by other contestants, they come in triples, so one of these is a multiple of $3$. Since $3\nmid k$, $3\mid 10k+5$, so $k\equiv 1\pmod 3$ so $n\equiv 1\pmod 3$ and each solve pair involving problem $6$ got $2k+1$.

Therefore, some other solve pair got $2k+2$. Assume WLOG this was problems $4$ and $5$. Since $3\mid n-1$, $p-2q$ must be $-2$ mod $9$, so it must be $-2$. But the extra pair does not have $1$ in it, contradiction. $\blacksquare$

Omg jatloe.

Anyways,
Let $n$ be the number of contestants.
Let $S(i, j)$ for $1 \le i < j \le 6$ denote the total number of contestants who solved both problems $i$ and $j$.

[b][color=pink]Claim:[/color][/b] WLOG we can assume that everyone either solved $4$ or $5$ problems.
[i]Proof.[/i] A counterexample to the claim with some contestant having solved less than $4$ problems remains a counterexample with additionally dummy solves tacked on. $\blacksquare$

[b][color=pink]Claim:[/color][/b] At least one contestant must have solved exactly $5$ problems.
[i]Proof.[/i] Assume not.
However, then \[ \sum_{1 \le i < j \le 6} \frac{S(i, j)}{n} = \frac{6}{15}. \] Since $\frac{S(i, j)}{n} > \frac25$ for all $i$ and $j$, this is a contradiction. $\blacksquare$
Now suppose that only one contestant solved $5$ problems.

[b][color=pink]Claim:[/color][/b] If $n \not\equiv 2 \pmod{5}$ contradiction immediately follows.
[i]Proof.[/i] As such, it follows that \[ \sum_{1 \le i < j \le 6} \frac{S(i, j)}{n} = \frac{6}{15} + \frac{4}{n}. \]
Then, it follows from $S(i, j) \ge \left\lceil \frac25 n \right\rceil$ that this can only hold if $n \equiv 2 \pmod{5}$, or else contradiction follows since the LHS is too large. $\blacksquare$
The case of $n = 5k + 2$ can thus only hold if some special $S(a, b) = 2k + 2$ while the rest are $2k + 1$.
WLOG let the one contestant have solved problems $1$ through $5$. It then follows that \[ S(1, 6) + S(2, 6) + S(3, 6) + S(4, 6) + S(5, 6) \] which is either $10k + 5$ or $10k + 6$ is $3$ times the number of contestants who solved $6$.
However, it follows similarily for $1 \le i \le 5$ that \[ \sum_{1 \le j \le 6, j \ne i} S(i, j) - 1 \] which is either $10k + 4$ or $10k + 5$ is $3$ times the number of contestants who solved $1$. This implies that the expression is $10k + 5$ independent of $i$, however only $S(a, b) = 2k + 2$, which can't occur in all of the expressions, contradiction.

Claim: At least 1 contestant solved 5 problems.
Proof: Suppose otherwise, let us double count the number of triplets of the form $(a_i, a_j, s_k)$, where student $s_k$ solved distinct problems $a_i, a_j$
Additionally, we may assume that all students solved at least 4 problems: if not, simply consider the case where a student who solved less than 4 problems solves an additional one: the conditions would still hold.

Note that we require strictly more than $15 \cdot \frac{2n}{5}=6n$ such triplets, but we have at most $\binom{4}{2} \cdot n=6n$ such triplets since each student contributes at most 6. This is a contradiction.

Next, we show that contradiction also occurs if exactly one student solved 5 problems.
In this case, we have at most $6n-\binom{4}{2}+\binom{5}{2}=6n+4$ such triplets.
Now, note that each pair of problems must admit at least
$\frac{2n+1}{5}$ triplets; hence $6n+3$ triplets are required.

Additionally, note if our bound is $\frac{2n+2}{5}$ or higher, contradiction occurs. In particular, we must have that $n \equiv 2 \pmod 5$
Then, let $n=5x+2$

We now have a maximum possible of $30x+16$ triplets, with each pair of problems corresponding to at least $2x+1$
Let $p_i$ equal the number of such triplets containing the problem $i$, and $q_{a,b}$ be the number of such triplets containing problems $a,b$
Then, we have $p_i \geq 4 \cdot (2x+1) = 8x+4$ for $i=1,2 \dots 6$

Additionally, WLOG let the contestant who solved 5 problems solve $1,2,3,4,5$
Then note that $p_1 = 4 + 3 k_1$, where $k_1$ is the number of contestants who solved exactly 4 problems, including 1.
In particular, if $x$ is not a multiple of 3, we need $k_1 > \frac{8x}{3}$.

This is also true for $k_2, \dots k_5$, hence the minimum possible total number of triplets required is $(2x+1) \cdot 15 + \frac{1}{3} \cdot 5 > 30k+16$, which is a contradiction. (informally put, a wastage of $\frac{5}{3}$)

Hence, we must have $3 | x$.

Now note that $p_6 = 3k_6 \geq 8x+4$

Hence, $k_6 \geq \frac{8x}{3} +2$ (informally put, a wastage of 2)
This implies that we need at least $(2x+1) \cdot 15 + 2 > 30k+16$ triplets, contradiction again.
Hence we need at least 2 contestants with 5 solves, and we are done.

Kinda long solution had to take some hints to deal with the $n\equiv 2 \pmod{5}$ case.

We simply double count the number of pairs $(P_1,P_2,c)$ where $P_1,P_2$ is a pair of problems solved by contestant $c$.
Then, if there are $f$ students who solved 5 problems, note that,
\[\binom{5}{2}f + \binom{4}{2}(n-f) \geq |(P_1,P_2,c)| \geq \binom{6}{2}\lceil{\frac{2n}{5}}\rceil\]
One can do case work $\pmod{5}$ to check that this requires $f\geq 2 $ for all $n\neq 2 \pmod{5}$ and $f\geq 1$ for $n\equiv 2 \pmod{5}$. This is the case we have to check now.\\

By way of contradiction, assume there exists only one student who solved 5 problems. WLOG, we assume that the student who solved five problems solved problems $1,2,3,4,5$. All other students have solved at most 4 problems each. Returning to the above double count by letting $n=5k+2$ we note that,
\[30k+16 \geq |(P_1,P_2,c)| \geq 30k+15\]
if there exists atleast one student who solved only 3 problems, then the LHS becomes at most
\[\binom{5}{2}+\binom{4}{2}(5k)+\binom{3}{2}= 30k + 13 < 30k+15\]
Thus, all other students except the one who solved 5 problems must have solved 4 problems each. This gives us that
\[|(P_1,P_2,c)| = 10 + 6(2k+1)=30k+16\]
Now, looking at the other side of the bound, we see that each pair of problems must have at most $2k+2$ solves each. Further, we cannot have 2 or more pairs of problems which had $2k+2$ solves, the left hand side becomes atleast
\[13(2k+1) +2(2k+2)= 30k +17 > 30k+16\]
Thus, there exists at most one pair of problems which had $2k+2$ solves. Since we already know that $|(P_1,P_2,c)|=30k+16$ this implies that we must have exactly one pair of problems which had $2k+2$ solves.\\

Now, consider this pair of problems which had $2k+2$ solves. Then, WLOG, the only possibilities are that $(P_1,P_2)=(1,2)$ or $(P_1,P_2)=(1,6)$ (other cases are symmetric as the student who solved 5 problems solved $1,2,3,4,5$). We check each of these separately.\\

Assume that the pair $(1,6)$ had $2k+2$ solves. We count the number of students who solved atleast one of the pairs $(1,2),(1,3),(1,4),(1,5)$ and $(1,6)$. On one hand, with multiplicities we know that this value is,
\[S=4(2k+1)+(2k+2)= 10k+6\]
Clearly the student who solved 5 problems solved all of these pairs and thus, contributes 4 (he has not solved the pair $(1,6)$) to this sum. Every student who solved 4 problems, contributes exactly 3 (if they have solved problem 1 and 3 other problems) or 0 (if they have not solved problem 1) to this sum. The number of students who solved atleast one of these pairs and did not solve 5 problems is
\[\frac{10k+6-4}{3} = \frac{10k+2}{3} \in \mathbb{Z}\]
Now, we count the number of students who solved atleast one of the pairs $(3,1),(3,2),(3,4),(3,5)$ and $(3,6)$. As before, counting with multiplicities this number is
\[S= 5(2k+1)=10k+5\]
The student who solved 5 problems, contributes exactly 4 to this sum (he has not solved the pair $(3,6)$) and every other student contributes either 3 (if they have solved problem 3) or 0 (if they have not solved problem 3). Thus, the number of students who solved a total of 4 problems, and at least one of the pairs in this set is,
\[\frac{10k+5-4}{3} = \frac{10k+1}{3} \in \mathbb{Z}\]
which is a clear contradiction.\\

Now, assume that the pair $(1,2)$ had exactly $2k+2$ solves. Then as before, we count the number of students who solved at least one of the pairs $(1,2),(1,3),(1,4),(1,5)$ and $(1,6)$. With multiplicities this is
\[4(2k+1)+2k+2 = 10k+6\]
as before we obtain that,
\[\frac{10k+2}{3} \in \mathbb{Z}\]
Then we count the number of students who solved atleast one of the pairs $(3,1),(3,2),(3,4),(3,5)$ and $(3,6)$. As before, we obtain that,
\[\frac{10k+1}{3} \in \mathbb{Z}\]
which is also a contradiction. Thus, both these possibilities are impossible which implies that there exists atleast 2 students who solved atleast 5 problems as desired.


[quote="Xantos C. Guin"]$x^{x^{x^{x}}}...=2$
$x^{2}=2$
Since $x>0$
$x=\sqrt{2}$[/quote]
Thats what i got. :)

[hide]Noting some infinity, we

get $x^{2}=2$

So $x=\sqrt{2}$[/hide]

Now solve this:
$x^{x^{x^{x^{\vdots}}}}=4$

[hide]
Remember that if $x=\sqrt{2}$:
$x^{x^{x^{x^{\vdots}}}}=2\neq4$
[/hide]

[hide] There is no solution because anything greater than 1 that is raised to the power of a number greater than 1 an infinite number of times cannot be equal to 2 or 4.[/hide]

[hide="Conjecture"]$x^{x^{x^{x^{\vdots}}}}=a$, for some positive real $a$, has a solution iff $a < e$. [/hide]

Find the maximum value of $f(a)$ if $f(a)=x$ when $x^{x^{...}}=a$.  :D

Using the same method,
$x^{a}=a$
$x=\sqrt[a]a$
$f(a)=\sqrt[a]a$

I used calculus, but I don't think calculus is allowed in this forum :maybe: ...

[hide="Calculus method"]$ln f(a) = \frac{1}{a}ln a$
$(f'(a))(\frac{1}{f(a)})=\frac{1}{a^{2}}-\frac{ln a}{a^{2}}$
$f'(a) = \frac{(1-ln a)(\sqrt[a]a)}{a^{2}}$
To find the maximum, let $f'(a)=0$:
$f'(a)=0$
$1-ln a=0$
$ln a=1$
$a=e$

[b]So the maximum occurs when a=e.[/b]
[/hide]

[quote="vishalarul"]Is there a way to compute the maximum value of $f(a)$ if $f(a)=x$ when $x^{x^{...}}$=$a$ without using calculus? :maybe:[/quote]

I'm not sure, but $a^{\frac{1}{a}}$ reminds me of $(1+\frac{1}{a})^{a}$.


calculus
derivative
function
symmetry
calculus computations

Note: no one is locking your topics. What I'm doing is moving them to the forum that is most appropriate for them. This sort of material belongs in "Calculus Computations and Tutorials."

[quote="symmetry"]Find the derivative using the quotient rule for both questions.

1) y = (x^2 + 4x + 3)/sqrt{x}

2) y = (3t - 7)/(t^2 + 5t - 4)[/quote]

Please learn how to use Latex. It will be easier for us to read.

Do you mean...

1) $y=\dfrac{x^2+4x+3}{\sqrt{x}}$

2) $y=\dfrac{3t-7}{t^2+5t-4}$

What are the steps for me to solve these questions?

Ok the quotient rule states that if you have a function $f(x) = \dfrac{u(x)}{v(x)}$ then $f'(x) = \dfrac{u'(x)v(x)-v'(x)u(x)}{v^2(x)}$, so for the fist one:

$u(x) = x^2+4x+3 \Rightarrow u'(x) = 2x+4$ and $v(x) = \sqrt{x} \Rightarrow v'(x) = \dfrac{1}{2\sqrt{x}}$

Now just plug these into the above equation.

Just out of curiosity, what are you getting certified for?

Thank you all for your help.

To Jimmy:

I am getting certified for a state job that requires a lot of math to pass the test but no math to do the job.  Like a lot of American jobs.  Take the law entrance test, for instance.  The exam has absolutely NOTHING to do with law school; it's just another test, another block or hurdle to make money of test takers.  They call it a fair society.  HA! HA !

symmetry


$ x \plus{} y \equal{} \frac {8 \pi}{9}$
$ \frac {\sin x}{\sin y} \equal{} 2 \cos \frac {2 \pi}{9}$

how to solve something like that?

hello, plugging $ y\equal{}\frac{8}{9}\pi\minus{}x$ in your second equation we get
$ \frac{\sin(x)}{\sin\left(\frac{8}{9}\pi\minus{}x\right)}\equal{}2\cos\left(\frac{2}{9}\pi\right)$
from here we have
$ \frac{1}{2\cos\left(\frac{2}{9}\pi\right)}\equal{}\frac{\sin\left(\frac{8}{9}\pi\minus{}x\right)}{\sin(x)}$
using the addition formulas we get
$ \frac{1}{2\cos\left(\frac{2}{9}\pi\right)}\equal{}\frac{\sin\left(\frac{8}{9}\pi\right)\cos(x)\minus{}\sin(x)\cos\left(\frac{8}{9}\right)}{\sin(x)}$
$ \frac{1}{2\cos\left(\frac{2}{9}\pi\right)}\plus{}\cos\left(\frac{8}{9}\pi\right)\equal{}\sin\left(\frac{8}{9}\pi\right)\cot(x)$
and from here we have
$ \tan(x)\equal{}\frac{2\cos\left(\frac{2}{9}\pi\right)\sin\left(\frac{8}{9}\pi\right)}{1\plus{}2\cos\left(\frac{8}{9}\pi\right)\cos\left(\frac{2}{9}\pi\right)}$
Sonnhard.

thanks, actually i hoped for a result $ x\equal{} \alpha \cdot \pi$

hello, sorry, but you can not obtaine this result.
Sonnhard.

Sonnhard, suddenly the ability to plug things into computer algebra systems fails you?  I'm disappointed!  Mathematica could have given you right away that $ x \equal{} \frac {13\pi}{18}$ is a solution, for example.

I haven't figured out how to derive this yet.  But, a good idea is to note that $ \frac {8\pi}{9}$ is a special number because its cosine and sine satisfy some reasonably simple algebraic equations -- I suggest playing around with double-angle identities and expressions like $ \sin t \equal{} \sin \pi \minus{} t$ and so on, writing everything in terms of the sine and cosine of $ \frac {n\pi}{9}$ for some well-chosen integer $ n$, for example.  Also, probably at some point you're going to need to square everything in order to get a half-angle involved.

Edit: of course, it's easy to check that the value from my first paragraph is correct; the question is how you can find it without already knowing it.

[hide="Solution"]
I think this works :
 $ x \equal{} \frac {8\pi}{9} \minus{} y$
$ \sin(x) \equal{} \sin (\frac {8\pi}{9} \minus{} y) \equal{} \sin(\frac {\pi}{9} \plus{} y) \equal{} \sin(\frac {\pi}{9})\cos(y) \plus{} \cos(\frac {\pi}{9})\sin(y)$
So, $ \frac {\sin(x)}{\sin(y)} \equal{} \sin(\frac {\pi}{9})\cot(y) \plus{} \cos(\frac {\pi}{9}) \equal{} 2\cos(\frac {2\pi}{9})$
So, $ 2\cos(\frac {\pi}{3} \minus{} \frac {\pi}{9}) \equal{} \cos(\frac {\pi}{9}) \plus{} 2\sin(\frac {\pi}{3})\sin(\frac {\pi}{9})$
$ 2\sin(\frac {\pi}{3})\sin(\frac {\pi}{9}) \equal{} \sin(\frac {\pi}{9})\cot(y)$
It now follows that $ y \equal{} \frac {\pi}{6}, \frac {7\pi}{6}$ and $ x \equal{} \frac {13\pi}{18}, \minus{} \frac {5\pi}{18}$
Where the first and second solution correspond
[/hide]


AMC
AIME
USA(J)MO
USAMO
MATHCOUNTS
number theory
AMC 10

I just wanted everyone to know that whenver we post a question on this forum, we want to encourage (hopefully, mathfanatic concurs) different ways of thinking. Thus, we hope that you will post your own, unique solutions to problems. WE want to see different ways of thinking, no matter how different, weird, or long it might appear. THus, if you have a different solution than one that has already been posted, please, by all means, post it. I am interested in new methods that I might not have thought about.

And by the way, I have a couple of number theory questions that I garnered up over the summer, which I plan on posting soon. Hopefully, no one has any problems? Number theory is extremely important on the AIME.

If someone doesn't like a problem, they don't have to answer it.  Simple.

Feel free to post whatever problems you like, darkquantum.

P.S. I'm going to combine most of the announcements into one thread (with the exception of the "News" one and the "Math Candy" one).  This way, we won't have about 5 announcements cluttering up the top.

--Cut from "Naming/Tiles"--

I have renamed the AMC Challenges as follows:

Easy AMC problems are "Easy AMC #X"
AMC problems are "AMC Challenge #X"
AIME problems are "AIME Challenge #X"
USAMO problems are "USAMO Challenge #X"
MOP/TST problems are "MOP Challenge #X"
Other olympiad problems are "Olympiad Challenge #X"

Additionally, the last group of problems might be posted in the "Advanced Topics" section.

I plan to post a number of problems each week. Not all problems will be from the AMC, AIME, USAMO, TST, etc. tests; I'll try to use problems from other countries that are comparable in difficulty.

This post will stay an announcement for one week. After that, I'll switch it back to a regular post.

One more thing: don't answer problems that are far below your skill level. Leave them for more beginning solvers. As the AMC series of competitions spans a wide range of levels, problems posted in this section will vary in difficulty.

[Edit] Note that the naming system is now somewhat random.  Oh well.  Darkquantum and I will continue to post difficult problems from various sources to help you prepare for the AMC, though.

--Cut from "Difficulty" Sticky by darkquantum--

Feel free to request new problems of varying difficulty, meaning you want more AMC level, AIME level, or -MO level problems. Also feel free to pm me or mathfanatic (at least i think he concurs.)

--Cut from "Difficulty" Sticky response by mathfanatic--

I concur. And I will post some new problems in a little. Maybe some easier ones, since there are still some hard ones out there...

Feel free to PM me to request problems, if you just want to talk, or if you're a girl looking for a date.  :D  Just kidding on the last one, but maybe some miracle will happen...  :wink:

{Note} I have placed all these announcements in one thread to simplify things and get rid of the clutter at the top of the AMC board.

I am wondering, is there anyone out there who wants to see easier problems put up, meaning problems around AMC 10 level?

If so, please post a reply here. If there are people out there who want easier problems, then i'll tell the smarter guys not to sovle those problems, ya kno, leave it towards the less developed guys...

I'm "less developed" so I would like more easier questions. (not more easier, but more number of easier questions)
Also, I know I'm going to sound stupid, but can you post hard AMC 8 questions also?

[color=cyan]I think I have some old questions I gave to freshmen last year . . . should be more of an AMC-8 level.  In general, though, problems of that difficulty will probably be more likely to appear in the Mathcounts forum.  Anyhow, I'll see what I can do.[/color]

hmm, i think i might have a couple of the easier quesitons Joel gave out over the summer, let me see if i can dig them up from the pigstuy i call my room...

Ok, guys.
Just posted a bunch of easier questions

Have fun

I have destickied this, since it's mainly common sense, obsolete (i.e. the nomenclature system), or cluttering up the top of the board (right now, when you open the page, you cannot see the new topics - you have to scroll down since the announcements and stickies take up the whole page).


algebra
polynomial
superior algebra
superior algebra unsolved

Let $ T : \mathbb{A}^2\to\mathbb{A}^2$ be a polynomial map. $ T(Q)\equal{}P$.

a. Show that $ m_Q(F^T)\geq m_P(F)$.

b. Let $ J_QT\equal{}\left(\frac{\partial T_i}{\partial X_j}\right)(Q)$ to be the Jacobian hyperplane to $ F$ at $ P$.

c. Show that the converse of $ (b)$ is not correct. Let $ T\equal{}(X^2,Y), F\equal{}Y\minus{}X^2, P\equal{}Q\equal{}(0,0)$.

Thanks in Advance.

I'll bite:
1. What is $ F$?
2. What does (b) ask for?


Squares just work better. The center associated with squared distances is the mean, while the center that goes with distances is the median. That's not too bad on its own... but what if you want to work with more than one dimension? What is the "median" of several points in $ \mathbb{R}^2$? With squared distances, we can simply find a mean one dimension at a time.
Then you have least-squares regression, additivity of variances, and many other useful methods.

[quote="jli"]my teacher said that we take the sum of the square of the differences to find the standard of deviation to ensure that the result is positive.  why not just use absolute values??[/quote]
Is it a (n-1)variance? I don't think it's S.D since I'm learning Statistics and this is in the chapter I already covered through. :P S.D is when you take the sum above, then divided into (n-1)(assume it has n data) and take square root of that ratio to get S.D.
PS: We can also find the maximum of the S.D if we are given the number of integers and find the maximum of k integers we choose from this set(for example, given 10 integers, choose 5 that has the maximum S.D!) I think it's a very great problem(and hard, of course)if we solve by Mathematics argument , but it's "sucked" when we solve by Statistics argument :wink:

the good things to work with a square is that $ x \mapsto x^2$ is smooth, but $ x \mapsto |x|$ is not !
Suppose that you have some data $ y_1, y_2, \ldots, y_n$. Can you find $ m$ such that $ \sum_1^n |y_i \minus{} m|^2$ is minimal. Is the minimum achieved at unique point ? and now, if you try to minimize $ \sum_1^n |y_i \minus{} m|$, is it still unique ?


combinatorial geometry
advanced fields
advanced fields unsolved

Consider a convex body $C$ in $\mathbb{R}^n$. Any intersection of with a half-space that has volume $\epsilon$ is called an $\epsilon-$cap. Let $\epsilon$-wet part be the union of all the $\epsilon$-cap, and the $\epsilon$- floating body be the remaining part.
 Now let $x$ and $y$ be in the wet part. We say that $x$ sees $y$ if  the segment $xy$ does not cross the floating body.
 Prove that the set $S_x$ of all $y's$ that $x$ sees is the union of all $\epsilon$-cap that contain $x$

This is false even in $\mathbb R^2$. Let $C$ be the convex hull of the points
$(-1000,0)$, $(0,1)$, $(1,1)$, $(1,-1)$ and $(0,-1)$. Let $\varepsilon$ be just slightly less than $2$. Then the entire interval between $x=(0,-1)$ and $y=(0,1)$ is wet (the lower half is contained in the $\varepsilon$-cap defined by the half-plane $\{x=(x_1,x_2)\,: \,x_2\leqslant x_1\}$ and the upper half is contained in the symmetric cap. But it is easy to see that there is no $\varepsilon$-cap containing $x$ and $y$ simultaneously.


Prove that for all $a,b,c\in\mathbb{R}^+$,
\[ \frac{1}{a^3+b^3+abc}+\frac{1}{b^3+c^3+abc}+\frac{1}{c^3+a^3+abc}\le\frac{1}{abc} \]

Masoud Zargar

[hide]
$\sum \frac{abc}{a^3+b^3+abc} \le \sum \frac{c}{a+b+c} = 1$

from

$ab(a+b) \le a^3+b^3$
$ab(a+b+c) \le a^3+b^3+abc$
$abc(a+b+c) \le c(a^3+b^3+abc)$[/hide]

[quote="blahblahblah"]Next time, use the search button.  This is one of the more well-known olympiad problems.[/quote]
I already know how to solve it, however, I didn't know it was posted many times.

Please take a look my solution. :)
[url]http://www.mathlinks.ro/Forum/viewtopic.php?p=324637#p324637[/url]


Does anyone know how to prove that:

for p an odd prime congruent to 1mod4, that p=x^2+y^2 for some integers x,y.

Cheers

Dave

Yes, this is a fairly well-known result :)
You can see, for example, this post :
http://www.mathlinks.ro/Forum/viewtopic.php?t=19869

EDIT : ZetaX beats me to it! ;)


A triangle $ABC$ with exradii $r_a, r_b, r_c$ , circumradious $R$ and inradious $r$ has area $S=1$.

Prove that $(r+r_a)(4R+r)+(r_b+r_c)^2-r_{b}r_{c}+r^2\geq10$  !!

 :)

Use 4R = r_a + r_b + r_c - r.
--

$\displaystyle (r+r_a)(4R+r)+(r_b+r_c)^2-r_{b}r_{c}+r^2\geq10$

is $\sum r_a^2 + \sum r_ar_b + r^2 + r\sum r_a \ge 10$.

Now, we know $r_a = S / (s-a) = 1/s-a$.  Put $a = y+z$, etc. (standard trick) and now $r_a = 1/x$.  Also, $sr = 1 \Rightarrow r = \frac{1}{x+y+z}$.

Finally, amgm the whole lot.  We are left to show that $\prod r^5r_a^5r_b^5r_c^5 \ge 1$, that is, $rr_ar_br_c \ge 1$.

But $r r_a r_b r_c = \frac{1}{xyz(x+y+z)} = \frac{1}{S} = 1$.


To proof,that there are [b]no[/b] natural numbers [b]a[/b] and [b]b[/b] ,such that the number:
a) $ (36a \plus{} b)(36b \plus{} a) \equal{} 2^n$
b) $ (46a \plus{} b)(46b \plus{} a) \equal{} 2^n$

Each expression in parenthesis must be equal to a power of 2. Other than that I got nothing.. I think it should be in the High School topics.

[quote="AIME15"]Should the second one be $ 2^m$?  Obviously they cannot be the same power of $ 2$.[/quote]

I don't think a change of variables is necessary because (a) and (b) are different problems, not a system of equations.

As Modularmarc101 pointed out, each expression must be a power of two. Thus, let $ 36a\plus{}b \equal{} 2^x$, and $ a\plus{}36b \equal{} 2^y$, and assume WLOG that $ x$ is greater than or equal to $ y$.  Also, note that $ x$ and $ y$ are both nonzero, since $ a$ and $ b$ are greater than or equal to 1. Adding the equations (to make things nice and symmetric), we have
$ 37a\plus{}37b\equal{}37(a\plus{}b)\equal{}2^x\plus{}2^y\equal{}(2^{x\minus{}y}\plus{}1)(2^y)$

Since $ 2^y$ does not divide 37, $ 2^y$ divides $ (a\plus{}b)$, which means that  $ (a\plus{}b)$ is greater than or equal to $ 2^y$, which contradicts out second (starting equation).

Someone please verify this.

If this is correct, i think that part (b) can be solved the same way.

What if a+b=something like 6? You could make the case that 2^y isn't a+b but 1/3(a+b)

That would mean that $ a\plus{}b$ is greater than $ 2^y$, which as mathking123 said, it contradicts our starting equation.

I don't know if this is right, but

$ a\equal{}b\equal{}0 (mod2)$

So there we can have $ a_1\equal{}\frac{a}{2}$ and $ b_2\equal{}\frac{b}{2}$. $ a_2$ and $ b_2$ are also natural numbers.

so $ (72a_1\plus{}2b_1)(72b_1\plus{}2a_1)\equal{}2^n$
$ (36a_1\plus{}b_1)(36a_1\plus{}b_1)\equal{}2^{n\minus{}2}$

but that would mean there also exist $ a_2\equal{}\frac{a_1}{2}$ and $ b_2\equal{}\frac{b_1}{2}$, and similarly $ a3$,$ a4$$ ...$ that are natural numbers.

So $ a,b$ would be infinitely large?

That's probably an infinite ascent type of thing  :P

I'd guess you can also do this by considering the largest power of $ 2$ that divides $ a, b$, and then dividing by a power of $ 2$ to get odd numbers.


For which integer values for $ n$ does $ n^{34}\minus{}9$ equal a prime?

factor : $ (n^{17}\plus{}3)(n^{17}\minus{}3)$

since its prime, one must be 1 and the other must be a prime number.

$ n^{17}\minus{}3\equal{}1, n^{17}\equal{}4$

um i dont think there exists an integer solution.


Small problem :

[color=blue]Problem[/color].Let $\l$ be a line and $A,B$ be two point in its plane ,but not on the $\l$.

Find the point $X$ ,on the line $L$ such that $AX+BX$ takes its minimum possible value.

i think i had this on my mga4u test before.

This is pretty easy, though if you haven't seen it before, it's a worthwhile exercise to play around with.

My guess ( and I really should prove it, I will later ):

[hide]

Draw segment AB. Find the midpoint M. Find the altitude from M to l, and where the altitude meets, call that point X.

Dunno, now i'll prove it.[/hide]

[hide="Hint"]
First consider the case where A and B are on opposite sides of the line.  Then extend to A and B being on the same side of the line.
[/hide]


I've always thought that languages are interesting, and i'm curious what AoPSers speak.

I'm assuming that by foreign you mean not from the USA? :wink:

Some people are going to get rather annoyed with you, and the USA in general.

Yo no hablo espanol.
Je ne parle pas francais.
Ich nicht spreche Deutsch.
Non parlo italiano.
我不讲中文。
Я не говорю русского.

I speak English, I am Chinese, and I take Spanish. I am also fluent in BASIC, Python, HTML, LaTeX, TI-BASIC, and a little bit of JavaScript and Virtual Basic.

[quote="SoxFan34"]I'm curious, i noticed a lot of people are of foriegn descent. Could you fill me in? :D[/quote]
This is the perfect example of USA-centrism.
I have absolutely no idea what country you live in, it could be Hungary or Gambia, but Turkmenistan as well.
There is a difference between being of "foriegn descent" and being a foreigner, or did you think only people in the USA could afford an internet connection?

Secondly, I have at least some understanding of three other languages, two of which are official languages in my OWN country.  Are they "foreign"?

Aah I remember the days, when "foreign" had no meaning on Mathlinks, a second language could be English, .....

[quote="fredbel6"]Aah I remember the days, when "foreign" had no meaning on Mathlinks, a second language could be English, .....[/quote]English is the second language in AoPS - MathLinks!! The first is Maths ... :P

I am not trying to be racist or anything, by "foreign languages" I mean languages that are not commonly spoken in the US. I live in the USA, but am of russian descent. I'm just curious.

OK!

Russian, Irish, Chinese, Japanese, Turkish, French, English, etc.... Hebrew, Egyptian............(I take it all the way up to Adam and Eve.)

Okay then :

1.  Dutch=Nederlands (my native, and the dominant language in Belgium)
2.  English
3. French=français, je ne parle pas souvent cette langue, et c'est pour ça que faire une conversation rapide en français est vraiment difficile pour moi  :(
4. German=Deutsch, I know the basics, and when a German speaks very slowly, I can understand him .. mein Deutsch ist nicht so gut, aber ich möchte es gerne lernen.

(5. Latin, but of course I don't speak this language ("Romani ite domum!"  :P )

I know Russian, English (obiously) and I'm learning Spanish. :D

I know Russian with a little bit of English (most comes from Google Language Tools), Italian, what I remember of Spanish and German [size=9][color=white][hide]okay I know English[/hide][/color][/size]

I speak Spanish (mother language) english and I'm learning german. I had been also learning esperanto, but I dropped it 'cause I have time to spare no more :P. However, from these four, the one I like least is english...

[quote="Eli"]A tiny bit of Japanese, some Chinese, a tiny bit of Spanish, a few word in French, some LaTeX, a bit of C/C++, some Javascript (I can only read, not write yet), some HTML, a bit of BBCode, English (32 on ACT reading),  some Latin (If you think that Latin is not worth learning, then [i]Tu fatua es.[/i]), music (I don't know the name for that), and some math.[/quote]
Okay, but please let us not let this topic degenerate into "I know HTML and C++" topic (I would not be the first time  :o ).  Nobody chats in Latex.  Try to order a drink in HTML once. :ninja:

[quote="fredbel6"]Try to order a drink in HTML once. :ninja:[/quote]

You can order drinks in HTML, as long as you order java :harhar: :roll:

I can swear in english, chinese, japanese, russian, italian, spanish, german, hindi, and probably some other languages too.

[quote="i_like_pie"][quote="kyyuanmathcount"]I speak Chinese and English and LaTeX fluently.  hablo espanol poco?  (is that right?)[/quote]
Hablo un poco español.[/quote]
Hablo espanol un poco works better in this situation, I believe.

[quote="fredbel6"][quote="kyyuanmathcount"][quote="nutz_for2.718281828"]Hey!! VV's Back!

Also, I'm planning on learning Italian, because I'm bored of only English.

P.S. Foriegn in what point of view?[/quote]

Um, don't call him VV, he sayed he gets pissed off.  Valentin Vornicu should work.

I speak Chinese and English and LaTeX fluently.  hablo espanol poco?  (is that right?)[/quote]
Oh man please, this must be like the fourth topic about this and always, and I mean ALWAYS it degenerates into a "I know HTMl or C++" topic.  I get the joke, everyone gets it know.

For the rest, I know next to no Spanish, apart from "no hablo español' :(
(hablo, hablas, habla, hablamos,habláis,hablan?)
Oh, and I think that Spanish is a pronoun dropper and has two genders.[/quote]
You can conjugate! :D

What do you mean by pronoun dropper? There's él and ella (he and she).

[quote="i_like_pie"]
You can conjugate! :D

What do you mean by pronoun dropper? There's él and ella (he and she).[/quote]
Actually I can't. :wink:   I only know the -ar verbs, I forgot the -ir and -or conjugations.

As far as I know, pronoun droppers are languages where pronouns exist, even as the subject of a sentence, but they are not obligatory and usually omitted.
Latin is of course a very good example : "Te amo" = "I love you"
French, English, German and Dutch are no pronoun droppers.
But as far as I know, Spanish is? :maybe:

[quote="Ignite168"]Spanish is a pronoun dropper as most of the time, the conjugation implies the subject of the sentence.

And there are no such thing as -or verbs  :maybe:[/quote]

You are correct, I should have written -ar,-ir, en -er verbs. :o

I should have known because the "most regular" conjugations in Latin go like "amare", "monere" and "audire".  (In Italian the infinitives actually end in are,ire and ere, so the similarity to Latin is even more obvious)

I speak English, I'm learning Spanish and Russian, I know bits and pieces of Arabic, and I'm starting to pick up $\ LaTeX$. :D

I apologize if my first intro sounded offensive to anyone. I did not mean it to be offensive.

I speak English (primarily), Chinese and now learning Japanese.

My spanish is beastly, for an 8th grader I guess. I know all the preterite and present verb conjugations, regular and irregular, and I'm learning to use direct and indirect object pronouns more fluently.

My chinese is all right, I guess. Not the best.

your spanish is beastly? mine is more like a fish...I don't talk much, and the words usually come out in gurgles.

My chinese is beastlike. I go RAWR RAWR RAWR

Well mine (chinese) is like,

MEOWWWWWWWWWWWWWWW.....

like a japanese woman

[aops]AOPSers speak in AoPS language[/aops]

WOW, this thread is OLD!!!

I wasn't even born in $2006$  :roftl:

[quote=mathnerd314]
Я не говорю русского.
[/quote]

AlienGirl thanks for the bump so I could point out that this is probably bad grammar

[quote=DaredevilChicken11]LOL  :P  :omighty:[/quote]

¡cuando le reanimar es [s]innecesario[/s] sus!

[s]i speak chinese, actually[/s]


Prove that the three inequalities

$\dfrac{a_1b_2}{a_1+b_2} < \dfrac{a_2b_1}{a_2+b_1}, \dfrac{a_2b_3}{a_2+b_3} < \dfrac{a_3b_2}{a_3+b_2}, \dfrac{a_3b_1}{a_3+b_1} < \dfrac{a_1b_3}{a_1+b_3}$

cannot be true simultaenously, if the numbers $a_1,a_2,a_3,b_1,b_2,b_3$ are positive.

[hide]Let's take the reciprocals of all these and flip the sign.
(a1+b2)/a1b2>(a2+b1)/a2b1 or 1/b2+1/a1>1/b1+1/a2.
(a2+b3)/a2b3>(a3+b2)/a3b2 or 1/b3+1/a2>1/b2+1/a3.
(a3+b1)/a3b1>(a1+b1)/a1b3 or 1/b1+1/a3>1/b3+1/a1.
Now, let's solve the inequality for a2, a3, and a1 respectively.
1/b2+1/a1-1/b1>1/a2.
1/b3+1/a2-1/b2>1/a3
1/b1+1/a3-1/b3>1/a1
Now, let's assume that by subtracting x from the left hand side of equation 1, we can equation 1 an equality.
1/b2+1/a1-1/b1-x=1/a2.  We substitute 1/a2 into equation 2.
1/b3+1/b2+1/a1-1/b1-x-1/b2>1/a3.  We simplify the equation and get 1/b3+1/a1-1/b1-x>1/a3.  Again, we assume that some given y when subracted from the left hand side of this new equation yields an equality.  1/b3+1/a1-1/b1-x-y=1/a3.  We substitute 1/a3 into equation 3.
1/b1+1/b3+1/a1-1/b1-x-y-1/b3>1/a1.  We simplify to get 1/a1-x-y>1/a1, which is false since -x and -y are negative.  We have a contradiction, showing that not all 3 of these equations are true.[/hide]

[quote="dengmi"][hide]Let's take the reciprocals of all these and flip the sign.
(a1+b2)/a1b2>(a2+b1)/a2b1 or 1/b2+1/a1>1/b1+1/a2.
(a2+b3)/a2b3>(a3+b2)/a3b2 or 1/b3+1/a2>1/b2+1/a3.
(a3+b1)/a3b1>(a1+b1)/a1b3 or 1/b1+1/a3>1/b3+1/a1.[/quote]

At this point you are basically done. Just add the three inequalities to get \[ \dfrac{1}{a_1} + \dfrac{1}{a_2} + \dfrac{1}{a_3} + \dfrac{1}{b_1} + \dfrac{1}{b_2} + \dfrac{1}{b_3} > \dfrac{1}{a_1} + \dfrac{1}{a_2} + \dfrac{1}{a_3} + \dfrac{1}{b_1} + \dfrac{1}{b_2} + \dfrac{1}{b_3} \] which is a very obvious contradiction, so the inequalities cannot hold simultaneously.


analytic geometry
graphing lines
slope
calculus
function

Can someone please help me with this problem as I can't for the life of me work out what it means?

'In order to climb a hill of gradient 1 in 6, a cyclist rides so that he makes an angle of 45° with the line of greatest slope. What is the gradient of his route?'

What does "line of greatest slope" mean?
Thanks for any help.

What does gradient mean?  Line of greatest slope implies steepest.  To me, gradient is something in multivariable calculus that allows you to find steepest ascents and descents, but you need to have a function.  And that's well beyond middle school math.

This may be a useful site for what gradient means at an elementary level (in short, gradient=slope)

[url]http://www.mathsisfun.com/gradient.html[/url]

Therefore, it is a concept suitable for middle school :)

PS: This problem deals with gradient of a straight line, in other words, the function is a linear function and the gradient is a constant. (Multivariable calculus connection)

This is my interpretation so far. The hill has a slope of $ \frac{1}{6}$.

We need to find the slope of his route.

Questions:
1) Since this is supposed to be a linear hill, wouldn't the line of greatest slope be the slope of the hill?
2) What do you mean by "he makes an angle of 45 degrees with the line of greatest slope"?

Correct me if my interpretations are wrong, the original problem needs some editing.


1)Let $ A$ be a complex Hermitian $ n$x$ n$ matrix that is positive define .Let $ z \in {\mathbb{C}^{n}}$ ,$ z \neq 0$ .
Find the Limit :
         $ \lim_{k \to + \infty}{\frac {z^{*}A^{k + 1}z}{z^{*}A^{k}z}}$
 exists and is an eigenvalue of $ A$ ([color=darkblue]maximum[/color])
Here $ z^{*} = \overline{z^{T}}$

Let $ A$ be a non zeroo hermitian $ \geq{0}$ matrix. Then $ \rho\equal{}Sup(spectrum(A))>0$.

Excuse me for the "false" previous post.
Let $ A$ be a non zero $ \geq{0}$ $ (n\times{n})$ hermitian matrix. Let $ spectrum(A)\equal{}\{\lambda_1,\cdots,\lambda_n\}$. Then $ \rho\equal{}Sup((\lambda_i)_i)>0$. Let $ E\equal{}ker(A\minus{}\rho{I}_n)$ and $ \{e_1,\cdots,e_n\}$ be an othonormal basis that diagonalizes $ A$ s.t. $ \{e_1,\cdots,e_p\}$ is a basis of $ E$. If $ z\equal{}\sum{z}_ie_i$, then $ z^*A^{k\plus{}1}z\equal{}\sum_{i\leq{p}}\lambda_i^{k\plus{}1}|z_i|^2\plus{}\sum_{i>p}\lambda_i^{k\plus{}1}|z_i|^2$. Now we must assume that the orthogonal projection of $ z$ on $ E$ is a non zero vector, that is
(*)  $ \sum_{i\leq{p}}|z_i|^2>0$.
Then $ z^*A^{k\plus{}1}z\sim\rho^{k\plus{}1}\sum_{i\leq{p}}|z_i|^2$ and $ z^*A^{k}z\sim\rho^{k}\sum_{i\leq{p}}|z_i|^2$  QED
Remark: if $ z$ is randomly chosen then the condition (*) is satisfied.


geometry trigonometry calculus integration

[hide="This was a bonus question, intended as a team problem to be solved within 20 seconds. On your mark, get set, GO!!!"]

MATH: Short Answer:
What is the area of the region enclosed by the graph of the polar curve \[ r\equal{}\frac{1}{\sin\theta\plus{}\cos\theta}\] and the $ x,y$ axes?

[hide="Solution"]
Clear the denominator and we get $ r\sin\theta\plus{}r\cos\theta\equal{}x\plus{}y\equal{}1$. The area of the triangle is $ \boxed{.5}$

Did you think you would need some quick integration?? :P
[/hide]
[/hide]

i think so.  At first i was like, woah this is complicated. but then i thought "This is SCIENCE bowl, it cant be too hard."

so yeah i got it  :)

dude haha i solved that in like 3 seconds its nice though

I didn't actually solve it... just thought "OK, this has to be something simple, and it isn't a circle... so it must be a line."


I'm trying to use the massive geometry_dev package, which I downloaded [url=http://piprim.tuxfamily.org/asymptote/travaux/modules/geometry_dev.asy]here[/url]. When I try it out I get an error at 1322.34 (i.e., way in the middle somewhere) "no matching variable fill type.fill"

Any ideas on what's going on here would be appreciated  :)

Please, update geometry_dev from the [url=http://svnweb.tuxfamily.org/listing.php?repname=piprim%2Fasymptote&path=%2Fbranches%2F#path_branches_]svn repository[/url].

I couldn't see at that site what I was supposed to do to download that file (I presume you mean [url=http://svnweb.tuxfamily.org/filedetails.php?repname=piprim%2Fasymptote&path=%2Fbranches%2Fgeometry_dev.asy]this[/url] one), so I copied the text and overwrote the previous version of geometry_dev I was using. I get the exact same error though when I try to run my file. I don't know if the copy-paste method is messing things up at all.

I'm sorry, it's Asymptote you need to update.
Here Asymptote version 1.69svn-r4119, but 1.68 should do.


A salesperson kept a mileage log of the last work week. How many miles per gallon, to the nearest tenth, did the salesperson get for the entire week?

\[ \begin{tabular}{c c p{1.6cm} p{1.5cm} }
Day & Miles & Gallons of Gas Used & Miles per Gallon\\
Mon. & 372 & 14.8 & 25.1 \\
Tues. & 290 & 10.4 & 27.9\\
Wed. & 542 & 17.6 & 30.8\\
Thurs. & 601 & 21.2 & 28.3\\
Fri. & 180 & 6.7 & 26.9\\
\end{tabular}\]


analytic geometry
geometry solved
geometry

Hi,
    I have n points on a plane. No three of these are collinear. I have to show that they can be joined in a way that no sides will intersect (except at vertices) and there will be n vertices and overall it'll be a closed polygon.

I know a method, where you choose a point at one end, then extend a line out from it and swipe it around 360 degrees then, you join points in order (starting and ending with the chosen point).

I know this works. So far i have not been able to prove that it does so  :( . I am hazarding a guess that this is not the correct method if i want the solution to be provable (or atleast provable more easily).

Any help appreciated. THANKS!  :D

You want a solution to be provable? :D

Is there a deadline for this one too?

Pierre.

Sorry. You have me confused. We all have our tastes and peculiarities, but I must say, I have never heard of someone [b]not[/b] preferring their solutions to be provable. Now, at primary school this was quiet unnecessery and rightly so. Ah! those were the days! Since then, I must fully admit my dark secret, I love my solutions to be provable for some strange reason. As for reason for this confusion, it maybe down to the different origins of the words 'solution' and 'proof'. You see, 'solution' has its roots in Old French, and 'prove' evolved directly from Latin. Our good friend here has put the cart before the horse. This is no place to discuss the finer points of English, but having been forced to do so, i have no regrets. Do you?

To pbornsztein, please refer to the Combinatorics section of this forum where I posted a question. There you would, I'm sure, delight in the fact that I am not some scandalous person as you might have thought at one time.

Come on now pbornsztein, it's time to admit, or rather confess that the end of the educational year can be referred to as a 'deadline' (though it maybe the understatement of the century ... you understand British humour more than you realise! :) )

Ok, let's give a solution to this problem proposed by a so well-educated gentleman :

Since there is a finite number of points, they determine by pairs a finite number of directions. So, we may choose an orthogonal system of coordinates so that the points have pairwise distincts first coordinate.
Let M_1,..., M_n be the points such that M_i(x_i, y_i) and x_1 < x_2 < ... < x_n.

Now let's draw the line (M_1M_n). Since no three poiints are collinear, this line separates the set of the other points in two groups (eventually empty) according to the side of the line where they are located.
Now, for each of these two groups, join the points in the order of their respective x-coordinate from M_1 to M_n (if one of the groups is empty, then just draw the segment [M_1M_n]), the desired polygon is drawn.

Pierre.


HOW TO FIND THE VALUE OF $ \tan\left(\frac {165}{2}\right)$?

You could plug it into a scientific calculator, yielding $ \boxed{7.5958}$, roughly.

In the future, please refrain from posting in all capitals.

[hide]Note: $ \tan \frac{165}{2}\equal{}\tan \frac{180\minus{}\frac{30}{2}}{2}$
See if that helps[/hide]


http://syk123.mybrute.com

A simple web game. You can put the character name to make a character (so called "brute"). You can train him/her by fighting with other brutes. New abilities, weapons, or pets come up when you level-up.

You can set a password for your brute of course.

It seems that only 6 battles are available for the first day, and 3 battles per day after then.

Can they be my pupils too?
http://oneequalstwo.mybrute.com


geometry
rectangle
combinatorics unsolved
combinatorics

Given 10x10 square,each of cell was numbered 1,2,..10 such that the numbers in 2 adjacent cells is co-prime.Show that:there are some numbers appear at least 17 times in this square!

See if this works  or not.
First of all I suppose that by "adyacent" you mean "with at least a vertex in common", because if you meant "with at least a side in common" by coloring cell $(i, j)$ with colour  $C(i,j)=i+j\; \;(mod 10)\;\; 0\leq i,j\leq 9 \;\;1\leq C(i,j)\leq 10$ you get a colouring which satisfies the condition, since any $2$ adyacent cells have within it consecutive, and hence coprime, numbers, and in which, however, the number of cells of each kind is exactly $10$.
Consider the set of cells with an even number, obviously none of its elements can be adyacent and, therefore, is not difficult to prove its cardinality must be $\leq 25$. Suppose, for the sake of contraddiction that there were at least $26$ of those cells. If we divide the square into 5 pairs of consecutive rows, since $26=5\times5+1$, by the pidgeon hole principle in one of such pair there would be at least 6 of those cells. Divide the corresponding $2\times10$ rectangle into $5$    $2\times2$ squares; again, by the pidgeon hole principle there would be one of those squares containing two of them, but this contraddicts the fact that none of them are adyacent. With the same reasoning it is possible to prove that the number of cells with an odd multiple of 3 is also $\leq 25$.
We deduce from the previous results that there are at least $100-25-25=50$ cells with a number among from $\left\{1, 5, 7\right\}$, and since $50>16\times3+1$ we conclude that one of those numbers appears in at least $16+1=17$ cells.