Putnam
limit
calculus
integration
algebra
partial fractions
calculus computations

Evaluate $\displaystyle\lim_{n\to\infty}\frac{1}{n^4}\prod_{k=1}^{2n}(n^2+k^2)^{\frac{1}{n}}$

[hide="here is what i did"]
I am not 100% sure this is right so could you please correct me if i am wrong.  :)
so $f(x)=\displaystyle\lim_{n\to\infty}\frac{1}{n^4}\prod_{k=1}^{2n}(n^2+k^2)^{\frac{1}{n}}$.
or (this is where i think i might have made a mistake)
$f(x)=\prod_{k=1}^{2n}\left(\frac{n^2+k^2}{n^2}\right)^{\frac{1}{n}}$.

$lnf(x)=\displaystyle\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{2n}ln\left(1+\left(\frac{k}{n}\right)^2\right)$.
so I convert this sum into the integral
$\displaystyle\int_{0}^4ln(1+x^2)dx$.
after using integration by-parts and partial fractions i got
$lnf(x)=4ln(17)+2tan^{-1}(4)-8$
or
$f(x)=e^{4ln(17)+2tan^{-1}(4)-8}$
well this is a really ugly answer so i think i might have done something wrong.  :?  since the answersi have seen for other Putnam problems are not this ugly. [/hide]

[quote="maokid7"]
$lnf(x)=\displaystyle\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{2n}ln\left(1+\left(\frac{k}{n}\right)^2\right)$.
so I convert this sum into the integral
$\displaystyle\int_{0}^4ln(1+x^2)dx$.
[/quote]
It should be $\int_0^2$, not $\int_0^4$. Otherwise you are correct. The answer is, iindeed, somewhat ugly but one can do nothing about it.

BTW, this belongs to Computations and Tutorials rather than to Open Questions, so I'm moving it there.


Take a point $P$ in the inside of a triangle $ABC.$ Denote by $Q$ the intersection point of the line $BP$ and the side $AC$ and denote by $R$ the intersection point of the line $CP$ and the side $AB.$ If $AR=RB=CP$ and $CQ=PQ,$ then find the mesuare of $\angle {BRC}.$ Note that $XY$ denotes the length of the segment $XY.$

[b]Proof (in three steps).[/b]

$1.\blacktriangleright$[u]Menelaus' theorem[/u] in $\triangle ABQ$ for the transversal $\overline {CPR}\Longrightarrow PB=AC\ .$
$2.\blacktriangleright$[u]Theorem of Sinus[/u] in $\triangle BRP\Longrightarrow\cot \widehat {BRC}=\frac 12\cdot \left(\cot A-\cot B\right)\ .$
$3.\blacktriangleright CP=\frac c2\Longrightarrow m(\widehat {BRC})=120^{\circ}\ .$

Let $K$ is the point of intersection of the circumcircle of triangle $BRC$ and $CR$. We have $RK$.$RC$=$RB^2$ or $RK$.$RP$+$RK$.$CP$ =$RK$.$RP$+$RK$.$RB$=$RB^2$.
We can prove $\triangle$ $KBR$ $\sim$ $\triangle$ $KBP$ $\rightarrow$ $KB^2 = KR.KP=KR^2+KR.RP$.
So $RB^2 + KR^2 - KB^2 = RB.RK$. We have $KRB = 60$ or $BRC =120$

[b]A equivalent (but more elaborated) enunciation of this nice problem.[/b][hide][color=darkred]Let $ABC$ be a triangle. Denote the middlepoint $M$ of the side ${BC}$. For a point $P$ of the ray $[AM$ for which $AP=\frac a2$ define the intersection $N\in AB\cap CP$. Prove that:
$1.\blacktriangleright P\in (AM)\Longleftrightarrow A<90^{\circ}\ .$
$2.\blacktriangleright$ If $A<90^{\circ}$ then $NA=NP\Longleftrightarrow m(\widehat {AMB})=60^{\circ}$
and in this case $PC=c$ and $\cot C-\cot B=\frac{2\sqrt 3}{3}\ .$[/color][/hide]See the previous Virgil Nicula's and Vutang's proofs.

[quote="Singular"]$2.\blacktriangleright$[u]Theorem of Sinus[/u] in $\triangle BRP\Longrightarrow\cot \widehat {BRC}=\frac 12\cdot \left(\cot A-\cot B\right)\ .$
can someone explain this theorem/ how this was found?[/quote][hide="Here is a proof."]Denote $x=m(\widehat {BRP})$. Then $m(\widehat {BPR})=$ $m(\widehat {CPQ})=$ $m(\widehat {RCQ})=$ $C-m(\widehat {BCR})=$ $C-(180^{\circ}-B-x)=$ $x-A$. Therefore, from the theorem of Sinus in $\triangle BRP$ $\Longrightarrow$ $\frac{BP}{\sin x}=\frac{BR}{\sin (x-A)}$ $\Longrightarrow$ $2b\sin (x-A)=c\sin x$ $\Longrightarrow$ $2\sin B\sin (x-A)=\sin C\sin x$ $\Longrightarrow$ $\cos (B+A-x)-\cos (B-A+x)=\sin C\sin x$ $\Longrightarrow$ $-\cos (C+x)-\cos (B-A+x)=\sin C\sin x$ $\Longrightarrow$ $\cos x\cos C+\cos (B-A+x)=0$ $\Longrightarrow$ $\cos x\cos C+\cos (B-A)\cos x=\sin (B-A)\sin x$ $\Longrightarrow$ $\cot x=\frac{\sin (B-A)}{\cos C+\cos (B-A)}=$ $\frac{\sin (B-A)}{2\cos \frac{C+B-A}{2}\cos \frac{C+A-B}{2}}=$ $\frac{\sin (B-A)}{2\sin A\sin B}=$ $\frac 12(\cot A-\cot B)$.[/hide]


linear algebra
matrix
probability
combinatorics proposed
combinatorics

we have a $N.N$ matrix.
we place $N$ numbers from $1$ to $N$ with $N>6$

where is the place that have more probability of have a $7$, if a number is the sum of it's $8$ neighborhood?

This is a very nice problem. My Teacher proposed this problem in a class saying the person who solve it wont need to make a test.

onegai, someone, solve this, i have no idea of how to solve.

thanks

Hello Yagaron,
[quote="yagaron"]we have a $N.N$ matrix.
we place $N$ numbers from $1$ to $N$ with $N>6$

where is the place that have more probability of have a $7$, if a number is the sum of it's $8$ neighborhood?[/quote]

Could you, please, give some precisions ?
I understand that we have a $N*N$ matrix in  which we have $N^{2}-N$ values $0$ and the $N$ other values being $1,2,...,N$ and such that each number (except, I think, zeroes) is the sum of its neighbours.

But how could $1$ be the sum of its neighbour since these neihbours may only be $0$ or $> 1$ ?
I think I don't undestand well.  :?:

--
Patrick

i think i make a mistake on the problem, thanks pco

i will talk to my teacher.

from now we can disconsidere the information "we place $N$ numbers"

but the problem is like a card game. we need to take one 7, but  must be a Position that have more probability of haven a 7, is this reasonable, dont is?

thanks and sorry for the mistake, i did not wrote in the paper,


limit
calculus
derivative
logarithms
function
calculus computations

Prove that $ \lim_{x \rightarrow 0}\frac{e^x\minus{}1}{x} \equal{} 1$ [b]without the use of derivatives at all[/b].

$ \lim_{x \to 0}\frac {e^{x} \minus{} 1}{x} \equal{} \lim_{t \to 1} \frac {t \minus{} 1}{\ln t} \equal{} \lim_{t \to 1} \left[\ln[t^{1/(t \minus{} 1)}] \right]^{ \minus{} 1} \equal{} \lim_{t \to 1} \left[\ln[(1 \plus{} t \minus{} 1)^{1/(t \minus{} 1)}]\right]^{ \minus{} 1}$

$ \equal{} (\ln e)^{ \minus{} 1} \equal{} 1$.

Here's the thing- that [i]is[/i] a derivative. It's also the exact limit we need to do any calculus with the exponential function, and how we evaluate it depends on how we define the exponential function.
In many calculus textbooks, $ e$ is [i]defined[/i] as the unique value that makes $ \lim_{x\to 0}\frac{e^x\minus{}1}{x}\equal{}1$. There's nothing to prove, because this is the definition of the function.

[quote="jmerry"]Here's the thing- that [i]is[/i] a derivative. It's also the exact limit we need to do any calculus with the exponential function, and how we evaluate it depends on how we define the exponential function.
In many calculus textbooks, $ e$ is [i]defined[/i] as the unique value that makes $ \lim_{x\to 0}\frac {e^x - 1}{x} = 1$. There's nothing to prove, because this is the definition of the function.[/quote]

In many other books the number $ e$ is defined as $ \lim_{n\to \infty} (1 + \frac1n )^n$

[quote="jmerry"]Here's the thing- that [i]is[/i] a derivative. It's also the exact limit we need to do any calculus with the exponential function, and how we evaluate it depends on how we define the exponential function.
In many calculus textbooks, $ e$ is [i]defined[/i] as the unique value that makes $ \lim_{x\to 0}\frac {e^x \minus{} 1}{x} \equal{} 1$. There's nothing to prove, because this is the definition of the function.[/quote]

Yes, your problem is just definition of $ e$.


calculus
integration
trigonometry
logarithms
calculus computations

$ \int_{0}^{\frac {\pi}{2}}\frac {\sin x}{1 \plus{} \sin^{2}x}\ dx \equal{} \int_1^0 \frac { \minus{} dt}{2 \minus{} t^2} \equal{} \frac {1}{2\sqrt {2}} \ln \frac {\sqrt {2} \plus{} 1}{\sqrt {2} \minus{} 1}$
we use subst. $ \cos x \equal{} t$

Thanks anik_andrew.

$ ... \equal{} \frac{1}{2\sqrt{2}} \ln \mid \frac{3\plus{}2\sqrt{2}}{\minus{}1} \mid \equal{} \frac{1}{\sqrt{2}} \ln(3\plus{}2\sqrt{2})^{\frac{1}{2}}\equal{} \frac{1}{\sqrt{2}} \ln (1\plus{}\sqrt{2})$

hello, your solution can be written as
$ \frac{\sqrt{2}}{2}artanh(\frac{\sqrt{2}}{2})$
Sonnhard.

Thanks Sonnhard.

$ \tanh^{\minus{}1} x \equal{} \frac{1}{2} \ln(\frac{1\plus{}x}{1\minus{}x})$ for $ \minus{}1<x<1$.


linear algebra
matrix
quadratics
function

Let be $ x,y,z\in \mathbb{R}$ such that $ x\plus{}3y\plus{}z\equal{}2$ and $ 11x\plus{}5y\minus{}3z\equal{}8$ . Find the minimum value of $ E\equal{}3x^2\minus{}2y^2\plus{}z$ .

[quote="alex2008"]Let be $ x,y,z\in \mathbb{R}$ such that $ x \plus{} 3y \plus{} z \equal{} 2$ and $ 11x \plus{} 5y \minus{} 3z \equal{} 8$ . Find the minimum value of $ E \equal{} 3x^2 \minus{} 2y^2 \plus{} z$ .[/quote]

$ x\equal{}2\minus{}3y\minus{}z$
$ 11(2\minus{}3y\minus{}z)\plus{}5y\minus{}3z\equal{}8$----> $ z\equal{}1\minus{}2y$---->$ x\equal{}1\minus{}y$--->

$ E\equal{}3x^{2}\minus{}2y^{2}\plus{}z\equal{}3(1\minus{}y)^{2}\minus{}2y^{2}\plus{}1\minus{}2y\equal{}y^{2}\minus{}8y\plus{}4\equal{}(y\minus{}4)^{2}\minus{}60\geq \minus{}60$

Give an example of $ x,y,z$ such that your minimum occurs .  :wink:

[quote="zaya_yc"][quote="alex2008"]Let be $ x,y,z\in \mathbb{R}$ such that $ x \plus{} 3y \plus{} z \equal{} 2$ and $ 11x \plus{} 5y \minus{} 3z \equal{} 8$ . Find the minimum value of $ E \equal{} 3x^2 \minus{} 2y^2 \plus{} z$ .[/quote]

$ x \equal{} 2 \minus{} 3y \minus{} z$
$ 11(2 \minus{} 3y \minus{} z) \plus{} 5y \minus{} 3z \equal{} 8$----> $ z \equal{} 1 \minus{} 2y$---->$ x \equal{} 1 \minus{} y$--->

$ E \equal{} 3x^{2} \minus{} 2y^{2} \plus{} z \equal{} 3(1 \minus{} y)^{2} \minus{} 2y^{2} \plus{} 1 \minus{} 2y \equal{} y^{2} \minus{} 8y \plus{} 4 \equal{} (y \minus{} 4)^{2} \minus{} 60\geq \minus{} 60$[/quote]

That minimum doesn't occurs .

[hide="Solution"]$ \{\begin{matrix}3y+z &=& 2-x\\ 5y-3z &=& 8-11x\end{matrix}$

Solving this as a system in $ y,z$, we get $ y=1-x,z=2x-1$

Now $ E=x^2+6x-3$, so by the known properties of a quadratic function, $ E_{\min}=-12$ for $ x_0=-3$, which yields $ (x_0,y_0,z_0)=(-3,4,-7)$[/hide]

[quote="zaya_yc"][quote="alex2008"]Let be $ x,y,z\in \mathbb{R}$ such that $ x \plus{} 3y \plus{} z \equal{} 2$ and $ 11x \plus{} 5y \minus{} 3z \equal{} 8$ . Find the minimum value of $ E \equal{} 3x^2 \minus{} 2y^2 \plus{} z$ .[/quote]

$ x \equal{} 2 \minus{} 3y \minus{} z$
$ 11(2 \minus{} 3y \minus{} z) \plus{} 5y \minus{} 3z \equal{} 8$----> $ z \equal{} 1 \minus{} 2y$---->$ x \equal{} 1 \minus{} y$--->

$ E \equal{} 3x^{2} \minus{} 2y^{2} \plus{} z \equal{} 3(1 \minus{} y)^{2} \minus{} 2y^{2} \plus{} 1 \minus{} 2y \equal{} y^{2} \minus{} 8y \plus{} 4 \equal{} (y \minus{} 4)^{2} \minus{} 60\geq \minus{} 60$[/quote]
I'm too lazy to check, but is there an algebraic error here (minimum occurs at y=4 is correct, but the minimum value is definitely not -60 -- just solve for z and x with the known value of y=4 and substitute that values into the original expression to get -12)?

[quote="zaya_yc"][quote="alex2008"]Let be $ x,y,z\in \mathbb{R}$ such that $ x \plus{} 3y \plus{} z \equal{} 2$ and $ 11x \plus{} 5y \minus{} 3z \equal{} 8$ . Find the minimum value of $ E \equal{} 3x^2 \minus{} 2y^2 \plus{} z$ .[/quote]

$ x \equal{} 2 \minus{} 3y \minus{} z$
$ 11(2 \minus{} 3y \minus{} z) \plus{} 5y \minus{} 3z \equal{} 8$----> $ z \equal{} 1 \minus{} 2y$---->$ x \equal{} 1 \minus{} y$--->

$ E \equal{} 3x^{2} \minus{} 2y^{2} \plus{} z \equal{} 3(1 \minus{} y)^{2} \minus{} 2y^{2} \plus{} 1 \minus{} 2y \equal{} y^{2} \minus{} 8y \plus{} 4 \equal{} (y \minus{} 4)^{2} \minus{} 60\geq \minus{} 60$[/quote]

i mistake. $ E\equal{}y^{2} \minus{} 8y \plus{} 4\equal{}(y\minus{}4)^{2}\minus{}12\geq\minus{}12$

$ y\equal{}4;x\equal{}\minus{}3;z\equal{}\minus{}7$


Let a_i (i=1,..,n) be real positive numbers. Prove that

((a_1)^n+n-1)((a_2)^n+n-1)...((a_n)^n+n-1) \geq (a_1+..+a_n)^n

You are really extraordinarily quick-witted to solve problems.
Incredible!!!!


this was the 24th question on a national sprint round.

M people pay a total of $X to travel on a tour bus. How much more money (MoMonayy! hehe), in dollars, will it cost for M plus N people to travel on the bus if each person pays the same fare?

i dont care who answers this question, just make sure youre not too advanced for it. and make sure to use spoiler font

thanks you!

Spoiler:

[hide]so each person must pay X/M dollars, and for M+N people to go, they must all pay a total of X/M * (M+N)= XN/M + X. So they have to pay XN/M + X - X more dollars, which simplifies to XN/M dollars[/hide]

[quote="Tare"]I don't quite understand what the problem is asking for.
Is it asking for the amount it will cost for yourself?[/quote]

well, the question was asking for the total amount of money M+N people would pay minus the amount of money for M amount of people.

so for example. if 5 people pay 30 dollars. and 5+3 people each pay the same rate as 5 people. then they would pay 48 dollars. 8 x 6=48. so the answer would be 48-30=18. but thats not the answer of course

[hide]each person: X/M

so then it is X + N(X/M) - X = N(X/M)[/hide]

X/M(M+N) total for those people... just subtract to get how much extra


search
combinatorics unsolved
combinatorics
graph theory

If you label the teams with numbers 1,2,...2n+1. And if for i>j the i-th team beat the j-the team then we have no cycle  triplets.So the minimum is 0.

The maximum is more interesting and i think it is $\frac{1}{4}\left(\stackrel{2n+1}{3}\right)$

I think it is posted before.

If we change $2n+1$ by $n$ ,this problem is very nice

[quote="malezgerd"][quote="boxedexe"][b]Solution.[/b]  A selection of three teams from $\{T_{i}\}_{i=1}^{2n+1}$ is not a cycle triplet if if there is a team that loses to the two others. If $T_{i}$ beats $W_{i}$ teams and loses to $L_{i}$ teams, the number of triplets that are not cyclic is
\[\text{Not}(C)=\sum_{i=1}^{2n+1}\binom{W_{i}}{2}=\sum_{i=1}^{2n+1}\binom{L_{i}}{2}=\sum_{i=1}^{2n+1}\frac{\binom{W_{i}}{2}+\binom{L_{i}}{2}}{2}\\ =\frac{1}{4}\sum_{i=1}^{2n+1}((W_{i}^{2}+L_{i}^{2})-(W_{i}+L_{i}))\geq \frac{1}{8}\sum_{i=1}^{2n+1}((W_{i}+L_{i})^{2}-2(W_{i}+L_{i})). \]
Since $W_{i}+L_{i}=2n$, $\text{Not}(C)\geq \frac{n(n-1)(2n+1)}{2}$.  As a result, the maximum is
\[\binom{2n+1}{3}-\frac{n(n-1)(2n+1)}{2}=\frac{n(n+1)(2n+1)}{6}, \]
as required.$\blacksquare$[/quote]

Only $4$ points out of $7$.

you proved this is a bound, not a maximum  :wink:[/quote]
The minimum of $\text{Not}(C)$ can clearly occur.  I don't understand what you are trying to say.

it is special case of Polish MO Final 2004 (actually one of two cases ;p)

b)

we'll search for non-cyclic triples. let $k=2n+1$ let $x_{i}$ determine number of looses of player $i$. so $\sum x_{i}={k \choose 2}$. if triple is non-cycle, then one of its players wins with two others. then the number of non cyclic triples is:

$\sum{x_{i}\choose 2}= \frac{1}{2}(\sum (x_{i})^{2}-{k \choose 2}) \geq \frac{1}{2}(\frac{1}{k}(\sum x_{i})^{2}-{k \choose 2}) = \frac{k(k-1)(k-3)}{8}= t$

then the maximal number of cyclic triples is:

${k \choose 3}-t = \frac{k(k^{2}-1)}{24}$

second case: k = 2n
$\sum{x_{i}\choose 2}\geq \frac{k(k-2)^{2}}{8}$
then we've got $\frac{n(n^{2}-4)}{24}$

omg i'm wasted, i'll think about a) tommorow ;) night night

btw. malezgerd... you tried to be smart but you failed, this is coherent proof but no, you have whine ;)

[quote=boxedexe][b]Solution.[/b]  A selection of three teams from $\{T_{i}\}_{i=1}^{2n+1}$ is not a cycle triplet if if there is a team that loses to the two others. If $T_{i}$ beats $W_{i}$ teams and loses to $L_{i}$ teams, the number of triplets that are not cyclic is
\[\text{Not}(C)=\sum_{i=1}^{2n+1}\binom{W_{i}}{2}=\sum_{i=1}^{2n+1}\binom{L_{i}}{2}=\sum_{i=1}^{2n+1}\frac{\binom{W_{i}}{2}+\binom{L_{i}}{2}}{2}\\=\frac{1}{4}\sum_{i=1}^{2n+1}((W_{i}^{2}+L_{i}^{2})-(W_{i}+L_{i}))\geq \frac{1}{8}\sum_{i=1}^{2n+1}((W_{i}+L_{i})^{2}-2(W_{i}+L_{i})).\]
Since $W_{i}+L_{i}=2n$, $\text{Not}(C)\geq \frac{n(n-1)(2n+1)}{2}$.  As a result, the maximum is
\[\binom{2n+1}{3}-\frac{n(n-1)(2n+1)}{2}=\frac{n(n+1)(2n+1)}{6},\]
as required.$\blacksquare$[/quote]

You could have also directly bounded by counting the number of triples with one person beating two people:

Let the number of people $A_1 , A_2 , ... A_{2n+1}$ defeated be $a_1 , a_2 , ... a_{2n+1}$ respectively. We want to minimize the number of non-cyclic triplets as possible. So we want to minimize:

$\binom{a_1}{2}+\binom{a_2}{2}+...+\binom{a_{2n+1}}{2}$.

But that's just:

$\binom{a_1}{2}+\binom{a_2}{2}+...+\binom{a_{2n+1}}{2}$ ≥ $(2n+1)*\binom{\frac{a_1+a_2+...a_{2n+1}}{2n+1}}{2}$ = (2n+1)*$\binom{n}{2}$.

So max number of triangles is $\binom{2n+1}{3}$ - (2n+1)*$\binom{n}{2}$ = $\frac{n(n+1)(2n+1)}{6}$.

So this formula is also the sum of squares, which really suggests a bijection argument. I'm probably not going to get that myself since I needed a hint to come up with the above sol in the first place.

The previous posts find the minimum of $0$ and maximum of $\frac{n(n+1)(2n+1)}{6}$, so I will prove that they are achievable. By visualizing this using graphs with teams as vertices and use directed edges, we want to consider the minimum and maximum directed triangles.

For the minimum of $0$, consider a tournament in which each team has a different skill level, and there are no upsets. There are no cycle triplets this way.

For the maximum, consider a configuration the vertices are equally spaced around a circle. An arrow points from vertex $A$ to $B$ if and only if there is an even number of vertices between $A$ and $B$ when traveling counterclockwise around the circle. Below is the configuration for $n=2$.
[asy]
unitsize(1.5cm);
dot(dir(90)); dot(dir(162)); dot(dir(90+144)); dot(dir(90 + 216)); dot(dir(18));
draw(dir(90)--dir(162), EndArrow); draw(dir(162)--dir(234), EndArrow); draw(dir(234)--dir(306), EndArrow); draw(dir(306)--dir(18), EndArrow); draw(dir(18)--dir(90), EndArrow); draw(dir(90)--dir(234), BeginArrow); draw(dir(234)--dir(18), BeginArrow); draw(dir(18)--dir(162), BeginArrow); draw(dir(162)--dir(306), BeginArrow); draw(dir(306)--dir(90), BeginArrow);
[/asy]
I claim that there are of $\frac{n(n+1)(2n+1)}{6}$ directed triangles in this configuration, and we induct on $n\ge 1$. If $n=1$ we can clearly have a maximum of $\frac{1\cdot 2\cdot 3}{6} = 1$ directed triangle.

For the inductive step, we add two vertices to go from $2n+1$ to $2n+3$ and want to show that there are $(n+1)^2$ additional triangles formed. We add the two vertices $A$ and $B$ such that they are consecutive and the entire graph still obeys the arrow rule. WLOG, $B$ is 1 vertex counterclockwise from $A$ (ie the edge $AB$ points to $B$).

We can see that there are $n+1$ new triangles that include $A$ and $B$. For triangles that contain $A$ and not $B$, there are $n+1$ edges pointing at $A$ and $n$ edges pointing away. For the $n(n+1)$ combinations of two edges and $A$, half of them result in a directed triangle. This is because if $DA$ points at $A$ and $AC$ points at $C$, then there are an even number of vertices between $C$ and $D$ moving counterclockwise only when $D$ is to the left of $C$ when viewed from $A$. By symmetry, this will happen half of the time. Similarly, there are $\frac{n^2+n}{2}$ triangles containing $B$ and not $A$. In all, there are $(n+1) + \frac{n^2+n}{2} + \frac{n^2+n}{2} = (n+1)^2$ new triangles, which completes our induction.

For completeness, $n=0$ leads to no cycle triplets.

We rephrase the problem as finding the minimum and maximum number of directed triangles in a tournament on $2k+1$ vertices.

Clearly, we can get $0$ directed triangles by drawing $i\to j$ if and only if $i<j$. So it suffices to find the maximum number.

We claim the maximum number of directed triangles is $\binom{2k+1}{3}-(2k+1)\binom{k}{2}$. To see this, note that the number of collections of $3$ vertices that don't form a triangle is
\[T=\sum_{v\in V}\binom{\mathrm{outdeg}(v)}{2}\ge(2k+1)\binom{k}{2}\]
by Jensen. To have equality, we just need all the outdegrees and indegrees to be equal to $k$, and this is achieved by $i\to i+1,\ldots,i+k\pmod{2k+1}$.

[quote=N.T.TUAN]Consider a round-robin tournament with $2n+1$ teams, where each team plays each other team exactly one. We say that three teams $X,Y$ and $Z$, form a [i]cycle triplet [/i] if $X$ beats $Y$, $Y$ beats $Z$ and $Z$ beats $X$. There are no ties.
a)Determine the minimum number of cycle triplets possible.
b)Determine the maximum number of cycle triplets possible.[/quote]

[hide=Minimum]The minimum value is $0$.This can achived as follows.Label the vertices $v_1,v_2\cdots v_{2k+1}$.For any $i$ draw the out-edges $v_i\to v_{i+1},\cdots v_{2k+1}$.
Indeed for any $i,j,k$ WLOG $i<j<k$ then $v_i\to v_j,v_j\to v_k,v_i\to v_k$ which clearly isnt a cycle hence this construction works. [/hide]
[hide=Maximum]Note that in-order to maximize number of cycles we need to minimize number of acycles and any acycle can be represented as $(i,j,k)$ for which $i\to j,i\to k$ are an edge.Let $T=(u,v,w)$ be the number of triples of vertices for which $w\to u,w\to v$ is an edge.Let $c_w$ denote the number of out-edges from vertex $v_w$.
[size=150]Lemma[/size] $\sum c_v=k(2k+1)$
[i]Proof[/i] Let $A,B$ be sum of all in-degrees and out-degrees respectively.Note that any edge connecting two vertices adds $1$ to both $A,B$.Hence $A=B$.Since $A+B=2\binom{2k+1}{2} \Rightarrow A=(2k+1)k$.$\square$

Hence $T=\sum_{v\in |V|} \binom{c_v}{2} \ge (2k+1)\cdot \binom{\left(\dfrac{\sum c_v}{2k+1}\right)}{2}=(2k+1)\cdot \binom{k}{2}$ because of Jenson's inequality on the convex function $\binom{x}{2}$ and our Lemma.Hence the max triangle-cycles is $\binom{2k+1}{3}-(2k+1)\cdot \binom{k}{2}=\dfrac{k(k+1)(2k+1)}{6}=1^2+2^2+\cdots k^2$.
[hide=Construction]Construct like this $i\to i+1,\ldots,i+k\pmod{2k+1}$ basically equalizing in and out degress.
[/hide]$\blacksquare$[/hide]

The minimum is $0$. Label the vertices $1, 2, \ldots 2n + 1$, and for each edge $i, j$, it will point towards the higher vertex. There are clearly no triangles.

The maximum is $\frac{n(n+1)(2n+1)}{6}$. This is achievable by placing the vertices on a circle, evenly spaced, and for each edge $v, w$, it will point toward $w$ iff $w$ is on the left side of the diameter through $v$. Then, all triples of vertices that form an acute triangle will be a directed triangle, and there are $\frac{(2n+1)n(n+1)}{6}$ such triangles (to see this, for each vertex $v$, there are $1 + 2 + \ldots n$ acute triangles that contain $v$, and this is true by doing casework on the vertex on the left side of the diameter through $v$).

I claim this is the upper bound. Denote a hairpin as two edges that share a vertex $v$ such that they are either both pointing away from $v$ or they're both pointing into $v$. Every non-directed triangle has exactly two hairpins, so we want to minimize the number of hairpins. For each vertex, if there are $a$ edges going into it, then the number of hairpins centered at that vertex is $\binom{a}{2} + \binom{2n-a}{2}$. This is minimal when $a = n$, so the number of hairpins per vertex is at least $n(n-1)$. Summing over all vertices, there are at least $(2n+1)n(n-1)$ hairpins, and since each non-directed triangle has two hairpins, there are at least $\frac{(2n+1)n(n-1)}{2}$ non-directed triangles. Every other triangle is directed, so the number of directed triangles is at most
\[\binom{2n+1}{3} - \frac{(2n+1)n(n-1)}{2} = \frac{n(2n+1)(2n-1)}{3} - \frac{(2n+1)n(n-1)}{2}\]
\[= (2n+1)(n)(\frac{2n-1}{3} - \frac{n-1}{2}) = \frac{(2n+1)(n)(n+1)}{6}\]

a) The answer is $0$. Simply make team $i$ defeat team $j$ iff $i > j$. It is easy to see that $x < y < z < x$ can never happen.

b) The answer is $\frac{n(n+1)(2n+1)}{6}$.

To show that this is possible, arrange the $2n+1$ teams in a circle and have team $i$ defeat team $j$ iff $i$ is at most $n$ spots counterclockwise from $j$. Then if $a, b, c$ are the number of spots in between the teams $x, y, z$, we obtain $a+b+c=2n+1$ with $1 \le a, b, c \le n$. A classical application of stars and bars and PIE gives us,
\[ \frac13 (2n+1) \left( \binom{2n}{2} - 3 \binom{n}{2} \right) = \frac16 (2n+1) n ((4n-2) - (3n-3)) = \frac{n(n+1)(2n+1)}{6} \]
cycle triplets, since after fixing $x$ in $2n+1$ ways, we count each triplet thrice.

Now to show that this is the maximum, let an ordered triple of teams $(x, y, z)$ where team $x$ defeats team $y$ and team $y$ defeats team $z$ a [i]critical[/i] triple. Notice that each unordered triple of teams either contains $3$ critical triples (if it is a cycle triplet) or $1$ critical triple. It suffices to show that there are at most
\[ \binom{2n+1}{3} + \frac{n(n+1)(2n+1)}{6} \cdot 2 = \frac{2n(2n+1)(2n-1+n+1)}{6} = n^2 (2n+1) \]
critical triples. But if a team $t$ defeats $o$ teams and is defeated by $i$ teams, then it is the middle element of exactly $io$ critical triples. Now
\[ io \le \left( \frac{i+o}{2} \right)^2 = \left( \frac{2n}{2} \right)^2 = n^2,\]
so by summing over all possible middle triples, we are done. $\blacksquare$

a) [b]Lower Bound:[/b]
The minimum bound is 0. Let $A_n$ be some tournament on $n$ vertices such that there are no directed triangles. We show that $A_n$ exists for all $n \ge 3$.

First, the base case $A_3$ can be defined by the edges $\{(v_1 \to v_2), (v_1 \to v_3), (v_2 \to v_3)\}$

We can inductively generate $A_{n+1}$ from $A_n$. Start with $A_n$. Add the new vertex $v_{n+1}$. Construct the directed edge $v_i \to v_{n+1}$ for all $1 \le i \le n$. Now observe that there are no directed triangles in $A_n$, by induction hypothesis. Furthermore, there are no directed triangles that include $v_{n+1}$, by construction. Thus there are no directed triangles in $A_{n+1}$, as desired.

b) [b]Upper Bound:[/b]
Let $T$ be the number of directed triangles and $T'$ be the number of non-directed triangles. Thus we have that
$$T = \binom{2k+1}{3} - T' \qquad \qquad (1)$$
Let $\deg^{-}(v_i)$ denote the indegree of the vertex $v_i$. Observe that each pair of edges $(v_y \to v_x), (v_z \to v_x)$ for some given vertex $v_x$ corresponds to a unique non-directed triangle, the converse is also true. Furthermore, note that the average value of $\deg^{-}(v_i)$ is
$$  \frac{1}{2k+1} \sum_{i = 1}^{2k+1}\deg^{-}(v_i)  = \frac{1}{2k+1} \binom{2k+1}{2} = k$$
This implies that
$$T' = \sum_{i = 1}^{2k+1} \binom{\deg^{-}(v_i)}{2} \ge (2k+1)\binom{k}{2} \qquad \qquad (2)$$
by Jensen's inequality.

Thus, (1) and (2) imply that $$T = \binom{2k+1}{3} - T' \le \binom{2k+1}{3} - (2k+1)\binom{k}{2} = \frac{k(k+1)(2k+1)}{6}$$

[b]Construction for upper bound:[/b]
For each edge $(v_i, v_j)$ with $i < j$, construct the directed edge $(v_i \to v_j)$ if $j-i$ is odd, otherwise construct $(v_j \to v_i)$ if $j-i$ is even.

[b]Remark:[/b]
The lower bound is easy to think of, especially if you think about the "team" phrasing of the problem.
I thought of the upper bound when considering the 5-way rock paper scissors configuration for $2k+1 = 5$  :play_ball: In general, I literally just find some symmetrical configuration for a GT problem and try it out. In $\ge 95 \%$ of the problems, this corresponds to an upper or lower bound.  :coolspeak:

Label the vertices $i$ from $1$ to $2k+1$. The minimum is 0. Achievable if  $i\rightarrow j \Leftrightarrow i>j$. A directed triangle would give $i>j>k>i$,  absurd, so there are no directed triangle.

Next, I claim the maximum is $\binom{2k+1}{3}-(2k+1)\cdot \binom{k}{2}$. Note that each cycle $abc$ is either a directed triangle, or it is a cool triangle, (defined as $\exists a\in \triangle, a\rightarrow b, a\rightarrow c$). Thus, it suffices to show that there are at least $(2k+1)\cdot \binom{k}{2}$ cool triangles.

First the lower bound, label the outdegree of each node $c_i$, then we have $\sum c_i = \binom{2k+1}{2}$. Thus,by double counting, the number of cool triangles is (ineq comes from jensen's)
\[=\sum \binom{c_i}{2} \geq (2k+1) \sum \binom{\mathbb{E}(c_i)}{2} = (2k+1)\cdot \binom{k}{2}\]
This is achievable when each vertex has $k$ out and $k$ in degree. We can achieve this by assigning the edge $i\rightarrow j$ if and only if $i-j\leq k \pmod{2k+1}$. Thus, our $\geq (2k+1)\cdot \binom{k}{2}$ minimum bound is achievable. So the maximum bound on directed triangles is
\[\binom{2k+1}{3}-\frac{(2k+1)k(k-1)}{2} = k(2k+1)\frac{(2)(2k-1) - 3(k-1)}{6} = \frac{k(2k+1)(k+1)}{6}\]
$\blacksquare$

Just a quick note: For the bounding part, you can use Cauchy as well, in the classic $(x_1^2+x_2^2+\cdots x_{2n+1})^2\cdot (2n+1)\geq (x_1+x_2+\cdots x_{2n+1})^2$ because the RHS is fixed. In this inequality, the $x_i$ denote the indegrees of the vertices.

The minimum possible number of directed triangles is $0$; we can simply direct $i \to j$ iff $i < j$, and we cannot ever have $a < b < c < a$. The maximum possible number is $\tbinom{2k+1}{3} - (2k+1)\tbinom{k}{2}$. This can be achieved if we direct $i \to j$ iff $j - i \in [1, k] \pmod{2k+1}$.

Note that there are only two types of triples - directed triangle or a triple where some guy is directed towards both the other remaining guys. We count the minimum number of triples of the latter description based on casework on its dominant guy (guy who is directed towards remaining two). Note that there is no overcounting because every such triple only has one such dominant guy.

Say the dominant guy is vertex $v$. The number of triples including it as the dominant guy is $\tbinom{\text{outdeg}(v)}{2}$. Hence the total number of such triples is\[\sum_{v} \binom{\text{outdeg}(v)}{2} \geq (2k+1)\binom{k}{2}\]by Jensen's, since it is known that in a directed tournament, $\sum \text{outdeg}(v) = k(2k+1)$. Indeed, the maximum number of directed triangles is then the complement of this, as desired.

[b]Quick Sketch.[/b]
[color=#f00]a.[/color] The minimum is $0$ and it works for all tournaments with a positive integer amount of teams and not only odd numbers. Say it's true for $k$ teams. For $k+1$, just make sure the new team beats all $k$ teams. It's easy to see that no cycle triplets containing the new team.

[color=#f00]b.[/color] Label the teams $1,2,\dots,2n+1$. Let $i_1,\dots i_{2n+1}$ be the indegree and $o_1,\dots o_{2n+1}$ be the outdegree of team $1,\dots 2n+1$ respectively. The [b]key claim[/b] is that the number of noncycle triplets is
$$\frac{1}{2}\left (\sum_{j = 1}^{2n+1}\binom{i_j}{2} + \binom{o_j}{2}\right).$$
It is minimized if $o_j=i_j=n$. It follows that the maximum cycle triplets is $\binom{2n+1}{3}-(2n+1)\binom{n}{2}$.

[b]Construction for the maximum: [/b]Put the teams in a circle in any order. Let team $\ell, \forall \ell = 1,\dots 2n+1$ beats the $n$ teams to its right and loses to the $n$ teams to its left.

[quote=N.T.TUAN]Consider a round-robin tournament with $2n+1$ teams, where each team plays each other team exactly one. We say that three teams $X,Y$ and $Z$, form a [i]cycle triplet [/i] if $X$ beats $Y$, $Y$ beats $Z$ and $Z$ beats $X$. There are no ties.
a)Determine the minimum number of cycle triplets possible.
b)Determine the maximum number of cycle triplets possible.[/quote]

We claim that $\max_{\text{number of cyclic triplets}}=\binom{2n+1}{3}-(2n+1)\binom{n}{2}$ and $\min_{\text{number of cyclic triplets}}=0$
[b][color=#f00]The Minimum Value:-[/color][/b] Order all the participants as $1,2,3,4,........,2N-1$
The idea is clear:-We make the $X$th player to defeat all the players less than $X$
Then the condition becomes equivalent to $X \ge Y,Y \ge Z,Z \ge X \implies X \ge Z$, contradiction.
[b][color=#f00]The Maximum Value:-[/color][/b] A simple double counting algorithm shows that there are atleast $$(2n+1) \binom{n}{2}$$ non-cyclic triplets.
Thus there are atleast $$\binom{2n+1}{3}-(2n+1)\binom{n}{2}$$ cyclic triplets.
The construction:-Make the $X$th team loose to $n$ terms to the right and win to $n$ terms to the left.$\blacksquare$

The minimum is not very interesting (it's simply zero), so we focus more on the maximum.

The idea is to double count angles between two edges that are oppositely oriented. Let there be $x$ directed triangles and $y$ non-directed triangles.

On one hand, for every vertex, there are at most $n^2$ angles, because we have $k(2n-k)$ angles where $k$ is the number of edges facing outwards. Thus, there are at most $n^2(2n+1)$ angles. On the other hand, every directed triangle contributes three angle, while every non-directed triangle contributes one angle. Furthermore, there are ${2n+1 \choose 3}$ triangles in total. Thus, we have the system of equations
\begin{align*}
x+y &= {2n+1 \choose 3} \\
3x + y &\leq n^2(2n+1).
\end{align*}
This solves to obtain at most $x=\frac{n(n+1)(2n+1)}6$ directed triangles.

The minimum is $0$ and the maximum is $\binom{2k + 1}{3} - (2k + 1)\binom{k}{2}$. Number the teams $T_1,T_2,\dots,T_{2k + 1}$. Let $f(T)$ denote the number of teams team $T$ beats.

    If $k = 1$, if $T_1$ beats $T_2$, $T_2$ beats $T_3$, and $T_1$ beats $T_3$, there are no cyclic triplets. If $k > 1$, if $T_i$ beats $T_{i + 1}$ for all $i$ between $1$ and $2k + 1$, there are no cyclic triplets, where indices are taken modulo $2k + 1$. Therefore, $0$ is the minimum.

    We now prove $\binom{2k + 1}{3} - (2k + 1)\binom{k}{2}$ is the maximum. It is enough to prove that the minimum number of non-cyclic triplets is $(2k + 1)\binom{k}{2}$. Observe that each non-cyclic triplet corresponds to exactly one team that beats the other two teams in that triplet. Therefore, each team $T$ corresponds to $\binom{f(T)}{2}$ non-cyclic triplets, and the number of non-cyclic triplets is
\[\binom{f(T_1)}{2} + \binom{f(T_2)}{2} + \dots + \binom{f(T_{2k + 1})}{2}\text{.}\]
Observe that $f(T_1) + f(T_2) + \dots + f(T_{2k + 1}) = \binom{2k + 1}{2}$, and $g(x) := \binom{x}{2}$ is convex since $g''(x) = 1 > 0$. Therefore, by Jensen's inequality,

\begin{align*}
(2k + 1)\binom{k}{2} &= (2k + 1)g\left(\frac{f(T_1) + f(T_2) + \dots + f(T_{2k + 1})}{2k + 1}\right) \\
&\ge g(f(T_1)) + g(f(T_2)) + \dots + g(f(T_{2k + 1})) \\
&= \left\lvert \text{non-cyclic triplets} \right\rvert\text{.}
\end{align*}

Equality holds if all teams win the same number of games, or if each team wins $k$ games. This is possible if $T_i$ beats $T_j$ iff $i > j$ and $2 \mid i + j$, or $i < j$ and $2 \nmid i + j$.


The Pre-Olympiad Forum should be used for two purposes:

(1) To post problems that don't fit well into any of the other categories.

(2) To post problems that you think are pre-Olympiad level but are not appropriate for Intermediate.  For a problem to be considered 'Intermediate', an Olympiad-level student should be able to solve it (or see how to solve it) within 5 minutes or so.  When in doubt as to whether your problem should be Intermediate or here, put it here.

I don't know if you know, but how are we supposed to post here?

[quote]Sorry, but only [b]moderators[/b] can post topics in this forum. [/quote]

Well, either you'll have to edit the permissions, or you'll have to make me a moderator :D

ok, thx! :)

DPatrick, do you have access to the source code too?

If yes, can you make the source field appear too when posting in beginner/intermediate? now it's only there when editing your message...

[quote="pbornsztein"]Hmmm... I do not understand the concept of pre-olympiad problems for problems from national olympiads.
Moreover, I thought that the problems from national olympiads were supposed to be post into the advanced section....

Pierre.[/quote]

I am not sure as well. I think it depends on the user's evaluation where to put a problem. So it is quite random whether a problem is put into the pre-olympiad or advanced section.
Let me provide a example. No offence regarding Belgium is meant but here it goes: The Belgium NMO might be compared with the third round in Russia, the German NMO with the fourth round in Russia but the Russia NMO (= 5th round) seems to be still a little bit harder. So I guess Belgium NMO problems are put into the pre-olympiad folder and for German problems it depends, e.g. Darij put the first round problems of the "Bundeswettbewerb Mathematik" in the pre-olympiad round and the second round in the respective advanced folders.
Maybe this is done to distinguish problems regarding its personal felt difficulty. What do you think ?  :)

ISL/ILL problems are to be posted in the advanced section by default from now on. Please move the problems into the advanced section which are not in this section yet.  :)

I think that any olympiad problem (national or not) should be put into the advanced section and not into the pre-olympiad one (otherwise, words have no meaning  :D ).
That's not a big deal that some 'easy' problems appear into the advanced section. I trust our regular posters to send really hard ones too, so that the average level would be sufficientely high....

Pierre.

P.S. Come one! Why do not offense belgium people? :D

Belgium hasn't got an olympiad. Some problems of our 'contest' have been posted in getting started, and got solved flawlessly there. Yes, of course we also have questions that are really worth being called "olympic". (I'm serious :D) But don't think you'll qualify for IMO in a big country just cuz you can solve all the questions flawlessly. :)

But I think the meaning here is: to find easier olympiad[u][i]-style[/i][/u] questions, both for fun as for good training.

Besides, doesn't it give some nostalgic feeling to have something like a beginner's corner in this? ;)

[quote="pbornsztein"]I think that any olympiad problem (national or not) should be put into the advanced section and not into the pre-olympiad one (otherwise, words have no meaning  :D ). [/quote]

Well, the forum name is the smallest difficult. We could rename it as easy olympiad problems for instance.

[quote="pbornsztein"]
That's not a big deal that some 'easy' problems appear into the advanced section. I trust our regular posters to send really hard ones too, so that the average level would be sufficientely high.... [/quote]

I do not really agree. If you put all levels of NMO/TST difficulty ranging from Belgium NMO to China TST in the advanced section you will loose the distinction of difficulty there (as there are lots of tough questions and some really easy ones). And it will be hard to distinguish the difficulty in the pre-olympiad and intermediate section as it will be almost on the same level. Hence I assume it might be better as it is done now. What do you think ?  :)

[quote="Peter VDD"][quote="ComplexZeta"]Which problems do you think should be moved? Note that I won't move any topics by TripleM. He is also a moderator of this board, and I therefore feel that I do not have the authority to move his posts.[/quote]

No need for anything to be moved urgently :) don't worry it's mainly about new ones that we will eventually post.

But I do think everyone's posts should be threaten equally, regardless of moderatorship. :?[/quote]

Well, I want that all the ISL/ILL problems which are onto the forum and are not in the advanced section yet should be moved in the advanced section. I agree with Peter that you also can move the problems which were posted by TripleM. Do you see any reasons why he should be treated differently ?

[quote="pbornsztein"]Orl : To be honest, I do not see the purpose of the 'pre-olympiad' forum, since there is already an 'intermediate' forum.

Pierre.[/quote]

When was the last time you visited intermediate, Pierre? Pre-Olympiad is of comparable level to the old ML beginner's corner, while intermediate is school level.

You can't be serious that you're going from school straight into advanced, can you? ;)

Come on. There's no way anyone can give a formula or something to decide whether a problem will be in, say, pre-olympiad or advanced. If someone posts a problem in pre-olympiad that you think should be in advanced, then fine, but don't expect it to be moved just because you feel this way. Other people disagree. Is it really worth it for you (or anyone else) to be policemen to make sure that every problem fits in perfectly? I don't think it's worth your time or mine.

Please feel free to move any of my posts. I thought some of them were probably meant to go into the advanced forum, however I thought the level of some of them were similar to the level of some posts in here, since they were from a looong time ago. In fact, if they aren't moved already, I'll move them now.

As someone who frequents the Pre-Olympiad forum, and yet rarely goes to the Advanced forums, I guess I can give my opinion.  I have never participated in any sort of math olympiad, national or otherwise, and have just started looking at these sort of problems, and I find that the ones in the Advanced forums are generally too difficult for someone like me, who finds a good amount of challenge with perhaps the first problem on a math olympiad.  Since I have just started looking at olympiad level problems, while looking through the Advanced forums, its very difficult for me to guage the difficulty of a problem... for example, I could try it and get nowhere in 1-2 hours, only to find out that the solution entails nothing that I have ever remotely encountered and was #6 on the IMO (or that level).  Also, it seems that the frequent posters in advanced have participated (even medalled) in the IMO, and the questions that they pose are ones that THEY find interesting, and I know that problems I find interesting are definetly not ones I could easily solve.

However, the intermediate forum tends to have more AIME style questions and later AMC12 level questions.  The proofs there tend to be something more often encountered in ARML.

So where does someone go who doesn't have much experience with Olympiad level questions and thus can only solve the easier ones, when it is often hard to guage the difficulty of the questions.  How can you tell whether a problem that someone created has a fairly simple solution, or whether it would challenge an IMO medallist?  Also with the sources of problems...I for one don't know which olympiads tend to be easier than others.  Sure I know that the Canadian math olympiad is a lot easier than the USAMO, but my point is that its very hard for me to find a problem in advanced that will give me a healthy challenge (I will either be able to find a solution, maybe make some progress, but even if I don't, I will be able to understand the solution and the methods used).

I am sure there are others like me who are transitioning from harder AIME problems->easier olympiad problems, and that's my opinion on what the pre-olympaid forum should entail.  But then again, if I am the only one who feels this way, then I guess we can put all olympiad problems in advanced.

Yeah, I agree with what you said. The only problems with that, is that extremely difficult problems can have very easy solutions (IMO 2003 #6 is a pretty good example, if I remember right - knowledge of basic modulos can help you understand the solution very easily). Once you know the answer to a problem, it can seem very easy, and thats probably why harder problems are posted to easier forums often. I suppose it is up to the problem poser to decide whether it is actually easy to *solve* or easy to understand the solution.

[quote="GeoMar"]So where does someone go who doesn't have much experience with Olympiad level questions and thus can only solve the easier ones, when it is often hard to guage the difficulty of the questions.  How can you tell whether a problem that someone created has a fairly simple solution, or whether it would challenge an IMO medallist?  Also with the sources of problems...I for one don't know which olympiads tend to be easier than others.  Sure I know that the Canadian math olympiad is a lot easier than the USAMO, but my point is that its very hard for me to find a problem in advanced that will give me a healthy challenge (I will either be able to find a solution, maybe make some progress, but even if I don't, I will be able to understand the solution and the methods used).

I am sure there are others like me who are transitioning from harder AIME problems->easier olympiad problems, and that's my opinion on what the pre-olympaid forum should entail.  But then again, if I am the only one who feels this way, then I guess we can put all olympiad problems in advanced.[/quote]

This message should also be delivered to [b]Pierre[/b]. That is what I meant and the pre-olympiad forum should be designed for. It should be a source for easy olympiad questions, e.g. Belgium. Medium and hard olympiad questions should be posed in the advanced section. Thus you get a suitable distinction of difficulty levels. And it is easier for people as GeoMar to evaluate the difficulty level as the advanced section does not get mixed up by so various difficulty levels. What do you think ?  :)

Hmmm... just read the introducing sentences for all sections in the index page.

I think that there would be no difficulty to evaluate the level of a problem if everyone posted the right reference (instead of 'unknown' or 'a book'), particularly for national olympiad problems.
I agree that some vietnamese problems are easy while they usually don't. But, you don't need very much experience into problem-solving to quickly learn that russian problems are usually more difficult than belgian ones, and that, in general, iranians are really hard. And so on. As the ISL problems from 30 years ago are in general quite easier than those from recent ISL.

Moreover, it is usually the way to improve when you face problems that you do not solve (at least, this is my way), and this is not a shame to do not solve a problem, even I agree that it is kind to solve a problem from time to time ;) .
I always keep the same way : I look at some problem that I feel cute or nice. I try to think about it. If I succeed that's fine. Otherwise, I hope someone will post a solution to see what I missed (idea or theorem). Then, I would be sharper to tackle the next one.

I think that, beside the reference, the only useful information is to know if this problem has a solution or not. More precisely, is it an 'unsolved' problem? A 'proposed' problem? An 'open' problem?

In my mind, the intermediate forum was intended to give 'easy' problems for beginner's, but for those who already know the basic results. And the advanced one, for all olympiad problems because, as told many times before, it is hopeless to try to find good criteria to evaluate the difficulty level for such a problem, which anyway woud be different for any two persons (look at Darij, who kill any geometrical problem and seems to be feel afraid with a combinatorical one (sorry Darij  :D ) ).

Do not forget that there is a 'College playground' too, for problems in advanced fields.
As I said before, this sounds lik a non-sense to post olympiad problems into a pre-olympiad section.
In my mind, the 'advanced section' should be called 'Olympiad section'. That's all.

Anyway, that's not a big deal....Keep the things as they are, no problem. I just think that it leads to some useless confusion in that way...

Pierre.

[quote="pbornsztein"]
I think that there would be no difficulty to evaluate the level of a problem if everyone posted the right reference (instead of 'unknown' or 'a book'), particularly for national olympiad problems[/quote]

Thank you for your interesting opinion. Yeah, the proper mentioning of sources is really a BIG problem. Sources as book, web or internet are simply invalid. What do the people think ? Is there just one site onto the web/internet or are there just 2 or 3 distinct books available world wide ? An unkown is stupid too as most users are aware for sure of the source where they took the problem from. Well, I also could say my source is: bike, car, air, shoes, journal. I think you get what I mean, don't you ? Thus please be so kind and be more specific. Otherwise Pierre's view is doomed to fail.  :)

[quote="Peter VDD"]I always post my sources... unless I really don't know them.

Some problems are here in our training papers, without reference to where they came from. So it's not always possible to know where they came from... :([/quote]

Well then write down for instance: Belgium IMO training 2004, unit/camp. number 5, problem 1.

In general I also dislike people just writing ISL. There are several problems for ISLs and right now many past ISL years are available. But even more ugly is when they just write, e.g. Kvant, Tournament of Towns or Saint Petersburg Olympiad. Have you ever thought about how many different problems these contests include, so could be please more specific and mention the year and if possible the round numbers. Thanks.  :)

Getting back on how to use this board I would just like to remaind you to use $\LaTeX$ as much as possible in your posts to make everything looks nicer for everyone else.

Also the new hide tag can be customised, like this
[hide="Solution!"]There there should be a $\LaTeX$ written solution ;) [/hide]

This is done by adding "Solution!" inside the first tag as below

[code][hide=Solution!]There there should be a $\LaTeX$ written solution ;) [/hide][/code]

For brevity: I second GeoMar's statements and his position.  I have been the best at my school for years, but that doesn't mean I'm automatically going to be seeing inside the most difficult problems or exposed to great proofs, theorems either.
 I'd in fact say that too often, the College Playground problems are easier than the ones in after-Intermediate.  Therefore, it makes sense to have an additional level here (like this) so that people like me can get used to the more advanced--IMO--techniques without ever having the need to look up a solution just to be able to solve much of any problem, like in Olympiad.  I'd still like to see a brilliant solution or even a problem with hints as to introduce me to a new insight, but some problems are just too hard; the motivation dwindles when one knows he can't find solutions personally, regardless of how much the problem lets the mather gain.

[quote="fedwinri"] I'd in fact say that too often, the College Playground problems are easier than the ones in after-Intermediate.[/quote] :what?:  :rotfl:  I hope you were kidding on that one?? I'll be surprised if I find 5 problems in CP that I solved :? While during my olympiad training I could solve many problems in Advanced Section...

[ oh well, maybe that's just cuz I'm in the first college year. it may change, though I know someone in 3rd year here who can solve advanced but not college as well... ]

Anyway, the discussion to shut this forum down stopped like eum... 6 months ago ;)

Ok the forum was created, the dispute was settled, now it's time for this topic to die :)

(requesting permission to un-announce this? letting it die off as Valentyn said is hard when it's on top...)


Specify real numbers. It should be $ 4c$; otherwise there are no solutions.

This is a contrived problem...

Add up those 3 relations.

$ a^{2}+6a+b^{2}+2b+c^{2}+4c=-14$
$ (a+3)^{2}+(b+1)^{2}+(c+2)^{2}=0$
$ (a,b,c)=(-3,-1,-2)$. [This solution set checks in the initial equations.]

$ a^{2}+b^{2}+c^{2}=14$.


I dont need the solution, just the correct way to set it up.

Armond has two solutions available in the lab, one with 5% alcohol, and another with 13% alcohol. How much of each solution should he mix together to obtain 8% alcohol?

I like table formats, but i cant get this right. Thanks!

	 Amount	percent	total
5%	x	         0.05	                .05x
13%	x	         0.13	                .13x
8% mix

$ \frac{1}{20}$ of the first is alcohol.

$ \frac{13}{100}$ of the second is alcohol.

If he adds $ x$ percent of the first, he must add $ 100\minus{}x$ percent of the second (Why? Make sure you understand this).

Can you set up the equation now?

[quote="grn_trtle"]$ \frac {1}{20}$ of the first is alcohol.

$ \frac {13}{100}$ of the second is alcohol.

If he adds $ x$ percent of the first, he must add $ 100 \minus{} x$ percent of the second (Why? Make sure you understand this).

Can you set up the equation now?[/quote]

because the only volume that is known is the result? I really dont understand :(. Can you put it in a table for me? I can visualize these alot better when i can see them in table form. Also, do you always change your percents to fractions? i change them to decimals usually...

thanks!

I usually use fractions... I don't know why, I guess I just don't like decimals.

Don't think of percentages as volumes (not exactly). The point (which is maybe why expressing as fractions is helpful) is that percentages are, in this context, limited between $ 0\%$ and $ 100\%$.
In the end our final solution must be $ 100\%$, unless I'm wrong.

I'm not sure how you want to represent this with a table...

bah, i wrote the problem wrong.

we have a final volume of 6 gallons. The last part is "how much of each should he mix together to obtain 6 gallons of solution that contains 8% alcohol.

Ok. So Let's say he adds $ x$ gallons of the $ 5\%$ alchohol and $ y$ gallons of the $ 13\%$alcohol. We know that $ .05x\plus{}.13y\equal{}6\cdot.08$ and $ x\plus{}y\equal{}6$. What do you do now?

well you can solve for y
y=6-x

then sub that in

.05x+.13(6-x)=.48
.05x+.78(.13x)=.48
.05x+.1014x=.48
.1514x=.48
x=3.17

this solution does not work, the correct set is {3.75,2.25}

what is more confusing is that this part of the book has not dealt with multiple variables, i know how to solve for them but this is review work, and i havent got there in the text...  im missing something :(

Look again at your second step. You made a mistake there. ($ .05x\plus{}.13(6\minus{}x)\equal{}.48\rightarrow .05x\plus{}.78(.13x)\equal{}.48$)

Ah, ok, I knew it seemed a little weird without some kind of total (I was making an assumption that the two solutions were equal in volume and we needed to partition them somehow into a third solution of the same volume).

yea thanks for your help. my mistake on mis typing the problem.


its not really factoring, but you could write the expression using summation notation since its a geometric series *shrug*

[quote="DiscreetFourierTransform"]This is the sum of a finite geometric series, so we can use a well known formula to get
$\frac{(1-{x^{4n}})}{1-x^{4}}$[/quote]
you mean
$\frac{(1-{x^{4n+4}})}{1-x^{4}}$

i dont think there's a certain "formula" that would give the factorization for all $n,$, but
1) if $n=-1\mod 3,$ it has 3rd roots of unity(but not 1) and 3rd roots of -1(but not -1) as roots, so $(x^{2}+x+1)(x^{2}-x+1)$ would be factors. similarly for other $n$th roots of unity,-1 where $n$ is odd. factoring out all of these should give complete factorization?
2) if $n$ is odd, it is divisible by $x^{4}+1.$ after dividing this out, we have the same thing with $x^{8n}$ instead of $x^{4n}.$ now repeat steps 1,2

[quote="junggi"]$\frac{(1-{x^{4n+4}})}{1-x^{4}}$

i dont think there's a certain "formula" that would give the factorization for all $n,$[/quote]

Actually, there is.  You were on the right track when talking about roots of unity, but here is the explicit factorization:

[b]Lemma:[/b]  $x^{k}-1 = \prod_{d | k}\Phi_{d}(x)$

(see [url=http://mathworld.wolfram.com/CyclotomicPolynomial.html]cyclotomic polynomial[/url]).  Then

$\frac{x^{4n+4}-1}{x^{4}-1}= \prod_{d | (4n+4), d > 4}\Phi_{d}(x)$

[quote="DiscreetFourierTransform"]This is the sum of a finite geometric series, so we can use a well known formula to get
$\frac{(1-{x^{4n}})}{1-x^{4}}$[/quote]

But to apply the formula don't you need $|x| < 1$?

[quote="BanishedTraitor"][quote="DiscreetFourierTransform"]This is the sum of a [b]finite [/b]geometric series, so we can use a well known formula to get
$\frac{(1-{x^{4n}})}{1-x^{4}}$[/quote]

But to apply the formula don't you need $|x| < 1$?[/quote]

No, that restriction only applies when the geometric series is infinite.

But what if x=1? and n+1 is a prime? I don't think that there is a factorization......

We are talking about the factorization of the polynomial, which is general.  And if $n+1$ is a prime then $\Phi_{n+1}(x), \Phi_{2n+2}(x), \Phi_{4n+4}(x)$ are the only factors.


logarithms
trigonometry
calculus
calculus computations

Calculate $(\ln \tan 1^{\circ})\times(\ln \tan 2^{\circ})\times......\times(\ln \tan 89^{\circ})$
:-)

[quote="shyong"][hide]$\ln(\tan 45^{\circ})=0$ ....[/hide][/quote]

hahahaha
Three years ago when I first attempted to solve it, it cost me quite a few minutes to find out that fact...

a similar question is trying to find

$\ln(\tan 1^o)+\ln(\tan 2^o)+\cdots +\ln(\tan 89^o)$

[hide]
is the answer to this $0$ since we have

$\ln(\tan(1^o)\tan(2^o)\dots\tan(89^o))=$

$\ln\left(\frac{\sin(1^o)\sin(2^o)\dots\sin(89^o)}{\cos(1^o)\cos(2^o)\dots\cos(89^o)}\right)=\ln(1)=0$

  :)
[/hide]


Diophantine equation
number theory proposed
number theory

Solve this equation   $ x,y,z \in Z$
\[ z^2\equal{}(x^2\plus{}1)(y^2\minus{}1)\plus{}2006\]

[quote="stvs_f"]Solve this equation   $ x,y,z \in Z$
\[ z^2 \equal{} (x^2 \plus{} 1)(y^2 \minus{} 1) \plus{} 2006
\]
[/quote]
This equation has infinite solution ,and I think it is very hard to find out all of them . For example we can chose $ y\equal{}1002$ then the equation is equivalent :
\[ z^2\minus{}(y^2\minus{}1)x^2\equal{}1003^2
\]
Use the Pell equation , it is easy to show that this equation has infinite solution .

[quote="ThangTongHopK41"]I think there is no big problem here
If $ x$ or $ y$ is odd then the RHS equal to $ 2$ $ (mod4)$, give a contradiction
If $ x,y$ all even then the RHS equal to $ 3$$ (mod 4)$, also impossible
This tackled the problem[/quote]
(x,y)=(1003,1002) is one of answers. its not impossible.be careful. :lol:


calculus
derivative
function
calculus computations

Show that the right derivative of function $ f$ in 0 equals 1, when
$ \begin {cases} f(x) \equal{} x^{(x^x)} \mbox{ if }x>0\\
f(0) \equal{} 0 \end {cases}$

[hide="Hint"]Take logs of the difference quotient.[/hide]

[quote="§outh§tar"]ASIDE:
Isn't there some problem about finding the limit of x^x^x...^x^...?

Does someone know the statement of that problem?[/quote] See [url=http://www.mathlinks.ro/viewtopic.php?t=223909]here[/url] and the link therein.


geometry parallelogram rectangle MATHCOUNTS AMC USA(J)MO USAMO \/closed

Hmm apparently mods got ordered to move all topics that are too hard for beginner's section. A good thing on it's own, but I think sometimes mods _really_ exaggerate in their job. :)

An example:

In a parallellogram ABCD, we have A=90.
*Show that B,C,D are also 90
*Show that AC = BD

Is this too hard for beginner's section? I don't think so... :maybe:

I think it is even too easy for beginners' section :D

My first thought too. But we don't have any 'kindergarten' or anything alike, so that's all for the beginner's section.

As for the voting, may I guess? Dpatrick disagrees; you, me, valentin and Ravi B agree? :) Just a guess...

[quote="Peter VDD"]Is this too hard for beginner's section? I don't think so... :maybe:[/quote]
While the result is very clearly and intuitively obvious, it's not necessarily easy to show in a rigid manner.

I take into account who replies early in a thread to gauge a thread's difficulty.

Remember that the forum membership includes persons as young as nine years old, and definitely includes a lot of school pupils who have not had any course in algebra or in geometry. Something has to be posted at their level, which is the Getting Started level, and problems that are harder ipso facto go to a higher level, e.g., Intermediate level.

There are questions for which that's true, confuted, but not here:

A = C = 90 so B = D = (360-180)/2 = 90 so we got a rectangle

For the second part, pythagoras gives us immediate result.

[quote="tokenadult"]I take into account who replies early in a thread to gauge a thread's difficulty.[/quote]
I don't get this? can you explain me please? :?

[quote]Remember that the forum membership includes persons as young as nine years old, and definitely includes a lot of school pupils who have not had any course in algebra or in geometry. Something has to be posted at their level, which is the Getting Started level, and problems that are harder ipso facto go to a higher level, e.g., Intermediate level.[/quote]

... I don't think there are many 9yo pupils on the forums, tokenadult. Anyway those don't need to "get started", that's the age they can just count to 1000 and learn how to divide 532:13 and stuff like that. There's simply no problem solving for this level, since there's no problem they can already solve. (unless they're very talented, and in that case they'll solve the problem anyway)

First algebra courses come at 12 year (7th grade), and that's the age they know sufficient algebra and geometry to solve these problems.

[quote="Peter VDD"][quote="tokenadult"]I take into account who replies early in a thread to gauge a thread's difficulty.[/quote]
I don't get this? can you explain me please? :?[/quote]

What I mean is that if I see most answers to a problem-solving thread are being posted by people with high levels of experience, and NOT by beginners, I doubt that the thread is at Getting Started level.

[quote="Peter VDD"][quote="tokenadult"]Remember that the forum membership includes persons as young as nine years old, and definitely includes a lot of school pupils who have not had any course in algebra or in geometry.[/quote]

... I don't think there are many 9yo pupils on the forums, tokenadult.[/quote]

I recently read a thread about a nine-year-old (she may be ten years old by now, in the Northern Hemisphere summer) who has taken AoPS online classes. There are several eleven-year-olds on the forum, some known personally to me in offline life. The point is that there has to be a set of easiest problems for the lowest-level forum: it shouldn't be any trouble to look at a forum one level higher if what one is looking for is harder problems.

Moreover, I have recently seen site owner Richard Rusczyk post a thread mentioning that the difficulty level of Intermediate Topics has increased greatly recently, which suggests that that forum needs to have some easier threads "promoted" into it.

[quote="Peter VDD"]There's simply no problem solving for this level, since there's no problem they can already solve. (unless they're very talented, and in that case they'll solve the problem anyway)[/quote]

I have seen numerous counterexamples in the problem sets used in elementary school in China and in middle school competitions (notably the AMC 8 and Mathcounts) in the United States. There is much problem-solving practice that can be obtained by a learner with no knowledge of algebra or geometry IF the problem-poser does a good job of writing the problem.

[quote="Peter VDD"]First algebra courses come at 12 year (7th grade), and that's the age they know sufficient algebra and geometry to solve these problems.[/quote]

No, first algebra courses do not come at the same age in all countries. Again, I am certain, because I have asked about this many times on this site, that there are many participants here who have little or no acquaintance with algebra, and quite a few more who have no acquaintance with proofs in geometry. I learned those subjects at an unusually young age (for the United States) in my schooling, as has my son through homeschooling, but there is nonetheless a large group of participants on the site who would be glad to see easier problems on Getting Started, and corresponingly other participants who would be glad to see some problems of the level now posted in Getting Started rather appear in Intermediate.

I personally think that some of the reasons for moving posts are not quite what I'd expect (in my opinion problem solving is a completely different subject to math, and thus most problems without "prove" shouldn't even be on here), but I'm not that worried about it. If a moderator thinks it should be moved, then it can be moved, and theres no point in posting that you disagree every time it happens.

[quote="tokenadult"]What I mean is that if I see most answers to a problem-solving thread are being posted by people with high levels of experience, and NOT by beginners, I doubt that the thread is at Getting Started level.[/quote]

Tokenadult, how are those "beginners" as you say, supposed to create their own problems already? If I post something in beginners, that's something I'd have been able to solve in grade 8 or higher.

Anyway, tokenadult, the problem I'm having with this is:
* The beginner's section is for those, so for us it's useless.
* The intermediate section, you claim, is for pre-olympiad students. So like the multiple choice-like questions.
* College uses theorems we've never heard of..
* So what rests us? Only advanced.
Belgian Olympiad and Chinese Olympiad simply don't fit in the same category... If you want it to be split like that, ok, but then the more experienced problem solvers would really like some extra categories of difficulty... now it's all sticked together.
And no, the intermediate forum hasn't proven a real solution. :( We'd need to have the advanced turn into like Moderate (small olympiads), Advanced (all below IMO), Challenge (IMO, USAMO and higher)  or something.

Don't get me wrong tokenadult, I'm not criticizing you or anything. I'm only saying that you're taking all the moderate stuff to the advanced section, and it's quite boring to have to open 10 topics before finding the right difficulty level :(

[quote]* The beginner's section is for those, so for us it's useless.[/quote]

Well to me all of the Advanced Forums are useless... So should I just start trying to get them to lower their problem level?

[quote]* The intermediate section, you claim, is for pre-olympiad students. So like the multiple choice-like questions.[/quote]

Yes, the intermediate should be for pre-olympiad.  Anything up at olympiad level should probably go in advanced... unless it is unusually easy for an olympiad question.

[quote]* College uses theorems we've never heard of..[/quote]

You use theorems I ve never heard of  ;)

[quote]* So what rests us? Only advanced. [/quote]

The people on this forum should be roughly divided into 3 different groups: beginner, intermediate, and olympiad level.  Beginner is just getting exposed to problem solving.  Intermediate is those who are a little experienced and are almost at the point where they can start looking at easy olympiad problems.  Advanced is anything above that.  So I guess that you are advanced.  You are just going to have to deal with the fact that you are too smart to be a beginner anymore( I know its hard to accept  ;) ).  But that doesn't mean that the rest of the ppl are advanced.  Like I said there should be about 3 groups.

Why are you so intent on raising the level of the beginner section?  Even if it is raised to say what the intermediate should be you will still not have questions that challenge you.

[quote="Peter VDD"]A = C = 90 so B = D = (360-180)/2 = 90 so we got a rectangle.[/quote]

Why? Why does A=C? Why does B=D? Why do B and D=(360-180)/2?

[quote="Peter VDD"]Tokenadult, how are those "beginners" as you say, supposed to create their own problems already? If I post something in beginners, that's something I'd have been able to solve in grade 8 or higher.[/quote]

They have managed quite well up until now. I don't see why that should change just because AoPS has merged with MathLinks.

[quote="Peter VDD"]Anyway, tokenadult, the problem I'm having with this is:
* The beginner's section is for those, so for us it's useless.
* The intermediate section, you claim, is for pre-olympiad students. So like the multiple choice-like questions.
* College uses theorems we've never heard of..
* So what rests us? Only advanced.
Belgian Olympiad and Chinese Olympiad simply don't fit in the same category... If you want it to be split like that, ok, but then the more experienced problem solvers would really like some extra categories of difficulty... now it's all sticked together.
And no, the intermediate forum hasn't proven a real solution. :( We'd need to have the advanced turn into like Moderate (small olympiads), Advanced (all below IMO), Challenge (IMO, USAMO and higher)  or something.[/quote]

Keep in mind that this site is not an olympiad site. It is the Art of Problem Solving, not How to Win the IMO. The goals are very different. The Art of Problem Solving should have something for everyone. There is no reason that smart people who like math should come to this site and not be able to solve anything because the beginner's section has turned into an easy olympiad section. That is not the point.

Easy olympiad problems have been in intermediate topic for a long time. Few people have criticized this. Most olympiad problems belong in advanced. That's the way it has always been.

[quote="ComplexZeta"]Keep in mind that this site is not an olympiad site. It is the Art of Problem Solving, not How to Win the IMO. The goals are very different. The Art of Problem Solving should have something for everyone. There is no reason that smart people who like math should come to this site and not be able to solve anything because the beginner's section has turned into an easy olympiad section. That is not the point.

Easy olympiad problems have been in intermediate topic for a long time. Few people have criticized this. Most olympiad problems belong in advanced. That's the way it has always been.[/quote]As far as AoPS-MathLinks is or is not an olympiad site, I both agree and disagree with you ComplexZeta. It is my hope that people that start in Getting Started (for what getting started? ;)), move on to Intermediate (it's intermediate to what? ;)) and then to Advanced. So basically it's a half-olympiad site :P

I also understand your worries Peter, but try to post new topics out of the Getting Started forums, and watch more intermediate / advanced.
It's most probable that we shall create a fourth division in the future, given the way things evolve, but that only after all the people have finally used with the merge, and the number of new forums, so that can navigate easily.

[quote="joml88"]Well to me all of the Advanced Forums are useless... So should I just start trying to get them to lower their problem level?[/quote]You can increase your level. I can not decrease mine...

[quote="joml88"]The people on this forum should be roughly divided into 3 different groups: beginner, intermediate, and olympiad level.  Beginner is just getting exposed to problem solving.  Intermediate is those who are a little experienced and are almost at the point where they can start looking at easy olympiad problems.  Advanced is anything above that.  So I guess that you are advanced.  You are just going to have to deal with the fact that you are too smart to be a beginner anymore( I know its hard to accept  ;) ).  But that doesn't mean that the rest of the ppl are advanced.  Like I said there should be about 3 groups.[/quote]Jolm, look at the number of posts/topics in each of the sections, and you'll know very soon how many people there are in each of the groups. Just asking a little balance...

As for the rest, I can only say one thing:

On the old mathlinks site it started with Beginner's Corner. (now the other problems forum in the advanced section). That was pretty hard to start indeed. But that's the way I learnt it. Indeed I've spent hours with pencil and paper in front of my screen, thinking but finding nothing. It's the best training I've had, and the only thing that made me advanced. And I'm very thankful to Valentin, who made the right decision to start at that level.
If there had been a beginner's section, and I'd have started there, where would I be now? Perhaps good in intermediate? :(

[quote="mecrazywong"]Actually I can find no forum in Mathlinks match my level....
Intermediate is too easy for me; advanced section is a little bit too difficult for me :([/quote]
Yeah, good ole' beginner's corner..
Well that's why I was asking for an easy advanced (for people like you), a medium advanced (standard olympiad players), and one just for though challenges (for the real pro players), if you really want to kill your brains on a beautiful problem. :)

Gonna have to wait and see what they'll do though :P

[quote="mecrazywong"]Actually I can find no forum in Mathlinks match my level....
Intermediate is too easy for me; advanced section is a little bit too difficult for me :([/quote]

Many people have your problem. For many people, they are not challenged enough by one forum, but find the next rung on the ladder too challenging. I do some problems in Getting Started and don't get too challenged, but when I visit the Intermediate forum, I can only find a few problems suited for myself. (Either that or it's just the fact that I haven't gone there in a while or spent much time on math  :? ) But if you're in this situation, the good thing about the forums is that they're not just limited to Getting Started, Intermediate, Advanced and College. You can visit the AMC forums or another competition forum to find things that fit your level perfectly. There are also bound to be some problems your level in both forums your stuck between, as in your case, easy problems for the Advanced forum and more difficult problems in Intermediate.

[quote="yif man12"]But if you're in this situation, the good thing about the forums is that they're not just limited to Getting Started, Intermediate, Advanced and College. You can visit the AMC forums or another competition forum to find things that fit your level perfectly.[/quote]

Can you point me to some of those forums? Know anywhere they got IMO-level (or a little below)? I always used mathlinks because it was the only good olympiad site on the web... or at least the only one I could find :blush:

All the MathLinks participants are still here, as best I can tell, and they are still posting problems unless they are busy during the Northern Hemisphere summer. And there have always been a lot of people on the old AoPS posting problems at the level of just-starting-IMO, perhaps mostly posting those problems in the Intermediate forum (mistakenly, in my opinion) or Advanced Forum (correctly, on the principle of posting to a HIGHER forum in cases of doubt). There are differences from country to country in what topics are learned first by competitors in problem-solving competitions, so perhaps what looks hard to participants on the new merged AoPS-MathLinks forums is problems that are based on a different order of introducing topics in IMO training from what you have in your country.

The problems are still here, and over time we will all get used to posting them in the proper forums. And everyone is still welcome to post problems, which I hope to do more often if I can take time from these metadiscussions to look up good problems in books I have from China, the United States, and Europe.

Tokenadult, I fully understand you. But I said my point and I think it was answered:[quote="Valentin Vornicu"]It's most probable that we shall create a fourth division in the future, given the way things evolve[/quote]

The only thing I had against it is that olympiad questions of all levels get pushed into 1 section, without any differentiation :) So if that will get solved by making additional category/categories, go ahead. :)

Only 1 thingie:
[quote]so perhaps what looks hard to participants on the new merged AoPS-MathLinks forums is problems that are based on a different order of introducing topics in IMO training from what you have in your country. [/quote]
We only learnt induction and modulo in IMO training, all the rest has been learnt here, on this great site :D

that is correct peter. From what I can tell currently, besides countries from top 10 at IMO (which seem to be the same each year, with small variations) the others do not an extensive IMO training program, not even for the selected team of 6, or if they have, the level is low. There are some exceptions, but in general that is the fact.

Even in Romania, the training is very short, and usually, it reaches far beyong the IMO topics, leaving many IMO-areas uncovered, thus the big variance in our team's results in the past 10 years (and also the variation of the scores inside the team - you can see in the case of China, USA, Russia or Bulgaria, that people tend to have more or less the same score, or very close to their team average score - that denotes, in my opinion, a good training program).


The pages of a book are numbered consecutively, beginning with page 1. If 1020 digits are used to number the pages, how many pages are in the book?

From $ 1\minus{}9$, $ 9$ digits are used.
From $ 10\minus{}99$, $ 2\cdot90\equal{}180$ digits are used.
So now we have $ 1020\minus{}180\minus{}9\equal{}831$ digits. Since the rest of the book contains $ 3$ digit numbers, we divide by $ 3$ to obtain $ 277$, and our answer is $ 100\plus{}277\minus{}1\equal{}\boxed{376}$.


[size=150]A group of students decided to by a cricket bat worth Rs.170 to 195. But, at the last moment two students backed out of the decision so that the remaining students had to pay one rupee each more than they had planned. What was the price of the cricket bat if the students paid equal share[/size][/quote]

:blush:

 :rotfl:

[hide]try it assuming no. of people as n and cost as x[/hide]

[quote="gmslinger"]how would you set up an algebraic equatoin if the total has to be between 170 and 195, rather than a set amount??? Can someone please help me, i'm just a beginner!!![/quote]

if you're just a beginner, don't go to the Getting Started forums, it's a misnomer, go to the middle school forums :X .

[hide="answer"]
180 has a lot of factors, so I tested it out first, and it works.

(20 people originally.)
[/hide]

But there's a catch: The question didn't say the price of the cricket bat was integral. So there could be lots of answers right? (Or am I wrong?)

I've posted the same question as well....some sqroot thing comes up somewhere and then you have to work out the possible values...not too sure,long time back.

[hide="Full solution"]Let $p=$ the price, $x=$ the number of people, and $y=$ the price each person originally planned to pay.  From the given information, we have
$p=xy$
$p=(x-2)(y+1)$
Then $xy=xy+x-2y-2\Rightarrow x=2y+2$.  So $p=y(2y+2)=2y^{2}+2y$.  Testing values for $y$, we find that only $y=9$ puts the price in the desired range, which gives $p=180$.[/hide]


Every body at my school is always talking about how the chem ap test is the hardest ap test of them all im just worndring how you guys that have already taken it thought of it?

nope!!
its not hard.
just be relaxed and you'll do fine... :)

one month till i take ap chem test!!! wooooooooooooooo

AP chemistry is not the hardest. Environmental science is harder. So are gov, US history and world history.

http://collegeboard.com/prod_downloads/student/testing/ap/sumrpts/2005/xls/national_summary.xls

But chem is pretty easy in my opinion.

I can answer about 3/5-2/3 of the questions even though I've never taken a formal chem class; and I 've only read high school chemistry on my own.

[quote="RiemannZetaFunction"]Im not really woried about the multiple guess part more about the free answers and essays.[/quote]

Personally, I think the FR section is a lot easier than the MC section. You get the equations and everything; for instance, on the AP Chem mock test we recently had there was an FRQ on Electrochemistry, but we hadn't learned it yet. So I really had no idea what I was doing. But using the equations and some common sense, I think I was able to pull a decent score on that question (a similar thing occured on our AP Physics B mock test last year with E&M stuff).


i had an idea...maybe instead of taking the AIME in the morning, it could be recommended to schools that they make us take it in the afternoon...because i'm sure that i, and a lot of other kids, perform much worse when it's bright and early... :maybe:
The proof of this?  I spent 40 minutes on number 3, then, after going back to it during the last 10 minutes, spent about 30 seconds on it... :ninja: gets even better: i didn't do number 1...period... :?: :!:

a few thoughts though...i thought this aime was imbalanced because, if you'd wanted to, you could have used casework/brute force to solve every single problem, at least up to number 11...

Also, too much computation on number 11...i set up the right expression to evaluate, and ended up multiplying wrong, because i had to perform about 10 operations with 3 digit numbers...

I also heard that number 2 screwed a bunch of people up, because of the wording of the last moving person...but that's a reading error and you can't really fault the aime for that....

Also, not enough problems relied on algebra...btw, where was the geometry?!...i didn't see any easy ones at all...WAY too many counting problems, i think a total of 6 or something, with 4 in the first 10 :!: (there's your casework for you)...sequences and series galore, too...

Hmm...i know a bunch of ubersmart people (those that normally score 11+) who scored about 4 or 5 problems lower than normal  :huh: ....so i guess that means, overall, i'm expecting a 6/7 cutoff (leaning toward 6)...hopefully, i can make it...but, i still dunno what exactly are the correct answers to the counting problems...so, here's to crossing my fingers  :wink:

We did get to take it in the afternoon 2-5 PM

Luckily for me, I was the only person in my school to qualify this year, so I was allowed to take it pretty much any time I wanted.  I decided on 10:30-1:30 and my score improved a lot since last year (when I took it at 8 in the morning) so I think that taking it later in the day can only be beneficial.  It would be nicer for more schools to offer it in the afternoon, though for many of them the morning may be the only feasable time.

This has nothing to do with people not at your school... And I was under the impression that most people work better in the morning. I find it [i]extremely[/i] annoying that the USAMO is so late. I wish it could be like 8:00-12:30.

And I took it from 8-11. :D Yay!

i took it from 8-11. :mad: maybe those stupid mistakes would've gone away if i took it in the afternoon... :P

I do a lot better with some warm up problems, like the Math League problems that used to coincide with the AIME dates for a couple years past. We would take the NEML, and then do the AIME afterwards.

I do best either late at night (6-11) or at late morning (10-2). Unfortunately I took it at 3-6, the time when you are most sleepy. Thus, 6-7 (I might have bubbled one wrong.

Just get your school to take it when you want.

there really isn't much else you can do about it.

it isn't necessarily proportional though. i find that i'm more on edge in the morning while less likely to make mistakes, and lazy in the afternoon.


conics
ellipse
geometry
ratio
geometry unsolved

Let $ A_1A_2, B_1B_2$ be the ellipse $ \mathcal E$ major and minor axes (given). First, project the ellipse to a circle by a parallel projection, preserving area ratios. That is, draw a circle $ (P)$ with diameter identical to the ellipse major axis $ A_1A_2,$ radius $ r \equal{} \frac {A_1A_2}{2}.$ Denote $ a$ the line $ A_1A_2.$ Perpendicular to $ a$ through the midpoint $ P$ of the segment $ A_1A_2$ cuts the circle $ (P)$ at $ B_1', B_2'.$ Then find projection of the given line $ l$: let $ b, b'$ be parallels to $ a$ through $ B_1, B_1'.$ The given line $ l$ cuts $ a$ at $ U$ and $ b$ at $ V.$ Perpendicular to $ a$ through $ V$ cuts $ b'$ at $ V'$ and $ l' \equiv UV'$ is the projection of $ l.$

 Construct equilateral triangles $ \triangle D'E'F', \triangle X'Y'Z'$ with $ D', X' \in l'$ and incircle $ (P).$ This gives the smallest possible area ratio $ \frac {S(\triangle D'E'F')}{S(\odot(P))} \equal{} \frac {S(\triangle DEF)}{S(\mathcal E)}$ (well known and the proof is trivial.) That is, draw a circle concentric with $ (P)$ and radius $ 2r \equal{} A_1A_2$ intersecting $ l'$ at $ D', X'.$ The lines $ D'P, X'P$ cut $ (P)$ at $ K', Q'$ on the opposite side of $ a$ than $ D', X'.$ Tangents to $ (P)$ from $ D'$ cut its tangent at $ K'$ at $ E', F'$ and similarly, tangents to $ (P)$ from $ X'$ cut its tanget at $ Q'$ at $ Y', Z',$ such that the $ \triangle D'E'F', \triangle X'Y'Z'$ are both equilateral.

Now, project the 2 equilateral triangles back: Perpendiculars to $ a$ through $ D', X'$ cut the original line $ l$ at $ D, X.$ Lines $ E'F', Y'Z'$ cut $ a$ at $ L, S$ and the line $ b'$ at $ M', T'.$ Perpendiculars to $ a$ through $ M', T'$ cut $ b$ at $ M, T$ and the lines $ LM, ST$ are the inverse projections of the lines $ LM' \equiv E'F', ST' \equiv Y'Z',$ i.e., the lines $ EF, YZ.$ Perpendiculars to $ a$ through $ E', F'$ cut $ LM$ at $ E, F$ and perpendiculars to $ a$ through $ X', Y'$ cut $ ST$ at $ Y, Z.$


calculus
integration
calculus computations


Does anyone know what day ARML tryouts are? I know its February, but anything more specific? Thanks

According to the announcement at the last MML meet, tryouts are on March 2 this year.

[quote="Pineappleperson"]who should I contact if I want to go to ARML[/quote]

You basically just show up at the tryout. If you want more information, contact Mr. Badoian at badoianm AT hotmail DOT com, or Mr. Curry at yyoda AT concentric DOT net (I believe those are correct, if not Mr. Curry's is on the arml website as the Eastern Site Director).

I'll try to do my best here. We leave Canton at around 9 AM on the Thursday before the competition, and arrive at around 6 PM, depending on traffic. The total cost of the trip is 200 dollars, not including at least 4 meals that you will have to pay for on your own (more depending on how much of the cafeteria food you want to eat and whether you want lunch after a big breakfast on Friday).

We leave right after the competition ends, around 5 PM Saturday afternoon, and get back to Canton at like 2:30 AM Sunday morning.

[quote="baozhale"]oops, guess not february. since we leave from Canton, I'm guessing tryouts are at Canton High? Thanks.[/quote]

Yes; Phillips Academy is also a tryout location.

[quote="perfect628"]I can't go... :([/quote]

stupid roxbury latin


geometry
incenter
trigonometry
inradius
ratio
angle bisector
geometry proposed

$I$ is incenter of $\triangle ABC$. If  $AI=x$, $BI=y$ and $CI=y$, then determine $r$ .
Please help because i strived to much i couldn't solve.

Here is important relation $ AI=r/sinA/2 $ :?

Must to find a,b,c or R,r,s. but $\sin \frac{a}{2}$ depends of a,b,c.It is O.K. ???

[quote="osmantelli"]I is incenter of ABC triangle. If AI=x, BI=y and CI=y, then determine r .[/quote]

If r means the inradius of triangle ABC here, then we get the cubic equation

$r^2\left(\frac{1}{x^2}+\frac{1}{y^2}+\frac{1}{z^2}\right)+2\frac{r^3}{xyz}=1$.

This cubic equation is (in general) unresolvable by compass and ruler.

Let me quickly explain how to prove the above equation $r^2\left(\frac{1}{x^2}+\frac{1}{y^2}+\frac{1}{z^2}\right)+2\frac{r^3}{xyz}=1$:

The incircle of triangle ABC has the center I and the radius r; thus, if this incircle touches the side CA of triangle ABC at a point Y, then IY = r and $IY\perp CA$, and thus < AYI = 90°. On the other hand, $\measuredangle IAY=\frac{A}{2}$, since the point I, being the incenter of triangle ABC, lies on the angle bisector of the angle CAB. Hence, in the right-angled triangle AYI, we have $\sin\measuredangle IAY=\frac{IY}{AI}$, so that $\sin\frac{A}{2}=\frac{r}{x}$.

But by the sum of angles in triangle ABC, we have A + B + C = 180°, so that

$\left(90^{\circ}-\frac{A}{2}\right)+\left(90^{\circ}-\frac{B}{2}\right)+\left(90^{\circ}-\frac{C}{2}\right)=270^{\circ}-\frac{A+B+C}{2}$
$=270^{\circ}-\frac{180^{\circ}}{2}=180^{\circ}$.

Also, the angles $90^{\circ}-\frac{A}{2}$, $90^{\circ}-\frac{B}{2}$ and $90^{\circ}-\frac{C}{2}$ are all positive (since $90^{\circ}-\frac{A}{2}>0^{\circ}\Longleftrightarrow 90^{\circ}>\frac{A}{2}\Longleftrightarrow 180^{\circ}>A$, what is clearly true, and similarly for $90^{\circ}-\frac{B}{2}$ and $90^{\circ}-\frac{C}{2}$). Hence, these angles $90^{\circ}-\frac{A}{2}$, $90^{\circ}-\frac{B}{2}$ and $90^{\circ}-\frac{C}{2}$ are the angles of a triangle. Thus, by the relationship $\cos^2 x+\cos^2 y+\cos^2 z+2\cos x\cos y\cos z=1$ which holds for the angles x, y, z of any triangle,

$\cos^2\left(90^{\circ}-\frac{A}{2}\right)+\cos^2\left(90^{\circ}-\frac{B}{2}\right)+\cos^2\left(90^{\circ}-\frac{C}{2}\right)$
$+2\cos\left(90^{\circ}-\frac{A}{2}\right)\cos\left(90^{\circ}-\frac{B}{2}\right)\cos\left(90^{\circ}-\frac{C}{2}\right)=1$.

In other words,

$\sin^2\frac{A}{2}+\sin^2\frac{B}{2}+\sin^2\frac{C}{2}+2\sin\frac{A}{2}\sin\frac{B}{2}\sin\frac{C}{2}=1$.

Now, using $\sin\frac{A}{2}=\frac{r}{x}$ and the similarly obtainable equations $\sin\frac{B}{2}=\frac{r}{y}$ and $\sin\frac{C}{2}=\frac{r}{z}$, this becomes an equation in the ratios $\frac{r}{x}$, $\frac{r}{y}$, $\frac{r}{z}$ and takes the form

$r^2\left(\frac{1}{x^2}+\frac{1}{y^2}+\frac{1}{z^2}\right)+2\frac{r^3}{xyz}=1$.

  Darij

Levi,I think my solution with $AI=\frac{r}{sinA/2}$ works,because using the well known identity with $sinA/2$ I
obtain almost the same thing as Darij.What do you think? :?

Abviously ! See at the ineq. $\sum m_a\le 4R+r$

please, can you show cos^2 x+cos^2 y+cos^2 z+2cos xcos ycos z=1 equation ?
Because i tried this equation in triangles , which its lenght of edge are 5-6-7 and 3-4-5, but this equation didn't suppose these triangles. Maybe i made mistake therefore i will try again.  please prove this equation.  Thanx for everything.


How do you move text on to the next line in LaTex- not the forum.

I want to make my running header more than one line so it doesn't look so jumbled.


Someone post a solution to this nice problem. I would love to see them.

Someone post a solution please. No solutions?????

[quote="Agr_94_Math"]If $ A \plus{} B \plus{} C \le \pi$,  Prove that $ 1 \plus{} 2cos(A \plus{} B)cos (B \plus{} C) cos (C \plus{} A) \ge cos^2(A \plus{} B) \plus{} cos^2 (B \plus{} C) \plus{} cos^2 (C \plus{} A)$.

It is somewhat nice inequality. So why no takers?[/quote]
Try $ A\equal{}\minus{}\frac{5\pi}{4}$ and $ B\equal{}C\equal{}\frac{\pi}{4}.$ :wink:

Sorry arqady, take $ A,B,C \ge 0$. Sorry for not specifying.


While staying inside the $ \text{\LaTeX}$ graphicx environment (or perhaps epic or eepic), how can you produce

- a filled black rectangle?

- a filled gray rectangle?

- a checkerboard pattern with alternating black and white squares?

Assuming the first two requirements are to create the third, how about creating a blank board with [url=http://tug.ctan.org/cgi-bin/ctanPackageInformation.py?id=chessboard]the chessboard package[/url] which is included with MiKTeX?

I just tried using \multiput to put so many lines so close together into a square that it prints as black. A pretty clumsy way to do things, but it does seem to work.


calculus
integration
trigonometry
calculus computations

How exactly does one find the the indefinite integral of 1+cos(3x)^3/2  ... after I've fiddled around with identities i've come up with nothing simpler to integrate, plus I have no idea what to do with  :sqrt:  :^3:

[quote="shaunamack"]I have no idea what to do with square root cubed[/quote]
Hint: $1+\cos 2y=2\cos^2 y$


factorial
function
vector
combinatorics theorems
combinatorics

Does anyone know a nice formula for distinct combinations of items, or do you have to do it case-wise?  I know there is one for distinct permutations, but that's easy...

The number of combinations of n objects, selected from a set of k objects, that are unique.  For instance {x,x,y} and {x,y,x} are the same thing.  A couple of problems:

Find the number of distinct combinations of 5 letters from the word "MISSISSIPPI"

Find the number of possible hands in "go fish" (5 cards drawn from a standard deck, suits do not matter).

BTW, I think if there is a relatively "nice" way to solve these problems, the formula would involve some sort of nested factorial, summation, or product.

Hmmm... Sounds like generating functions to me.
Two years ago, maybe I could have figured out something, but I'm completely out of practice now.
But perhaps an approach through generating functions could work?

I think everything is much easier. Consider the taking (k)C(n+k) . This is the combination sign. Now, to the vector $x = (x_1,x_2,\ldots,x_k)$ put in a corespondence  a new vector $F(x) = (x_1,x_2-1,\ldots,x_k-k+1)$. You have a bijection of what you needed.

Er... Sorry. Things still look a little dull to me these days. Could you please explain? I don't get it.

There is no explicit formula for the general case. It, however, bijects to:

$a_1 + a_2 + ... + a_k = n | 0 \leq a_i \leq m_i$

Where n is the total number of items you want to choose, there are k groups of items, and there are $m_i$ of item i. This allows you to basically exploit all of the special cases where the problem is reducible to something with an explicit formula.

Answer for the mississippi problem.
It is the co-efficient if $x^5$ in
$(1 + x + x^2 + x^3 +x^4)^2(1 + x + x^2)(1+x)$

In general  if r things have to be chosen from n things out of which l are of one kind,k are of second kind...
The no. of ways in which this is possible is the co -efficient of $x^r$ in $(1+x+x^2+x^3+...x^l)(1+x+x^2+x^3+...x^k)....$


Could someone give me some pointers on solving clock problems such as the ones on MC?
Thanks.

The general formula for clock problems ( I assume you mean the angle formed by the hour and minute hand) is:
$ |30h\minus{}5.5m|$
This formula is derived like so:

The hour hand moves 30 degrees an hour.
$ 30h$
This means that the minute hand moves 6 degrees a minute
$ 30h\minus{}6m$
But since the hour moves half a degree every minute $ \frac{30}{60}$
$ 30h\plus{}.5m\minus{}6m$
Gives us
$ 30h\minus{}5.5m$
Due to the fact that it could be negaitve we make it absolute value
$ |30h\minus{}5.5m|$

Problems
1)What is the acute angle formed by the hands of the clock showing 4: 30
2) What is the [b]obtuse [/b] angle formed by the hands of the clock showing 3:02

Challenge
1) What is the first time between 4 and 5 that has an angle of 119


Don't post the same problems over again.

It doesn't help that some people find it rude when people come here just to expect others to do their homework for them.


matt276eagles as you can see from tµtµ and dule_00 induction can be used directly. nice solution.

Fermat little theorem says that $a^{p-1}\equiv 1\mod p$ for prime $p$ with $a$ not divisible by $p$.  Euler-phi is a generalization that says $a^{\phi(m)}\equiv 1\mod m$ for $\gcd(a,m)=1.$


inequalities
trigonometry
LaTeX
inequalities solved

Prove that in every triangle $ABC$, we have inequality
$\sin^2A+\sin B\sin C\leq\frac{25}{16}.$

The general inequality is
\[ \sin^2A+\lambda \sin B\sin C\leq 1+\frac{\lambda}2+\frac{\lambda^2}{16}. \]
$0\leq \lambda \leq 2$.

[b]To show a more general case, first fix alpha = t with 0 < t < 2.

Then consider S = sinA^2 + t.sinB.sinC. From part 1, S = S(y) = -4.y^2 + (4 + t).y where y = (cos(A/2))^2. And it

is quite clear that maximum of S occurs at y = (4 + t)/8 and S((4 + y)/8) = (4 + t)^2/16 = 1 + t/2 + t^2/16 as

claimed.[/b]

Make your posts more readable by learning to use $\text{\LaTeX}{}$.

We need to prove that: $P=sin^{2}A+asinBsinC\le 1+\frac{a}{2}+\frac{a^2}{16}$.
We have: $asinBsinC\le a(\frac{sinB+sinC}{2})^2=\frac{a}{4}(sinB+sinC)^2\le a sin^{2}{\frac{B+C}{2}}$
because $sinB+sinC=2sin{\frac{B+C}{2}}cos{\frac{B-C}{2}}$
     and: $cosA\le 1$.
So $P\le sin^{2}A+acos^{2}{\frac{A}{2}} (1)$
Let $sin^{2}{\frac{A}{2}}=x , cos^{2}{\frac{B}{2}}=y$ then
$\Large (1)$ become $P\le 4xy+ay=4(1-y)y+ay=-4y^2+(a+4)y$.
It's easy to prove that : .....


Δύσκολη αν δεν την έχετε ξαναδεί, αλλά δεν θέλει ιδιαίτερες γνώσεις.

Έχουμε μια σκακιέρα 1000x1000. Θα μολύνουμε αρχικά ορισμένα τετραγωνάκια της σκακιέρας. Μετα ο ιός μεταδίδεται ακολουθώντας τους ακόλουθους κανόνες:

1) Ένα μολυσμένο τετραγωνάκι παραμένει πάντα μολυσμένο.
2) Ένα μη μολυσμένο τετραγωνάκι μολύνεται αν και μόνο αν έχει τουλάχιστον δυο μολυσμένα γειτονικά τετραγωνάκια. (Ως γειτονικά τετραγωνάκια εκλαμβάνονται μόνο τα (το πολύ) 4 τετραγωνάκια που βρίσκονται πάνω,κάτω αριστερά και δεξιά.)

Ποιος είναι ο μικρότερος αριθμός τετραγώνων που μπορούμε να μολύνουμε αρχικά ώστε στο τέλος να μολυνθεί όλη η σκακιέρα;

[quote="gpapargi"]Κάτι που έμαθα διαβάζοντας φυσική είναι ότι πολλά προβλήματα απλοποιούνται κατά πολύ αν εντοπίσεις τις λεγόμενες «διατηρήσιμες ποσότητες».[/quote]

Δεν διάβασα με λεπτομέρεια τη λύση και δεν ξέρω αν σου ξέφυγε κάτι, αλλά η ιδέα και μόνο αξίζει 12 points! Well done :first:

Cheerio,

Durandal 1707

[quote="gpapargi"]Κάτι που έμαθα διαβάζοντας φυσική είναι ότι πολλά προβλήματα απλοποιούνται κατά πολύ αν εντοπίσεις τις λεγόμενες «διατηρήσιμες ποσότητες».
Φαίνεται πως σε αυτό το πρόβλημα η «διατηρήσιμη ποσότητα» είναι το «μήκος της ακτογραμμής» του πλέγματος των μολυσμένων τετραγώνων μετρημένο σε πλευρές ενός τετραγώνου. Σε αυτή την ακτογραμμή συμμετέχουν και οι εσωτερικές και οι εξωτερικές πλευρές.

Μπορούμε να δούμε εύκολα ότι  το μήκος της ακτογραμμής δεν μπορεί να αυξηθεί. Να τα 2 ακραία σενάρια:
Αν έχεις όλη τη σκακιέρα άδεια και 2 παραδιπλανά τετράγωνα μολυσμένα τότε μολύνεται και το ενδιάμεσο και το μήκος της ακτογραμμής του πλέγματος παραμένει σταθερό (2 πλευρές μπαίνουν και 2 ενσωματώνονται στο πλέγμα και χάνονται).

Αν έχεις ένα τετράγωνο πλήρως περικυκλωμένο από μολυσμένα τότε μολύνεται και αυτό και το μήκος της ακτογραμμής μειώνεται κατά 4.

Να αυξηθεί η ακτογραμμή δε γίνεται αφού για να έχεις μόλυνση απαιτούνται 2 γείτονες και άρα στην καλύτερη περίπτωση 2 χάνεις και 2 κερδίζεις.

Δηλαδή η ακτογραμμή δεν είναι ακριβώς διατηρήσιμη ποσότητα… έχει και απώλειες

Άρα το αρχικό μήκος ακτογραμμής είναι το άνω όριο που έχεις. Αφού θέλεις 4000 πλευρές τετραγώνου  τελικό μήκος ακτογραμμής αποκλείεται να έχεις κάτω από 4000 αρχικό μήκος ακτογραμμής. Αυτό σημαίνει ότι θέλεις 1000 τετράγωνα τουλάχιστο και μάλιστα κατάλληλα τοποθετημένα. Άρα κάτω από 1000 δεν πέφτεις με τίποτα λόγω αρχή διατήρησης της ακτογραμμής.

Με 1000 γίνεται. Αν τα βάλεις στη διαγώνιο εύκολα από σχήμα βλέπεις ότι η μόλυνση εξαπλώνεται σε όλη τη σκακιέρα. Άρα 1000 είναι το μικρότερο.

Ελπίζω να μη μου ξέφυγε τίποτα.[/quote]

Τίποτα δεν σου ξέφυγε. Αυτή είναι και η γνωστή λύση. Ακόμα και αν σας έλεγα "κοιτάξτε για αναλλοίωτες ποσότητες" το πρόβλημα θα εξακολουθούσε να είναι δύσκολο. Συγχαρητήρια.