inequalities
combinatorics proposed
combinatorics

Prove that in a tournament with 799 teams, there exist 14 teams,  that can be partitioned into groups in a way that all of the teams in the first group have won all of the teams in the second group.

there is a team that won more than 13games......(trivial...)
select this team(call this team A) and other 13teams those lost to A.
then we pick 14teams and divide them into two groups(1 to 13) as condition..

something strange

I think a group of 14 teams should be partitioned into 2 groups with 7 teams. (Case "2 and 12" is also easy.)

Official Solution:
Throughout this solution, $ a^\plus{}$ denotes $ \max\{a,0\}$.

Consider the tournament as a directed graph, where an edge from $ v$ to $ u$ shows that $ v$ has won its game against $ u$. Let's count the number of directed $ 7$-paw's. (An $ n$-paw is a subgraph consisting of $ n$ edges coming	out from a vertex)

If the out degree of vertices are denoted by $ d_i$ then this number is obviously equal to $ \sum_i{d_i\choose 7}$.

Assuming that the claim of the problem is not satisfied, for each $ 7$ vertices there are at most $ 6$ vertices having edges coming out to each of those $ 7$. Hence the number of $ 7$-paw's is at most $ 6{n\choose 7}$ where $ n$ is $ 799$, the number of vertices.

The remaining parts of the proof try to show that $ \sum_i{d_i\choose 7}>6{n\choose 7}$.

Let $ a_i\equal{}(d_i\minus{}6)^\plus{}$. Then $ {d_i\choose 7}\equal{}\frac{d_i(d_i\minus{}1)\dots(d_i\minus{}6)}{7!}\equal{}\frac{a_i(a_i\plus{}1)\dots(a_i\plus{}6)}{7!}$. This is because if $ d_i>6$, then $ a_i\equal{}d_i\minus{}6$ and this identity obviously holds. And if $ d_i\leq 6$ then 	both sides are $ 0$ and the identity still holds.

Now let $ f(x)\equal{}\frac{x(x\plus{}1)\dots(x\plus{}6)}{7!}\equal{}\sum_ic_ix^i$. Of course $ c_i$'s are all non-negative. \[ \sum_i{d_i\choose 7}\equal{}\sum_if(a_i)\equal{}\sum_i\sum_jc_ja_i^j\equal{}\sum_jc_j\sum_ia_i^j\]Note that $ c_0\equal{}0$. For $ j\geq1$, we have the following inequality between $ j^{th}$ exponents mean and arithmetic mean.\[ \left(\frac{\sum_ia_i^j}{n}\right)^{\frac 1j}\geq\frac{\sum_ia_i}n\]
But since our graph is a tournament $ \sum_id_i\equal{}{n\choose 2}$. Hence $ \sum_ia_i\geq{n\choose 2}\minus{}6n$. This shows that $ \frac{\sum_ia_i}n\equal{}\frac{n\minus{}1}2\minus{}6\equal{}\frac{n\minus{}13}2$. Name this constant as $ A$. Substituting in our inequality gives \[ \sum_ia_i^j\geq nA^j\]Now substituting in our previous identities, we get \[ \sum_i{d_i\choose 7}\geq\sum_jc_jnA^j\equal{}n\sum_jc_jA^j\equal{}nf(A)\]But $ f$ is defined so that $ f(x)\equal{}{x\plus{}6\choose 7}$. So $ nf(A)\equal{}n{\frac{n\minus{}1}2\choose 7}$. A straightforward calculation reveals that this number is $ 242071561222413021$ while $ 6{n\choose 7}$ is $ 241047478096826154$, a slightly smaller number. This completes the proof.

A count-twice works in the same way as well :

Let $X_i$ be the teams. Construct the set $\mathcal{T} = \left \{ \left ( X_1,\cdots , X_7 \right ),(X_{looser}) \right \}$, where $X_{looser}$ is defeated by all of $X_1,X_2, \cdots, X_7$. On the  contrary assume that number of teams defeated by all of any set of $7$ other teams is less than equal to $6$. So $|\mathcal{T}|\le 6\cdot \binom{799}{7}$. We count it in another way :Let $X_i$ be defeated by $n_i$ number of teams, so $|\mathcal{T}| = \sum_{i \in \text{teams}}^{{}}\binom{n_i}{7}$. Also note that $\sum_{i \in \text{teams}}^{{}}n_i = \binom{799}{2}$. So we have $\sum_{i \in \text{teams}}^{{}}\binom{n_i}{7} \le 6\cdot \binom{799}{7} $. Which can be proved to be false,(as above)  and hence the problem statement is true.

Consider some set of guys $|A|=7$ and let $X$ be the set of guys beaten by [b]all[/b] the guys from $A.$ Let $X_i :=1$ if i-th player is in $X,$ otherwise $0.$
We have $$\mathbb E[X]=\sum_{i=1}^{799-7}\mathbb E[X_i]=\sum_{i=1}^{799-7}(\frac{1}{2})^7=\frac{792}{128}=6.1875 >6$$
Thus, there is some configuration such that $X \ge 7$ and just take any $B \subset X.$

Hi everyone,

I did exactly the same thing as SidVicious, but it seems so simple that I doubt it's working...Why the official solution is so hard if the one proposed by SidVicious, which is not hard to find, is true ? Seems strange :s
Moreover, the solution proposed above by SidVicious seems imply that for any set of 7 people, we can find another set of 7 people checking the conditions. Isn't it weird ?

I don't think $\sum_{i=1}^{799-7}{\mathbb E[X_i]}=\sum_{i=1}^{799-7}{(1/2)^7}$ is true. Even if you choose $|A|$ with equal probability from each of $799$ teams, the probability of a team being beaten by team $A_j\in A$ is fixed (and usually not equal to $1/2$).

This kind of flaw doesn't encourage me to use expectation in combo. It's so magic that I don't understand what I do. Even here, where there's obviously a problem, I don't really understand where the prooblem is...

EDIT : Ok I did understand my mistake, and it was a big one. Actually, the tournament can't be generate with randomize procedure. Otherwise, we'll show that "for some" tournaments, there will be a tournament which fullfill conditions, but it's not at all the question.

So we have to consider a given tournament, and then we can use randomization to choose a team or something else.

It's exactly what Dark Lord said I know ^^

Here is a generalization proved using the probabilistic method:
[quote=Generalisation]In a tournament with $n$ teams, let $k,l$ be integers satisfying $$n{{(n-1)/2}\choose{k}}>(l-1){{n}\choose{k}}$$ Then there exist two sets of teams $A, B$ with $k, l$ teams respectively such that each team in $A$ beat each team in $B$.[/quote]
Note: If we say a set of teams $X$ beat a different team $U$, then that means all members of $X$ beat $U$.

Randomly choose a set $A$ with $k$ teams. Let $X$ denote the number of teams $A$ has defeated, and let $D_i$ denote the event that $A$ defeated the team $i$. Further, for any team $i$, let $z_i$ denote the number of teams that $i$ lost to. Hence
$$\mathbf{E}[X]=\sum_i \mathbf{P}[D_i]=\sum_i {{z_i}\choose{k}} \cdot {{n}\choose{k}}^{-1} \geq n{{(n-1)/2}\choose{k}} \cdot {{n}\choose{k}}^{-1} > l-1$$
Hence, there exists a set $B$ of $l$ teams such that $A$ beat $B$, as desired. $\blacksquare$

For the given problem, set $n=799$ and $k=l=7$.

To #6 - the expected value is wrong  !
    To arrive at the inequality is easy
     $\sum_i{d_i\choose 7}>6{n\choose 7}$
The rest is algebra  (this is an algebra prob.  rather than combi ! Even one can NOT use Jensen to derive that inequality  !)

For a team $x$, let $\lambda(x)$ denote the set of teams $x$ beat, and let $\omega(x)$ be the set of teams $x$ lost to. The problem is equivalent to showing that there exist $7$ teams $x_1,\ldots,x_7$ with
\[|\lambda(x_1)\cap\cdots\cap\lambda(x_7)|\ge 7.\]
As usual, we'll compute
\[\mathbb{E}(|\lambda(x_1)\cap\cdots\cap\lambda(x_7)|).\]
For each fixed team $y$, the probability it is in this intersection is just
\[\frac{\binom{|\omega(y)|}{7}}{\binom{799}{7}},\]
so by linearity of expectation,
\[\mathbb{E}(|\lambda(x_1)\cap\cdots\cap\lambda(x_7)|)=\sum_{y\in\tau}\frac{\binom{|\omega(y)|}{7}}{\binom{799}{7}}\]
where $\tau$ is the set of teams. Note that the average value of $\omega(y)$ is $\frac{\binom{799}{2}}{799}=782/2$ since there are a total of $\binom{799}{2}$ losses. Thus, by Jensen,
\[\mathbb{E}(|\lambda(x_1)\cap\cdots\cap\lambda(x_7)|)\ge\frac{799}{\binom{799}{7}}\binom{\frac{798}{2}}{7}.\]
It is a computation to verify that
\[\frac{799}{\binom{799}{7}}\binom{\frac{798}{2}}{7}>6,\]
so we're done, since there must be some $x_1,\ldots,x_7$ with
\[|\lambda(x_1)\cap\cdots\cap\lambda(x_7)|>6.\]

[b]Remark[/b] In our use of Jensen's inequality, we assumed the function $f(x):=\binom{x}{7}$ is convex, which strictly speaking holds only for $x\ge 7$. The fix for our purposes is to define $\tilde{f}(x)=\binom{x}{7}$ for $x\ge 7$ and $\tilde{f}(x)=x-6$ for $6\le x<7$, and $\tilde{f}(x)=0$ for $0\le x<6$. This matches $\binom{\bullet}{7}$ wherever we need it to, and is now correctly convex.

Let team $i$ win $c_i$ games; note $c_1+...+c_n={799\choose 2}$. Randomly choose a set B of 7 teams. For each team T, the probability that T beat all teams in B is $\frac{{c_i\choose 7}}{{799\choose 7}}$ so by linearity of expectation, the expected number of teams that B completely lost to is $\frac{{c_1\choose 7}+...+{c_{799}\choose 7}}{{799\choose 7}}\ge \frac{799{399\choose 7}}{{799\choose 7}}>6$ (by Jensens) which finishes the problem.

Let $a_i$ denote the number of games that each team won to. Then, $\binom{a_i}{7}$ is the number of sets of $7$ teams that were all beaten by team $i$. If we add this up for all of the teams, then we obtain by Jensen's
\[ \sum \binom{a_i}{7} \ge 799 \binom{399}{6}  > 6 \cdot \binom{799}{7} \]
Since there are $\binom{799}{7}$ sets of $7$ teams in total, there exists groups $A$ and $B$ of seven teams each such that each team in $A$ beat each team in $B$.

We randomly select a group of $7$. Now, the idea is to sum up all loss-counts for the $792$ other people. If $l_i$ is the number of losses of person $i$, then the expected number of losses to the 7-group is $$\frac{1}{\binom{798}{7}} \cdot \sum_{i = 1}^{792} \binom{l_i}{7} \geq 792 \cdot \frac{\binom{399}{7}}{\binom{798}{7}},$$ which we can verify is between $6$ and $7$, hence done.

Let $c_i$ be the number of teams that team $i$ beat. Then, firstly note that
\[\sum_{i=1}^{799} c_i = \text{ number of matches } = \binom{799}{2}\]
Now, by Jensen's, since $\binom{x}{7}$ is convex we have that
\[\text{the number of sets $(A,B_1,B_2,\ldots B_7)$}= \sum_{i=1}^{799} \binom{c_i}{7} \geq 799 \cdot \binom{\frac{\sum c_i}{799}}{7}=799 \cdot \binom{399}{7}\]
Summing over all $(B_1,B_2,\ldots B_7)$, the average number of people who have beaten everyone in this group is
\[\frac{ \sum_{i=1}^{799} \binom{c_i}{7}}{\binom{799}{7}}\geq \frac{799\cdot \binom{399}{7}}{\binom{799}{7}}= \frac{(396\cdot395\cdot394\cdot393)}{2^{3}\cdot(797\cdot795\cdot793)} = \frac{(99\cdot79\cdot197\cdot131)}{(797\cdot53\cdot\left(13\cdot61\right))}>6  \]
Thus, by pigeonhole there is some group $(B_1,B_2,\ldots B_7)$ such that there is a group of size 7:$(A_1,\ldots A_7,)$ such that all teams in A beat all teams in B.

We just have to double-count the number of pairs $T = \left \{ \left ( A_1,\cdots , A_7 \right ),(A) \right \}$, where $A$ has lost all matches with the $A_i$. If $A$ has lost $n_i$ matches, then $\sum^{{}}\binom{n_i}{7} \le 6\cdot \binom{799}{7} $, where the bounding contradiction is achieved with Jensen.

We count the number of pairs $(P, S)$, where $P$ is a player and $S$ is a set of $7$ players that $P$ beat. If we let $w_i$ be the number of wins each person had, the sum is $\sum \dbinom{w_i}{7}$, and by Jensen's, the minimum is $799 \cdot \dbinom{399}{7}$.
There are exactly $\dbinom{799}7$ values of $S$. By Pigeonhole, one of them appears at least $\frac{799 \cdot \dbinom{399}7}{\dbinom{799}7} > 6$ times, which finishes.

Let $\ell_i$ denote the number of losses that the $i$th team. Notice that there is ${\ell_i \choose 7}$ groups of $7$ that have all beaten team $i$. Now summing this over all $i$, we receive that $$\sum_{i} {\ell_i \choose 7} > 799 \cdot {399 \choose 7}$$ which is true by Jensen's. Now this is equal to the total number of times a group of $7$ have all beaten a singular person. Now we want to find the expected value of people that a random group of $7$ have commonly beaten, call this $X$. Note that $$\mathbb{E}[X] > \frac{799 \cdot {399 \choose 7}}{{799 \choose 7}} > 6$$ so we are done.

Another standard global problem: The heuristic is usually to compute expected value with counting and Jensen's.

Take a directed connected graph G, where vertices represent teams. We sample $A$ randomly from the $799$ teams and compute the number of teams defeated by everyone in $A$; a team v is expected to lose to every team in A with probability $$\frac{{\binom{\text{indeg} v}{7}}}{{\binom{799}{7}}}\implies A\text{(\# of wins)}=
  \frac{1}{\binom{799}{7}}
  \sum_v \binom{\text{indeg} v}{7}
  \overset{\text{Jensen}}{\ge}
  \frac{1}{\binom{799}{7}}799 \binom{399}{7}>6,$$ so there's a group of seven teams that each team of A beat, as desired. $\blacksquare$

Randomly choose a set of 7 "loser" teams. Then, we call a team good if it defeated all 7 loser teams.\\

The probability of a team with $w$ wins being good is $$\frac{{w\choose 7}}{{799\choose 7}}$$ since all 7 randomly chosen teams must be in would of the $w$ teams that it beat. By Jensen's Inequality, since ${w\choose 7}$ is convex, and the sum of all $w_i$ is constant (equal to 799 choose 2), this is minimized when all $w_i$ are equal (equal to 399). Thus, the expected number of good teams is at least $$799\cdot \frac{{399\choose 7}}{{799\choose 7}}\approx 6.03,$$ which is greater than 6, so some way must achieve at least 7 good teams.

Let $W$ be the number of wins a team has.
Then the probability that the team beats a given group of $7$ teams is $\frac{\binom{W}{7}}{\binom{799}{7}}$.
Then the expected value of teams that beat the given $7$ teams is $\cdot \frac{\binom{W_i}{7}}{\binom{799}{7}}$ for all teams $i$.
Then by Jensen's since $\binom{W}{7}$ is convex, we have $\frac{\binom{W_i}{7}}{\binom{799}{7}} \geq 799 \cdot \frac{\binom{399}{7}}{\binom{799}{7}} > 6$, so we are done.

(I'm not really sure how people got that the final expression is greater than $6$ without a calculator lol)


algebra
polynomial
Probabilistic Method
probability
IMO Shortlist
expected value

Let $ S$ be a finite set of points in the plane such that no three of them are on a line. For each convex polygon $ P$ whose vertices are in $ S$, let $ a(P)$ be the number of vertices of $ P$, and let $ b(P)$ be the number of points of $ S$ which are outside $ P$. A line segment, a point, and the empty set are considered as convex polygons of $ 2$, $ 1$, and $ 0$ vertices respectively. Prove that for every real number $ x$ \[\sum_{P}{x^{a(P)}(1 \minus{} x)^{b(P)}} \equal{} 1,\] where the sum is taken over all convex polygons with vertices in $ S$.

[i]Alternative formulation[/i]:

Let $ M$ be a finite point set in the plane and no three points are collinear. A subset $ A$ of $ M$ will be called round if its elements is the set of vertices of a convex $ A \minus{}$gon $ V(A).$ For each round subset let $ r(A)$ be the number of points from $ M$ which are exterior from the convex $ A \minus{}$gon $ V(A).$ Subsets with $ 0,1$ and 2 elements are always round, its corresponding polygons are the empty set, a point or a segment, respectively (for which all other points that are not vertices of the polygon are exterior). For each round subset $ A$ of $ M$ construct the polynomial
\[ P_A(x) \equal{} x^{|A|}(1 \minus{} x)^{r(A)}.
\]
Show that the sum of polynomials for all round subsets is exactly the polynomial $ P(x) \equal{} 1.$

[i]Proposed by Federico Ardila, Colombia[/i]

I think you can do this with probability. Let's colour the points black and white and Let the probability that a point has colour black be x. Now look at any convex polygon $ P$. The probability that all its vertices are black is $ x^{a(P)}$ and that all the points outside it are white is $ (1 \minus{} x)^{b(P)}.$ The given summation is the probability that there exists a polygon with vertices black and all points outside it are white. But we know this is true (i.e. 1) as all we have to do is consider the convex hull of the black points. Now this is true for all $ x\in(0,1)$. But this is a polynomial with finite degree and the number of points at which it evaluates 1 is infinite. so, this is an identity and holds $ \forall x\in \mathbb{R}$

[i]Moderator edit: See also the discussion of [url=http://www.mathlinks.ro/viewtopic.php?p=1223776#1223776]Lubell-Yamamoto-Meshalkin inequality.[/url][/i]

[quote="watchcatno1"]
Let's colour the points black and white and Let the probability that a point has colour black be x. Now look at any convex polygon $ P$. The probability that all its vertices are black is $ x^{a(P)}$ and that all the points outside it are white is $ (1-x)^{b(P)}.$
[/quote]

Very very beautiful!!

[quote]
The given summation is the probability that there exists a polygon with vertices black and all points outside white.
[/quote]

Or: The given summation is the expected number of polygons with black vertices and all points outside white.
Since for every fixed coloring, there exists exactly one such polygon, the expected number over all such colorings equals 1.

I know using the [url=http://en.wikipedia.org/wiki/Probabilistic_method]probabilistic method pioneered and championed by Erdös, Alon, Spencer[/url] is a very neat solution. Maybe somebody wants to discuss a different approach.  :)

Let $ f(P)\equal{}x^{a(P)}(1\minus{}x)^{|S|\minus{}a(P)}$.
By the binomial theorem, $ \sum _{P\in S} f(P)\equal{}1$ where $ P$ is any set of points in $ S$ not just convex polygons.
For any convex polygon $ P$,  the value of $ \sum _Q f(Q)$, where the sum is taken over all sets of polygons $ Q$ such that all points of $ Q$ are in or on $ P$ and $ P\in Q$ (i.e. all polygons with $ P$ as its convex hull), is $ \sum ^{|S|\minus{}b(P)}_{k\equal{}a(P)}\dbinom{|S|\minus{}a(P)\minus{}b(P)}{k\minus{}a(P)}x^{k}(1\minus{}x)^{|S|\minus{}k}\equal{}x^{a(P)}(1\minus{}x)^{b(P)}$.
Since every set of points has exactly one convex hull, $ \sum _{P\in S} f(P)\equal{}\sum _{P}x^{a(P)}(1\minus{}x)^{b(P)}\equal{}1$, as desired.

A different approach using strong induction:

For any finite set $T$ of points in a plane with no three collinear points,
Let $P^*_T$ be the set of all convex polygons whose vertices are in $T$,
$b_T(P)$ be the number of points in $T$ which lies outside $P$
We assume that $\sum_{P\in P^*_{T}}\left[x^{a(P)}(1-x)^{b_{T}(P)}\right]=1$ forall $T$ with $|T|<|S|$
We can check for base case to be true.

Let $S$ be the universal set here, i.e. for any set $X\subseteq S$, we denote $X'=S\setminus X$
Let $C$ be the convex hull of $S$.

For any finite non-empty set $A$ and any number $z,$ $\sum_{X\subseteq A}z^{|X|}=(1+z)^{|A|}\cdots (I)$
For $X\subseteq C$, $P^*_{X'}\subseteq P^*_S$ and $b_S(P)=b_{X'}(P)+|X|\ \forall P\in P^*_{X'}\cdots (II)$

For a fixed $P\in P^*_S$ such that $P\neq C$,
$\sum_{X\subseteq C, P\subseteq X'}(-1)^{|X|}=0$ (sum ranging over all sets $X$ satisfying $X\subseteq C, P\subseteq X'$)
this follows from $(I)$ with $A=C\cup P'$ and $z=-1$
Now, for $P\neq C$:
\[0=x^{a(P)}(1-x)^{b_S(P)} \left[ \sum_{X\subseteq C, P\subseteq X'}(-1)^{|X|} \right]\]
\[=\sum_{X\subseteq C, P\subseteq X'}\left[(-1)^{|X|}x^{a(P)}(1-x)^{b_S(P)}\right]\]

For $P=C$, \[\sum_{X\subseteq C, P\subseteq X'}\left[(-1)^{|X|}x^{a(P)}(1-x)^{b_S(P)}\right]\]
\[=\sum_{X=\phi}\left[(-1)^{|X|}x^{a(P)}(1-x)^{b_S(P)}\right]=(-1)^0x^{|C|}(1-x)^0=x^{|C|}\]

Now, by varying $P$ we have:
\[x^{|C|}\]
\[=\sum_{P\in P^*_S}\sum_{X\subseteq C, P\subseteq X'}\left[(-1)^{|X|}x^{a(P)}(1-x)^{b_S(P)}\right]=\]\[\text{(from } (II) \text{ we have)}\]
\[=\sum_{X\subseteq C}\sum_{P\in P^*_{X'}}\left[(-1)^{|X|}x^{a(P)}(1-x)^{b_{X'}(P)+|X|}\right]=\]
\[=\sum_{X\subseteq C}(x-1)^{|X|}\sum_{P\in P^*_{X'}}\left[x^{a(P)}(1-x)^{b_{X'}(P)}\right]=\]
\[=\sum_{X\subseteq C,X\neq \phi}(x-1)^{|X|}\sum_{P\in P^*_{X'}}\left[x^{a(P)}(1-x)^{b_{X'}(P)}\right]+\sum_{P\in P^*_{S}}\left[x^{a(P)}(1-x)^{b_{S}(P)}\right]=\]\[\text{(from induction hypothesis}\sum_{P\in P^*_{X'}}\left[x^{a(P)}(1-x)^{b_{X'}(P)}\right]=1\ \forall |X'|<|S|\text{)}\]
\[\sum_{X\subseteq C,X\neq \phi}(x-1)^{|X|}\cdot 1+\sum_{P\in P^*_{S}}\left[x^{a(P)}(1-x)^{b_{S}(P)}\right]\]

So
\[\sum_{P\in P^*_{S}}\left[x^{a(P)}(1-x)^{b_{S}(P)}\right]\]
\[=x^{|C|}-\sum_{X\subseteq C,X\neq \phi}(x-1)^{|X|}=x^{|C|}+1-\sum_{X\subseteq C}(x-1)^{|X|}=x^{|C|}+1-[1+(x-1)]^{|C|}=\]\[\text{(follows from }(I)\text{ with }A=C,z=(x-1)\text{)}\]
\[1\]
QED

We use strong induction on $|S|$, where the base case $|S|=0$ is clear.

Consider the convex hull of $S$, and say it has $n$ points $Q_1,Q_2,\ldots,Q_n$. Then by the inductive hypothesis, (letting $S'=S-\{Q_{i_1},Q_{i_2},\ldots,Q_{i_k}\}$)
\[f(S')=\sum_{P\in S'}x^{a(P)}(1-x)^{b_{S'}(P)}=1,\]so using PIE to sum up $x^{a(P)}(1-x)^{b_{S}(P)}$ over all convex polygons $P\in S$ excluding [i]at least one point[/i] on the convex hull $Q_1Q_2\cdots Q_n$ (note that the $k$ points excluded are outside $P$), we obtain
\[f(S)-x^n(1-x)^0=-\sum_{k=1}^{n}(-1)^{k}\binom{n}{k}(1-x)^k f(S')=-((1-(1-x))^n-(1-x)^0)\]and thus
\[f(S)=1,\]as desired.

My solution :

We use strong induction to solve the problem. The base cases are found to be true. Let for any polygon $P$ let $F(P) = x^{a(p)}(1-x)^{b(p)}$. Assume for any set $L$, with $|L| < |S|$, we have $\sum_{\substack{P \in L \\ P \ne \emptyset }}^{{}} F(P) = 1 - (1-x)^{|L|}$ Now consider $S$, if it forms a convex polygon the claim can easily be proved. Else let $\mathcal{C}$ be the convex hull of $S$. Let $|\mathcal{C}| = t$ and let the number of points inside it be $m$. So $|S| = m+t$. Let $\mathcal{P}_i  $ denote the polygons which has exactly $i$ number of vertices in the convex hull $\mathcal{C}$. Note that $P_i \ne \emptyset $ for all $i$.  We define $f(N_i)= \sum_{{}}^{{}} F(\mathcal{P}_i  ) $ where the summation is taken over all the polygons having exactly  $i$ number of vertices in the convex hull $\mathcal{C}$. Note that if $i=t = |\mathcal{C}|$, there is no  polygon other than the convex hull itself containing all the points of $\mathcal{C}$ as the vertices. So $f(N_t) = F(\mathcal{C}) = x^{t}$.

So $\sum_{\substack{P \in S \\ P \ne \emptyset}}^{{}}F(P) = \sum_{i=0}^{t} f(N_i ) = \sum_{i=0}^{t-1} f(N_i ) + x^t $. Note that $x^t + \sum_{i=0}^{t-1} f(N_i )  = x^t + \sum_{i=0}^{t-1}f(N_i)\left (\sum_{r=1}^{t-i} (-1)^{(r+1)} \binom{t-i}{r} \right ) $.  $= x^t + \sum_{r=1}^{t}(-1)^{(r+1)}\sum_{i=0}^{t-r}\binom{t-i}{r}f(N_i)$ $= x^t +  \sum_{r=1}^{t} (-1)^{r+1} \sum_{\substack{P \in S\setminus \mathcal{C}\cup T , P \ne \emptyset \\ T \subseteq \mathcal{C} \\ |T| = t-r}}^{{}} F(P)$ $ = x^t + \sum_{r=1}^{t} (-1)^{(r+1)}\binom{t}{t-r} \left ( 1- (1-x)^{t-r+m} \right )\left ( 1-x \right )^r = 1 -(1-x)^{t+m}$ $ = 1 -(1-x)^{|S|}  $, and the induction is complete.

We randomly color the point by black and white, and the probability for a points to be colored by black is $p$. For each convex polygon $P$, let $\mathbb{E}[P]$ be the event that every vertices of $P$ is black and every point outside $P$ is white. These event are pairwise mutually exclusive. Hnece the LHS is the probability of the event that some $\mathbb{E}[P]$. But this surely happens, by considering the convex hull of all balck points.

We prove the statement when those $ |S| $ points form a convex $ |S| $-gon. It is easy because the convex hull of every $ P \subseteq S $ is exactly $ P $ (i.e. $ a(P) + b(P) = |S| $), so we need to evaluate:
$$ \sum_{P}{x^{a(P)}(1 - x)^{b(P)}} = \sum_{P}{x^{a(P)}(1 - x)^{|S| - a(P)}} = \sum_{i=0}^{|S|}\sum_{a(P) = i}{x^{i}(1 - x)^{|S|-i}} = \sum_{i=0}^{|S|}{{|S| \choose i}x^{i}(1 - x)^{|S|-i}} = (x + (1 - x))^{|S|} = 1 $$

Let us call one point $ T $. We draw $ {|S|-1} \choose 2 $ lines for every pair of points which are not $ T $ and consider translation of $ T $ over a line $ l $ which passes through points $ A $ and $ B $ and divides plane in two halfplanes where $ H_1 $ and $ H_2 $ denote set of points in a halfplane ($ A $ and $ B $ included). Let $ f(P) \equiv x^{a(P)}(1 - x)^{b(P)} $. We can say that $ f(P) = 0$ for non-convex $P$. WLOG $ T $ goes from $ H_1 $ to $ H_2 $. $ X' $ denotes an object $ X $ after this transformation.

These facts are true:

$$ f(P') = f(P) \qquad \qquad \forall P \subseteq S \quad A \notin P \lor B \notin P $$
because moving point $T$ over $ l $ does not affect convexity of $P$, $ a(P) $ nor $ b(P) $.

$$ f(P') = f(P)(1-x) \qquad \qquad \forall P \subseteq H_1 \setminus \{ T \} \quad A, B \in P $$
because moving point $T$ over $ l $ does not affect convexity of $P$ and $ b(P) $ increases by $1$ (that is point $T$).

$$ f(P' \cup \{ T \} ) = f(P)x \qquad \qquad \forall P \subseteq H_1 \setminus \{ T \} \quad A, B \in P $$
because $ a(P) $ increases by $1$ (that is point $T$).

$$ f(P \cup \{ T \} ) = 0 \qquad \qquad \forall P \subseteq H_1 \setminus \{ T \} \quad A, B \in P $$
because it is not convex.

Combining last three facts and deducing similarly for $ P \subseteq H_2 \setminus \{ T \} $ we conclude that: $$ f(P') + f(P' \cup \{ T \} ) = f(P) + f(P \cup \{ T \} ) \qquad \qquad \forall P \subseteq S \setminus \{ T \}  \quad A, B \in P $$

(We used that $ A, B \in P $ implies either $ P \subseteq H_1 \setminus \{ T \} $ or $ P \subseteq H_2 \setminus \{ T \} $.)

Finally,

$$ \sum_{P'}{x^{a(P')}(1 - x)^{b(P')}} = \sum_{P'}{f(P')} = \sum_{\substack{P' \subseteq S \\ A \notin P' \lor B \notin P'}}{f(P')} + \sum_{\substack{P' \subseteq S \setminus \{ T \} \\ A, B \in P'}}{f(P') + f(P' \cup \{ T \})} = \sum_{\substack{P \subseteq S \\ A \notin P \lor B \notin P}}{f(P)} + \sum_{\substack{P \subseteq S \setminus \{ T \} \\ A, B \in P}}{f(P) + f(P \cup \{ T \})} = \sum_{P}{f(P)} = \sum_{P}{x^{a(P)}(1 - x)^{b(P)}} $$

proving that this is a monovariat expression. We can achieve every configuration by using that transformation. Q.E.D.

[b]Lemma [/b] If we have a set $A$ of $s$ points such that any convex polygons formed by the points not in $A$ does not contain any points in $A$ in the interior, then \[\sum_{P, A \in P}{x^{a(P)}(1 - x)^{b(P)}} = x^{|A|}.\]
Proceed via induction on number of points total for this and the main problem together. Consider each distinct set $B$ of points in $S-A$ such that $A+B$ is a convex polygon. We consider the smaller set of points on and inside $A+B$, excluding the points $A$. For all convex polygons $C$ such that convex hull of $C+A$ is the same as $B+A$, $C$ is in the set. Now the sum \[\sum_{C}{x^{a(C)}(1 - x)^{b(C)}}\] by induction is $x^{|B|}$. Then readding all the other points besides $A$, we get $x^{|B|}(1-x)^{b(A+B)}$. By induction, the sum across all such $B$'s is $1$. So if we then add back $A$, we get $x^{|A|}$.

Take a point $T$ on the convex hull of $S$, by induction hypothesis for lemma all the polygons with $T$ in it contribute $x$ to $\sum_{P A \in P}{x^{a(P)}(1 - x)^{b(P)}}$. And if we consider removing $T$, then the sum for the remaining points would be $1$ by inductive hypothesis so that adding back $T$ these would contribute $1-x$ to the sum ($T$ is outside all those polygons). And finally $x+(1-x) = 1$, so our sum is $1$ as desired.

Very short and nice problem. The $x$ and $1-x$ begs us to use some sort of probability construction. First assume $0<x<1$, we color the points with the following method: each point has probability that a point is red is $x$, blue is $1-x$. The expression is the probability that the convex hull of all the red points is P. Obviously summing over all P, we get the probability that the convex hull of all the red points is a convex polygon in S which is clearly true. The polynomial is 1 for $0<x<1$. Since the polynomial is 1 for an infinite number of x, and has a finite degree, It must be 1 for all x.

[b]Lemma: [/b]Given a set $S$, and $a$ consecutive points along its convex hull, then the sum over all convex polygons containing these $a$ points is $x^a$.

We will prove this with induction. The base case for the claim is when $S$ is a set with exactly $a$ points on its convex hull. In this case, there exists only one such polygon, and its value is just $x^a(1-x)^0=x^a$ as desired.
Now, for the inductive step, consider an arbitrary set $S$, and $a$ points along its convex hull. Consider the next point after these $a$ points, still along the convex hull - $B$. If we sum over all convex polygons containing our $a$ points but not $B$, we will get $x^a(1-x)$, since inductive hypothesis tells us we get $x^a$ if we sum over the set $S\setminus B$, but now $B$ will add $1$ to the $b$ value of all polygons. On the other hand, if we include $B$, then inductive hypothesis from the $a+1$ case tells us that this yields a net sum of $x^{a+1}$. Combining these two cases, the sum over all convex polygons with these $a$ points is $x^a(1-x+x)=x^a$, as desired. So, the induction is complete.

To finish, we will use induction on the size of $S$. The base case of $|S|=3$ is clear, so continue to $|S|=n$. In this case, consider a point $P$ on the convex hull of $S$. Using similar logic as before, the sum over all convex polygons not including $P$, by inductive hypothesis, is just $1-x$. On the other hand, the sum over all polygons with $P$ is $x$, by our Lemma, so the total sum is $1$, as desired.

There must be some method without using convex hulls

The result is obvious if $S$ consists of vertices of a convex polygon since it becomes the binomial theorem.

Now imagine moving points of $S$ around; our goal is to show the LHS does not change. Let $X$ be a point and consider the $\binom{|S|-1}{2}$ lines determined by two points in $S$. As $X$ moves, there is no change unless some line is crossed.

Now imagine $X$ crosses a line segment $AB$. If $P$ was a polygon that contained $A$ and $B$ as consecutive vertices, then that polygon has one more point outside it; at the same time, a new convex polygon with $a(P)+1$ vertices is created, with $b(P)$ vertices. So we need to check \[ \underbrace{x^{a(P)} (1-x)^{b(P)}}_{\text{original } P} 	= 	\underbrace{x^{a(P)} (1-x)^{b(P)+1}}_{\text{modified } P} 	+ \underbrace{x^{a(P)+1} (1-x)^{b(P)}}_{\text{new polygon}} \] which is true. The same argument (in reverse) applies for polygons $P$ which have $A$ and $B$ as consecutive vertices in which $X$ moves in to the polygon.

This handles the case where $X$ crosses a segment $AB$. If $X$ crosses the extension of ray $AB$ past $B$, we can repeat the same proof with the roles of $B$ and $X$ swapped. Hence, we finally conclude that moving $X$ does not change the LHS.

Since we may move any point in the set arbitrarily, this shows the LHS depends only on $|S|$ and hence must equal $1$.

I guess this is a repeated solution..but can't help! :D
Let us just consider $x \in [0,1]$, because that is enough to imply the problem for all reals.
We colour every vertex of $S$ red or blue with probability $x$ and $1-x$ respectively. Then, \[{x^{a(P)}(1 - x)^{b(P)}} \] is just the probability that every vertex of $P$ is red and all points outside $P$ are blue. When we take a sum over all convex polygons, the resulting sum of the probabilities is just the probability of that there is at least one such convex $P$ having all vertices red and all points outside it blue. But such a $P$ always exists (the convex hull of all red points, which may be empty but that is allowed). We are done.

Color each point red with probability $x$ and blue with probability $1-x$. Call a polygon $P$ [i]good[/i] if all its vertices are red and all the vertices outside it are blue. Then
\[ \Pr[\text{$P$ good}] = x^{a(P)}(1-x)^{b(P)}. \]
So
\[ \mathbb{E}[\text{number of good polygons}] = \sum_{P} 1\cdot \Pr[\text{$P$ good}] = \sum_{P} x^{a(P)}(1-x)^{b(P)}. \]
where the expectation is taken over all possible colorings. But note that in a fixed coloring, there is exactly 1 good polygon: the convex hull of the red points. So the expectation over all polygons is also 1, finishing.

[hide=Remarks]The expression begs for a probability interpretation, and along with expectation, it just works. [/hide]

Solved with [b]GeronimoStilton[/b] and [b]awang11[/b]:

Because polynomials are happy, assume $x \in [0,1]$. Color every point red randomly with probability $x$. Then $\sum_{P} x^{a(P)}(1-x)^{b(P)}$ is the probability that some $P$ is the convex hull of the red points. This is $1$.

Let $x$ be the probability that we color a certain point white, and then $1 - x$ probability of black. The left hand basically just computes the probability of a specific polygon being a white convex hull. Exactly one exists, so we are done.

Let $a=x$ and $b=1-x$, notice that for each round subset $A$ let $I(A)$ be the number of points in its interior then
$$P(x)=\sum_{\text{A round}}a^{|A|}b^{r(A)}(a+b)^{I(A)}\hspace{20pt}(1)$$
Notice that if we expand the right hand side of $(1)$, we get a homogeneous polynomial with degree $|M|$. Let $|M|=k$ we show that the coefficient of the term $a^ib^{k-i}$ has coefficient $\binom{k}{i}$.

Indeed, we create a bijection between each such terms and $i$-point sets in $M$. Consider every $i$-point set in $M$, let $A$ be its convex hull then it will be a round subset, then it will correspond to the term $a^{|A|}b^{r(A)}a^{i-|A|}b^{I(A)-i+|A|}$. It is easy to see that this is a bijection.

Therefore,
$$P(x)=\sum_{i=1}^n\binom{n}{i}a^ib^{n-i}=(a+b)^n=1$$
as desired.

Feels somewhat contrived, as the summation idea kind of implies the solution.

It suffices to prove the identity for $0<x<1$. Define a set $A \subset S$ of points as follows: any given point in $S$ has a probability $x$ of being in $A$. Then, the sum on the left is equal to the expected number of polygons $P$ for which no points in $A$ are excluded from $P$, and all points on the boundary of $P$ lie in $A$.

However, this quantity is precisely 1 because the only polygon that satisfies these conditions is the convex hull of $A$, which proves the identity.

First suppose $x \in (0,1)$. Randomly color the points in $S$ red with probability $x$ and blue with probability $1-x$. I claim both sides count the expected number of convex polygons with entirely red vertices such that every red vertex lies within that polygon. Summing over polygons (by linearity of expectation) yields the summation on the LHS, since for a polygon $P$ to satisfy the conditions described, we need $a(P)$ specific vertices to be red and $b(P)$ specific vertices to be blue. On the other hand, there will always be exactly one polygon $P$ that works: the convex hull of the red points. This is because if some part of this convex hull is not in $P$, then a red point lies outside $P$ (a vertex of said convex hull), and if $P$ contains the convex hull and some other vertex, that vertex must be blue.\\
To finish, note that for any fixed $S$, the equation is a polynomial identity. Since both sides agree for infinitely many $x$, they must agree for all $x \in \mathbb{R}$, so we're done. $\blacksquare$

[b]Remark:[/b] Feels like the condition about $P$ being convex is a bit of a giveaway regarding the involvement of a convex hull?

We choose to select or not select each point independently and at random with probability $x$. Then, the probability that all the vertices of $P$ is selected is $x^{a(P)}$, and the probability that no point outside of $P$ is selected is $(1-x)^{b(P)}$. Thus, the probability that $P$ is the convex hull of the selected points is
\[x^{a(P)}(1 - x)^{b(P)}\]
Each set of points has exactly one convex hull, so we are done.

We will prove that the LHS is equal to $1$ for any $x$ such that $0<x<1$, then the result follows automatically because the LHS is a polynomial.

Consider colorings of the points in $S$, with each point being red with probability $x$ and blue with probability $1-x$, and the colors being independent. Call a polygon [i]good[/i] for a coloring if all of its vertices are red and all of the points outside it are blue.

[b]Claim.[/b] The convex hull of the red points, $P$, is the only good polygon.
[b]Proof.[/b] Obviously $P$ is good. Now consider a polygon $Q\ne P$ that has a vertex set that is not a superset of the vertex set of $P$. Then choose a vertex $v$ that $Q$ left out but is a vertex in $P$. The only way to not have $v$ be on the outside of $Q$ is for $Q$ to take points that are outside the convex hull, which are not red, so $Q$ is bad.
Now consider a polygon $Q\ne P$ that has a vertex set that is a superset of the vertex set of $P$. Then $Q$ contains points outside the convex hull, which are not red, so $Q$ is bad.

Now simply note that a coloring makes a specific polygon good with probability $x^{a(P)}(1-x)^{b(P)}$. QED.

Silly funny goofy problem

Suppose all the points are initially grey, and we color some of the points in $S$ with probability $p$. First, notice that there is always a unique convex polygon $Q$ with all red vertices and with no red points outside of $Q$, just take $Q$ to be the convex hull of the red points. But, given any polygon $P$, the probability that all the vertices of $P$ are red and all the points in $S$ outside of $P$ are grey is $p^{a(P)}(1-p)^{b(P)}$. But since such a polygon must exist, it must be the case that \[ \sum_{P} p^{a(P)}(1-p)^{b(P)} = 1 \]

This might be one of my favourite double counting problems.

For each convex polygon $P$ with vertex set $V(P)$ contained in $S$, define $I(P)$ to be the set of points lying inside $P$, $E(P)$ the set of points lying outside $P$. Also denote by $c(P)$ the cardinality of $I(P)$. We call the wanted value $A$.
Set $y=1-x$. Now we begin our magical calculation.

\begin{align*}
A&=\sum_{P}x^{a(P)}y^{b(P)} \\
    &=\sum_{P}x^{a(P)}y^{b(P)}(x+y)^{c(P)} \\
   &=\sum_{P}x^a(P)y^{b(P)}\sum_{J\subset I(P)}x^{|J|}y^{c(P)-|J|} \\
    &=\sum_{P}\sum_{J\subset I(P)}x^{a(P)+|J|}y^{b(P)+c(P)-|J|} \\
    &=\sum_{K\subset S}x^{|K|}y^{|S|-|K|} \\
    &=(x+y)^{|S|} \\
&=1
\end{align*}

Then we are done! :-D

One of the problems of all time.

Let $c(P)$ be the number of points inside $P$, such that $a(P) + b(P) + c(P) = |S|$.

Then, it remains to show that
\[
	\sum_{P}{x^{a(P)}(1 - x)^{b(P)}(x + (1-x))^{c(P)}} = 1
\]

Consider $2$-colorings $(R, B)$ of $S$ where vertices in $P$ are painted red, vertice outside $P$
are blue, and vertices inside can be painted either color, where $R$ and $B$ are the number of each color
painting respectively.

The LHS is equivalent to summing $x^R(1-x)^B$ over all two colorings.

Then, there exists a bijection between the possible values of $R$ and $\mathcal{P}(S)$ since for each
$s \in \mathcal{P}(S)$, it corresponds to letting $P$ be the convex hull of $s$ and coloring the interior
points accordingly.

As such, the sum is just
\[
	\sum_{P \in \mathcal{P}(S)} x^{|P|}(1-x)^{|S \setminus P|} = ((x) + (1-x))^{|S|} = 1.
\]

Assume that $x \in (0, 1)$ since the LHS is a polynomial in $x$ (if the identity holds for infinitely many reals, it holds for all reals). Color the points in $S$ black with probability $x$ and white with probability $1 - x$. Then the LHS sums the probability that all of the vertices of $P$ are black while all of points outside $P$ are white, across all convex polygons $P$. But for every coloring of the points, there exists exactly one such polygon; the convex hull of the black points (all other convex polygons $P'$ either have white points as vertices or black points lying outside $P'$). Therefore the LHS indeed equals $1$ for all $x \in (0, 1)$, so it must be $1$ for all reals and we are done.

Fortunately the polynomial given in the problem is not a series, so convergence issues are off our back. In particular, it suffices to prove the problem for $x \in (0, 1)$. That said, consider the following random process. Color each point in $S$ red with probability $x$ and blue with probability $1-x$. The quantity in the LHS of the desired equality is the probability that the convex hull of the red points is a convex polygon. But clearly this probability is $1$ as no three points in $S$ are collinear, and we conclude.

Pick each point with probability $x$, and pick the convex hull of these points.

We claim that the summand is exactly the probability that the polygon in question is picked. First of all, we must pick all of the vertices of the polygon itself, which is $x^{a(P)}$. Then, we must not pick any vertices in the exterior of the polygon, which happens with probability $(1-x)^{b(P)}$. We do not care about the status of the vertices inside the polygon, since we are taking the convex hull.

Thus, the sum of the probabilities is 1, which solves the problem for $0\leq x\leq 1$. To finish, note that the summation is a polynomial in $x$, and it matches the constant polynomial $1$ at infinitely many values, so by identity theorem it is always 1.


geometry
3D geometry
prism
AMC
USA(J)MO
USAMO

Prove that if $ G$ is a connected graph, then there exists at least two vertices $ x,y$ such that both $ G\minus{}x$ and $ G\minus{}y$ are connected.

[hide]
If it is a tree, then just take the vertices that are only connected to 1 edge, yay.  If it is not a tree then there is a cycle, take x and y from the cycle and you win.[/hide]

That doesn't sound correct. Suppose we start with a prism, top face shaped like an n-gon, and then remove all of the edges on the top face (leaving n vertices of degree 1 on the top, and n vertices of degree 3 on the bottom). Let the remaining verices and edges be $ G$. We have a cycle, but we can't remove any vertices from it, or we lose a vertex on the top. So your method doesn't work.

He just needs to refine his argument. If you have a cycle, arbitrarily remove an edge so that cycle doesn't exist anymore. Once you remove all cycles, the problem is trivial.

Or, in fewer words, say something about a spanning tree of the graph (which is exactly the object you end up with if you follow Altheman's suggestion).

Right...I like that argument more than the 'lets just state that we can do that' approach. This same suggestion came up during discussion about USAMO 2007 #4.


analytic geometry
graphing lines
slope
geometry
rectangle

Let $ ABCD$ be a rectangle. The coordinates of $ A$ and $ C$ are $ (1,3)$ and $ (5,1)$, respectively. If the slope of the diagonal $ BD$ is $ 2$, then determine the coordinates of $ B$ and $ D$.

[hide]With some quick trial and error with graphing I got $ B \equal{} (2,0)$ and $ D \equal{} (4,4)$[/hide]

Take the circle diameter $ AC$ and intersect it with the line of slope two through the midpoint of $ AC$. This gives you your two points.

[I think this is fair to do in about three to five minutes...]

Wow nice thinking Alex! :)  I could do that, but we aren't in the circles chapter yet. So I'm not sure if they would consider this solution to be awarded full marks. :(  Here's what I did:

[hide="My Solution"]Let the equation of $ BD$ be $ y\equal{}2x\plus{}c$. Plugging in the midpoint  $ \left(\frac{1\plus{}5}{2},\frac{3\plus{}1}{2}\right)\equal{} (3,2)$ of $ BD$ and $ AC$ in this equation we get $ c\equal{}\minus{}4$. Thus all points on $ BD$ satisfy $ y\equal{}2x\minus{}4$. Assume the coordinates of $ B$ and $ D$ are $ (x_1,2x_1\minus{}4)$ and $ (x_2,2x_2\minus{}4)$ respectively. Then we have $ \left(\frac{x_1\plus{}x_2}{2},\frac{2x_1\minus{}4\plus{}2x_2\minus{}4}{2}\right)\equal{} (3,2)$ implying $ (x_1\plus{}x_2)\equal{}6\qquad(1)$.

Now $ AC\equal{}BD$ implies $ (x_1\minus{}x_2)^2\plus{}(2x_1\minus{}4\minus{}2x_2\plus{}4)^2\equal{}(1\minus{}5)^2\plus{}(3\minus{}1)^2$, which is euqivalent to $ (x_1\minus{}x_2)^2\equal{}4$ or $ x_1\minus{}x_2\equal{}\pm 2\qquad(2)$. Combining this with $ (1)$ we get $ (x_1,x_2)\equal{}(2,4),(4,2)$ and thus the coordinates are $ (4,4)$ and $ (2,0)$.[/hide]

Also, for mhisno1, use the tags:

[code][hide=stuff to show to click]hidden stuff here[/hide][/code]

[hide="stuff to show to click"]hidden stuff here[/hide]

[quote="CircleSquared"][quote="mhisno1"]This is my first time ever posting on AOPS, so be happy :)

The way I tackled this problem worked out pretty well.

Knowing that the diagonals of rectangles are perpendicular bisectors of each other, you realize that diagonal CA shares a midpoint with diagonal BD.  Average the given points and determine the midpoint to be (3,2).  Use the slope (rise 2, run 1) to get (4,4) and (2,0).

Easy  (if only I could draw... now)[/quote]

Umm... the diagonals of rectangles are not perpendicular bisectors of each other.  Just pointing that out.  Only works for rhombi.[/quote]

well it oinly works for squares. and if you calculate the slope of the one diagonal you'll see that it's orthogonal to the other one, so we know that ABCD is a square which schould simplify things a lot ;)


Let $ n$ be a positive integer. Prove that $ 2^{n\minus{}1}$ divides
\[ \sum_{0\leq k < n/2} \binom{n}{2k\plus{}1}5^k.\]

The sum of the odd coefficients of $ P(x) \equal{} \frac{1}{ \sqrt{5} } (\sqrt {5} x \plus{} 1)^n$ is given by $ \frac {P(1) \minus{} P( \minus{} 1)}{2} \equal{} \frac {(\sqrt {5} \plus{} 1)^n \minus{} ( \minus{} \sqrt {5} \plus{} 1)^n}{2 \sqrt{5}}$.  Dividing by $ 2^{n \minus{} 1}$ gives

$ p_n \equal{} \frac{1}{ \sqrt{5} }\left( \left( \frac {1 \plus{} \sqrt {5}}{2} \right)^n \minus{} \left( \frac {1 \minus{} \sqrt {5}}{2} \right)^n \right) \equal{} F_n$,

the Fibonacci sequence.

An easier version of the (straightforward enough) http://www.mathlinks.ro/viewtopic.php?t=74382 .

  darij


if I'm right.
It can be proved by [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=64933]http://www.mathlinks.ro/Forum/viewtopic.php?t=64933[/url]
it is also useful to find the maximum


Sum of bases are definitely not equal to sum of legs in all isosceles trapezoids.

I think that the condition is that in the trapezoid the sum of bases has to be equal to the sum of legs.

cats... wrote:Can you inscribe a circle inside of every isosceles trapezoid?
Are the sum of the bases = to the sum of the legs, for all isosceles trapezoids?
I know that this is true for ones with a circle inscribed in it, but I am wondering if this is true for all.  If the answer to my first question is 'yes', then the 2nd question would be yes as well.
If the answer to the first question is no, what are the conditions that allow you to inscribe a circle in an isosceles trapezoid?
thanks.

Listen, you have a lot of freedom drawing an isoceles trapezoid -- you should be able to see just by drawing some of them that you [hide]cannot inscribe a circle in all of them.  For example, try one with bases 1000 and 999 and edges of lenth 1.  This should take care of the first three bits.  As for the last one, the coditions are that the sum of the bases equals the sum of the legs.  You can express this in other ways (for example, in terms of angles and sides) if you just play around with it a little -- you should be able to do this on your own.[/hide]

Actually, this reminds me of a problem I have done last year...  I think it was in Mu Alpha Theta...

A circle is inscribed in an isosceles trapezoid with bases 8 and 24.  Find the radius of the circle.  (The inscribed circle is tangent to both bases and both legs.)

We can use a circumscribed isosceles trapezoid to prove AM-GM-HM for 2 numbers. Try to prove these:

The line connecting the middlepts of the legs = (b+B)/2

The diameter of the incircle=(bB)^1/2

The line connecting the pts of tangency of te incircle with the legs = 2bB/b+B

Here b, B are the small and big base respectively. I'm not sure if "legs" means what I think it does:the 2 sides of the trapezoid different from the bases. We can use the second question to find the radius of the circle in the problem WarpedKlown1335 posted.

grobber wrote:
[quote]We can use a circumscribed isosceles trapezoid to prove AM-GM-HM for 2 numbers. Try to prove these:

The line connecting the middlepts of the legs = (b+B)/2

The diameter of the incircle=(bB)^1/2

The line connecting the pts of tangency of te incircle with the legs = 2bB/b+B[/quote]

Umm...it's really simple using coordinate proofs.

Well, I didn't exactly say it was difficult, did I? :D  :D  :D


If $ f (x) \plus{} 3 f (1\minus{} x) \equal{} x^2 \plus{} 4x \plus{} 7$

Find $ f (x)$

[hide="hint"]
Substitute y = 1-x, then you get some linear equations you can solve.[/hide]

[quote="pythag011"]
Substitute y = 1-x, then you get some linear equations you can solve.[/quote]
I don't really think that it is going to help...rather differentiating should work...i guess. :huh:

You don't know that $ f$ is differentiable.  What's wrong with pythag011's suggestion?  Have you actually tried it?

Oops...sorry :blush: I misunderstood what pythag011 said. Thanks!

So the [hide="solution"]
$ y\equal{}1\minus{}x$
We have
$ f(y)\plus{}3f(1\minus{}y)\equal{}y^2\plus{}4y\plus{}7$ (1)
And
$ f(1\minus{}y)\plus{}3f(y)\equal{}(1\minus{}y)^2\plus{}4(1\minus{}y)\plus{}7\equal{}y^2\minus{}6y\plus{}12$ (2)
So from (1) we have $ f(1\minus{}y)\equal{}\frac{y^2\plus{}4y\plus{}7\minus{}f(y)}{3}$ plug this thing to (2) and simplify we get
$ f(x)\equal{}\frac{2x^2\minus{}22x\plus{}29}{8}$
Am I right? And I have a question, Why when you look at this problem, you know let $ y\equal{}1\minus{}2$? because of experience or .........?
[/hide]


function
Support
real analysis
real analysis unsolved

How can we find the comon point of the graphs of the function $f(x) =-x^{3}$ and it's inverse function.
 A Greek mathematician asserts that these graphs have only one common point , namely on the line $y=x$ . He supports his opinion by saying that the function
   $f^{-1}(y)$ and  $f^{-1}(x)$ are different ,because their graphs are drawn in differrent directions.When you draw $f$ , the inverse is far ect .Have you ever heard something like this?Please talk it with your teachers !
 babis

If a point $(a,b)$ is common to the graphs $y=f(x)$ and $x=f(y)$, then $a=f(b)$ and $b=f(a)$. In general, such points need not lie on the line $y=x$ (consider $f(x)=-x$).

If $a=f(b)$ and $b=f(a)$, then $a$ satisfies the equation $a=f(f(a))$. Try solving this equation with $f(x)=-x^{3}$ and you will find two more points of intersection.


Moderator's Note - Post has been modified due to the similarity of the problem to a problem on a camp application.

It might have been good not to have switched variables from a to x right in the middle.

I don't know what exactly the policy is, but you may want to delete this problem/post because the problem posted is equivalent to a problem off of the PROMYS application.

that question could be popular (as I have seen several of the PROMYS application problems in books that I've read), but it is better to leave it deleted so that people don't stumble onto this forum and get a free answer to the app problem.

[hide]our teacher gave the  problem  as an extra credit.. lol can u guys tell us the website from where he is taking them ?  so we can be ready in advance hehe

btw whats PROMYS application? heres google search results...

PDF] PROMYS

File Format: PDF/Adobe Acrobat - View as HTML

... 9. Now that you have tried all of the problems, tell us which problem appealed to

you the most and why. Page 7. PROMYS Recommendation Form To be completed by ...

math.bu.edu/people/promys/Application04.pdf - Similar pages

PROMYS for TEACHERS

... Weekly problems sessions run by PROMYS staff help teachers pull together

threads of ideas from the problem sets and focus on the big ideas. ...

math.bu.edu/people/promys/PFTInformation.html - 12k - Cached - Similar pages

[ More results from math.bu.edu ]

lol uhmm.  n^4+n^3.... is seen in the first google result. and the second problem he gave us is also from there 3^3^3.... omg haha sry guys didnt know that. the next one we wre going to post 3^3^3... but anyway thanks fo the help on the first.. we wont help in plagiarising...[/hide]

Don't worry about it, the PROMYS people did not make up all of their questions either.  But as I said, it would be unfair to them if somebody posted a solution to one of their problems, as people could copy it and it would skew their results.

If a teacher assigns a problem as extra credit, I don't think you should ask other people how to solve the problem.  Unless you are planning to give your extra credit points to the solver...


hello, one solution is
$ x\equal{}\frac{1}{2}(12\plus{}4\sqrt{5})^{\frac{1}{3}}\minus{}1$
Sonnhard.

hello, yes of course, the other real solution is
$ x\equal{}\frac{1}{2}(12\minus{}4\sqrt{5})^{\frac{1}{3}}\minus{}1$
Sonnhard.


function
topology
real analysis
real analysis unsolved

let f be a continuous real valued function defined on a connected metric space M and the image of f is a subset of the integers, show that f is a constant function

The image of the continious function of every connected space is also connected, by the only only connected subset of integers is just one of this integers, so $f \equiv const$

f(M) connected -> M is an interval -> costant  :)

Let's pretend we don't know the theorems quoted by eugene and kotfare, and start from scratch.

Let $x_0$ be an arbitrarily chosen element of $M$ and let $n=f(x_0).$

$A=\{x\in M: f(x)=n\}$ is the inverse image of a closed set, hence closed.

But if $|f(x)-n|<\frac12,$ then $f(x)=n$ because there are no other integers within a distance of one half of $n.$ That means we can also write

$A=\left\{x\in M: |f(x)-n|<\frac12\right\}.$

This is the inverse image of an open set, hence open.

Since $M$ is connected, the only sets in $M$ that are both open and closed are the empty set and $M$ itself. $A$ is both open and closed, and we have constructed it to be nonempty. Thus, $A=M$ and $f(x)=n$ for all $x\in M.$

thanks for the help kent. rite now i have a course in topology( point set) and i'm finding it a bit difficult. i seem to follow the proofs of the theorems but a lot of times i dont seem to be able to do the excersises. i'd appreciate it if any of you here could give me a few tips to do well, thanks in advance


A polyhedron $P$ is given in space. Find whether there exist three edges in $P$ which can be the sides of a triangle. Justify your answer!

[i]Barbu Berceanu[/i]

Yes

Suppose $e_1,\dots, e_n$ are length of the edges in non-increasing order. COnsider the 2 faces that share the edge $e_1$. So $e_2+\dots e_n>2e_1$. (Write the triangle inequlaity for the 2 faces) Now beacuse $e_i,e_{i+1},e_{i+2}$ can not be edges of triangle so $e_{i+1}+e_{i+2}\leq e_i$ and $2(e_2+\dots+e_n)=e_2+(e_2+e_3)+\dots+(e_{n-1}+e_n)+e_n$ and $e_2+(e_2+e_3)+\dots+(e_{n-1}+e_n)+e_n\leq e_2+e_1+e_2+\dots +e_{n-2}+e_n$
Therefore $e_2+e_3+\dots+e_n\leq e_1+e_2-e_{n-1}<e_1+e_1+0=2e_1$.
Contradiction prove the problem and there exist 3 edges that can be sides of triangle.


function
advanced fields
advanced fields unsolved

Hi all,

has somebody an idea to the following problem?

[b]f[/b] : G -> \Omega analytic,
[b]phi[/b] : \Omega -> R is subharmonic.
Show: phi  :^o: f is subharmonic if f is one-one.
What happens if f'(z) :!=: 0 for all z in G?

Thanks!

Here's a useful formalism. Define the following differential operators:

$\frac{\partial}{\partial z}=\frac12\left(\frac{\partial}{\partial x} -i\frac{\partial} {\partial y}\right)$

$\frac{\partial}{\partial \overline{z}}=\frac12\left(\frac{\partial}{\partial x} +i\frac{\partial} {\partial y}\right)$

If $f(z)$ is an analytic function, then $\frac{\partial f}{\partial z}=f'(z)$ and $\frac{\partial}{\partial \overline{z}}=0.$ In fact, $\frac{\partial f}{\partial \overline{z}}=0.$ is precisely the Cauchy-Riemann equations.

By direct calulation, $\frac{\partial^2}{\partial z\partial\overline{z}}=\frac14\left( \frac{\partial^2}{\partial x^2}+\frac{\partial^2}{\partial y^2}\right)$. That's (a positive constant times) the Laplacian. So we can write the condition that $f$ is subharmonic as $\frac{\partial^2f}{\partial z\partial\overline{z}}\ge 0.$

Now suppose $\varphi$ is subharmonic and $f$ is analytic. For the sake of notation, let $w=f(z).$

$\frac{\partial}{\partial z}\varphi\circ f=\frac{\partial\varphi}{\partial w} \frac{\partial w}{\partial z}+\frac{\partial\varphi}{\partial\overline{w}} \frac{\partial \overline{w}}{\partial z}=\frac{\partial\varphi}{\partial w} w'$

$\frac{\partial^2}{\partial\overline{z}\partial z}\varphi\circ f= \frac{\partial^2\varphi}{\partial w^2}\frac{\partial w}{\partial\overline{z}}w' + \frac{\partial^2\varphi}{\partial\overline{w}\partial w}\frac{\partial\overline{w} }{\partial\overline{z}}w' + \frac{\partial\varphi}{\partial w}\frac{\partial w'}{ \partial \overline{z}}$

$=\frac{\partial^2\varphi}{\partial\overline{w}\partial w}|w'|^2.$

It is clear that this is $\ge 0.$ The requirement that $f$ be (locally) invertible would seem to have to do with being strictly subharmonic  - that is having the Laplacian be positive.


Gauss
modular arithmetic
algebra
system of equations
number theory
Quadratic Residues

The positive integers $a$ and $b$ are such that the numbers $15a+16b$ and $16a-15b$ are both squares of positive integers. What is the least possible value that can be taken on by the smaller of these two squares?

The answer is $231361$ :
$a = 14911,$
$b = 481.$

$15 \cdot 14911 + 16 \cdot 481 = 231361 = 481^2,$
$16 \cdot 14911 - 15 \cdot 481 = 231361 = 481^2.$

Now, let us prove it.
We have :
$E_1 : 15a + 16b = x^2,$
$E_2 : 16a - 15b = y^2.$

$E_1^2 + E_2^2 \implies 481(a^2+b^2) = x^4 + y^4.$

So $x^4 + y^4 = 0 \mod 13 \cdot 37.$

But, this implies $x^4 + y^4 = 0 \mod 13$ and $x^4 + y^4 = 0 \mod 37$ that is, since these are primes, and taking $x$ and $y$ to be non-zero in $\mathbb{Z}/13\mathbb{Z}$ and $\mathbb{Z}/37\mathbb{Z}$ :
$\left(\frac xy \right)^4 = -1 \mod 13$ and $\left(\frac xy \right)^4 = -1 \mod 37.$

But, this is impossible, which implies that $x$ and $y$ are both divisible by $13$ and $37,$ hence $x = 481u$ and $u = 481v,$ hence $a^2 + b^2 = 481^3(u^2+v^2).$

The possible minimum for $\min(u, v)$ is $1.$
But, $1^2 + 31^2 = 2 \cdot 481 \implies 481^2 + (31 \cdot 481)^2 = 481^3(1^2 + 1^2).$

And, (today's a lucky day :) ), this necessary condition happens to be sufficient, giving the result announced in the very beginning of this post.

[quote="Peter"]The positive integers $ a$ and $ b$ are such that the numbers $ 15a \plus{} 16b$ and $ 16a \minus{} 15b$ are both squares of positive integers. What is the least possible value that can be taken on by the smaller of these two squares?[/quote]

 We characterize the set
\[ \mathcal{S} \equal{} \{\; (a,b)\;\vert\; 15a \plus{} 16b \equal{} x^{2},\; 16a \minus{} 15b \equal{} y^{2}\;\text{for some}\; x,y\in\mathbb{N }\;\}.
\]
Let $ (a,b)\in\mathcal{S}$. We can find positive integers $ x$ and $ y$ such that $ 15a \plus{} 16b \equal{} x^{2}$ and $ 16a \minus{} 15b \equal{} y^{2}$.  After solving the system of equations $ 15a \plus{} 16b \equal{} x^{2}$, $ 16a \minus{} 15b \equal{} y^{2}$, we obtain
\[ a \equal{} \frac { 15x^{2} \plus{} 16y^{2}}{15^{2} \plus{} 16^{2}} \equal{} \frac { 15x^{2} \plus{} 16y^{2}}{13\cdot 17},\; b \equal{} \frac {16x^{2} \minus{} 15y^{2}}{15^{2} \plus{} 16^{2}} \equal{} \frac {16x^{2} \minus{} 15y^{2}}{13\cdot 17}.
\]
Now, we have to work modulo $ 13$ and modulo $ 17$.

[b] Step 1.[/b] First, we work modulo $ 13$. We need to solve the system of congruences
\[ 15x^{2} \plus{} 16y^{2}\equiv 0\; (mod\; 13)\;\;\text{and}\;\; 16x^{2} \minus{} 15y^{2}\equiv 0\; (mod\; 13).
\]
The first equation reads $ 2x^{2} \plus{} 4y^{2}\equiv 0\; (mod\; 13)$ or $ x^{2}\equiv \minus{} 2y^{2}\; (mod\; 13)$. The second equation reads $ 3x^{2} \minus{} 2y^{2}\equiv 0\; (mod\; 13)$ or $ 3x^{2}\equiv 2y^{2}\; (mod\; 13)$. We apply [b]Gauss Elimination[/b]. We compute $ 3 ( \minus{} 2y^{2})\equiv 2y^{2}\; (mod\; 13)$ or $ 8y^{2}\equiv 0\; (mod\; 13)$. This implies that $ y\equiv 0\; (mod\; 13)$. Also, we find that $ x^{2}\equiv \minus{} 2y^{2}\equiv 0\; (mod\; 13)$ so that $ x\equiv 0\; (mod\; 13)$. We conclude that $ x\equiv y\equiv 0\; (mod\; 13)$ is the unique solution of the system of congruences.

 \textsc{Step 2.} Second, we work modulo $ 17$. We need to solve the system of congruences
\[ 15x^{2} \plus{} 16y^{2}\equiv 0\; (mod\; 17)\;\;\text{and}\;\; 16x^{2} \minus{} 15y^{2}\equiv 0\; (mod\; 17).
\]
The first equation reads $ \minus{} 2x^{2} \minus{} y^{2}\equiv 0\; (mod\; 17)$ or $ 2x^{2}\equiv y^{2}\; (mod\; 17)$. The second equation reads $ \minus{} x^{2} \plus{} 2y^{2}\equiv 0\; (mod\; 17)$ or $ x^{2}\equiv 2y^{2}\; (mod\; 17)$. Hence, we compute $ 2 ( 2y^{2})\equiv y^{2}\; (mod\; 17)$ or $ 4y^{2}\equiv 0\; (mod\; 17)$. This implies that $ y\equiv 0\; (mod\; 17)$. Also, we find that $ x^{2}\equiv 2y^{2}\equiv 0\; (mod\; 17)$ so that $ x\equiv 0\; (mod\; 17)$. We conclude that $ x\equiv y\equiv 0\; (mod\; 17)$ is the unique solution of the system of congruences.

 Combining results from [b]Step 1[/b] and [b]Step 2[/b], we can write $ x \equal{} 13\cdot 17 u$ and $ y \equal{} 13\cdot 17 v$ for some positive integers $ u$ and $ v$. Now, observe that
\[ 15a \plus{} 16b \equal{} x^{2},\; 16a \minus{} 15b \equal{} y^{2}
\]
becomes
\[ a \equal{} \frac { 15x^{2} \plus{} 16y^{2}}{13\cdot 17},\; b \equal{} \frac {16x^{2} \minus{} 15y^{2}}{13\cdot 17}
\]
or
\[ a \equal{} 13\cdot 17 (15u^{2} \plus{} 16v^{2}) ,\; b \equal{} 13\cdot 17 (16u^{2} \minus{} 15v^{2}).
\]
Hence, it follows that the set $ \mathcal{S}$ can be represented as
\[ \mathcal{S} \equal{} \{\; (a,b)\;\vert\; a \equal{} 13\cdot 17 (15u^{2} \plus{} 16v^{2}) ,\; b \equal{} 13\cdot 17 (16u^{2} \minus{} 15v^{2}), u,v\in\mathbb{N }\;\}.
\]
We therefore conclude that the minimum value is $ \left( 13\cdot 17\right)^{2}$.

 [b] Notes [/b]

 In the solution, we met the systems of congruences. We recall the congruences from [b]Step 1[/b]: $ 15x^{2} \plus{} 16y^{2}\equiv 0\; (mod\; 13)$, $ 16x^{2} \minus{} 15y^{2}\equiv 0\; (mod\; 13)$. There are many alternative ways to reach $ x\equiv y\equiv 0\; (mod\; 13)$.

  [b]Method 1.[/b]  One may use Brahmagupta-Fibonacci Identity:
\[ \left( A^{2} \plus{} B^{2}\right)\left( X^{2} \plus{} Y^{2}\right) \equal{} \left( AX \plus{} BY\right)^{2} \plus{} \left( AY \minus{} BX\right)^{2}.
\]
Indeed, we obtain
\[ \left({15}^{2} \plus{} {16}^{2}\right)\left( a^{2} \plus{} b^{2}\right) \equal{} \left( 15a \plus{} 16b\right)^{2} \plus{} \left( 16a \minus{} 15b\right)^{2} \equal{} x^{4} \plus{} y^{4}.
\]
Since $ {15}^{2} \plus{} {16}^{2} \equal{} 13\cdot 17$, we find that $ x^{4} \plus{} y^{4}$ is divisibly by $ 13$. We now apply the following result with $ p \equal{} 13$ to conclude that $ x\equiv y\equiv 0\; (mod\; 13)$.

[b]Proposition.[/b] Let $ p$ be a prime with $ p\equiv 5\; (mod\; 8)$. Suppose that $ a^{4} \plus{} b^{4}$ is divisible by $ p$ for some integers $ a$ and $ b$. Then, both $ a$ and $ b$ are divisible by $ p$.

[b] Proof. [/b] Assume to the contrary that at least one of them are not divisible by $ p$. Since $ p$ divides $ a^{4} \plus{} b^{4}$, we see that none of them are divisible by $ p$. Fermat's Little Theorem yields that $ a^{p \minus{} 1}\equiv b^{p \minus{} 1}\equiv 1\; (mod\; p)$. Since $ p\equiv 5\; (mod\;8)$ or since $ \frac {p \minus{} 1}{4}$ is odd, we have $ ( \minus{} 1)^{\frac {p \minus{} 1}{4}} \equal{} \minus{} 1$. Since $ p$ divides $ a^{4} \plus{} b^{4}$, we obtain
\[ a^{4}\equiv \minus{} b^{4}\; (mod\; p).
\]
Raise both sides of the congruence to the power $ \frac {p \minus{} 1}{4}$ to obtain
\[ a^{p \minus{} 1}\equiv ( \minus{} 1)^{\frac {p \minus{} 1}{4}}b^{p \minus{} 1}\equiv \minus{} b^{p \minus{} 1}\; (mod\; p).
\]
or
\[ 1\equiv a^{p \minus{} 1}\equiv \minus{} b^{p \minus{} 1}\equiv \minus{} 1\; (mod\; p).
\]
This is a contradiction because $ p$ is an odd prime. Therefore, both $ a$ and $ b$ are divisible by $ p$.

 [b]Method 2.[/b] We now work on the field $ \mathbb{Z}/{13\mathbb{Z}}$. (Since $ 13$ is prime, we know that the ring $ \mathbb{Z}/{13\mathbb{Z}}$ is a field. We identify $ \overline{\alpha}\in\mathbb{Z}/{13\mathbb{Z}}$ with $ \alpha$.) The above congruences become
\[ 2x^{2} \plus{} 3y^{2} \equal{} 0\;\;\text{and}\;\; 3x^{2} \minus{} 2y^{2} \equal{} 0.
\]
Of course, [b]Gauss Elimination[/b] works. However, we offer an alternative way. Observe that
\[ \left[\begin{array}{cc}x^{2} & y^{2} \\
\minus{} y^{2} & x^{2}\end{array}\right]\left[\begin{array}{c}2 \\
3\end{array}\right] \equal{} \left[\begin{array}{c}0 \\
0\end{array}\right].
\]
This implies that  $ \left[\begin{array}{cc}x^{2} & y^{2} \\
\minus{} y^{2} & x^{2}\end{array}\right]$ has zero determinant so that $ x^{4} \plus{} y^{4} \equal{} 0$. We compute
\[ x^{12} \equal{} \left( x^{4}\right)^{3} \equal{} \left( \minus{} y^{4}\right)^{3} \equal{} \minus{} y^{12}
\]
If $ y\neq 0$, then we also have $ x \equal{} 0$. Hence, we obtain $ 1 \equal{} x^{12} \equal{} \minus{} y^{12} \equal{} \minus{} 1$, which is a contradiction. Therefore, we get $ y \equal{} 0$ and so $ x \equal{} 0$.

Hi Ideahitme,

I'am sorry to say this but it seems to me that there is something wrong in your solution

Namely,

                                15^2 + 16^2 = 481

                            but

                                       481 = 13 x 37

( and not as you write 13 x 17)

Thus we work modulo 13 and 37.

So, in   Step 2  we   consider

                          15x^2   +  16 y ^2  =   0   mod 37
and
                          16x^2  -      15y^2 =   0    mod 37

 :lol:  :wink:

[quote="mathmanman"]$ \left(\frac xy \right)^4 \equal{} \minus{} 1 \mod 13$ and $ \left(\frac xy \right)^4 \equal{} \minus{} 1 \mod 37.$[/quote]It took me really long to realize these were fractions and not L\'egendre symbols.

Just posting this for the next person.

\[ 15a \plus{} 16b \equal{} x^2,16a \minus{} 15b \equal{} y^2\Rightarrow (15^2 \plus{} 16^2)a \equal{} 15x^2 \plus{} 16y^2
\]
Now $ 15^2 \plus{} 16^2 \equal{} 481 \equal{} 13\cdot 37$ so we need the congruences
\[ 15x^2 \plus{} 16y^2\equiv 0\pmod{p}
\]
for each of $ p \equal{} 13,37$. In each case, if $ p$ divides $ x$, then $ p$ divides $ y$ as well. Otherwise, we get
\[ (4yx^{ \minus{} 1})^2\equiv \minus{} 15\pmod{p}
\]
We can check (using QR for example, or the long way... :roll: ) that -15 is not a square modulo either prime, so we necessarily find that 481 divides both $ x,y$. But in this case, if $ x \equal{} 481m,y \equal{} 481n$, then there is always an integer solution for $ a,b$, namely
\[ a \equal{} 481(15m^2 \plus{} 16n^2),b \equal{} 481(16m^2 \minus{} 15n^2)
\]
In particular, there's a positive integer solution for $ m \equal{} n \equal{} 1$, that is, $ x \equal{} y \equal{} 481$, for $ a \equal{} 31\cdot 481,b \equal{} 481$. Since $ x,y$ positive and divisible by 481, the minimum is $ \boxed{481}$.

Let $15a+16b=m^2$ and $16a-15b=n^2.$
Sum up their squares to get $$m^4+n^4=481(a^2+b^2)=13\cdot 37(a^2+b^2).$$ So $13, 37 \mid m^4+n^4.$

[b]Claim:[/b] $13, 37\mid m+n.$
[i]Proof.[/i] Assume the contrary that $13\nmid m+n.$ The case with 37 is similar. So we have $$m^4\equiv -n^4\pmod{13} \implies m^{12}\equiv- n^{12} \pmod{13}.$$ By Fermat's we get the contradiction that $2\equiv 0 \pmod{13}.$ $\blacksquare$

Let $m=481x, n=481y.$ So $$a=481(15x^2+16y^2) \text{ and } b=481 (16x^2-15y^2).$$ For the least, set $x=y=1,$ to get $$a=14911 \text{ and }b=481 \implies b^2=231361.$$


function
integration
induction
calculus
limit
real analysis
real analysis solved

Let f:[a,b]->R be a Riemann-integrable function s.t. there is an A>0 for which |\int{a->x}f(t)dt|>=A|f(x)| for all x\in[a,b]. Show that f(x)=0 for all x\in[a,b].

Let F(x)= \int (a,x) f(t)dt and let B=1/A. Then |f(x)|<=B|F(x)| for all x. Take M=supf(t), where t is taken in [a,b]. This exists and is finite, since f is integrable. We have |f(x)|<=B* \int (a,x) |f(t)|dt<=BM(x-a). Then |f(x)|<=B|F(x)|<=B* \int (a,x) |f(t)|dt<=B^2M(x-a)^2/2!. By an easy induction we can find that for any x and n we have |f(x)|<=B^n*M*(x-a)^n/n!. For fixed x take n very large. You will find that f(x)=0. Finish!

No Harazi ! You wrote " Take M=supf(t), where t is taken in [a,b]. This exists and is finite, since f is integrable."  That's false !

 Take for ex. f(t) = 1/ \sqrt(t-a) if t>a , f(a)=1 ...... Try again .. :D

...............

That's strange, since I know that we cannot speak about Riemann integrability for unbounded functions. But if you say so, then I must be wrong.

Diogene a fonction f:[a,b]-->R wich is Riemann integrable on the compact
[a,b] is bounded, so M= sup_[a,b] f exist and it is finite.

Thanks, Moubinool, I really started to ask myself strange questions about integrability.

There other definitions of other kinds of integrability which don't require f being bounded, but it's not the case for Riemann-integrability.

Yes Grobber, I don't know how to say in english in french "intgrale impropre" maybe improper integral

Let f:]a,b] -->R locally integrable we consider F(x) =  \int _[x,b]f(t)dt
if   \lim_(x->a) F(x) = k exist and it is finite real, we say that the improper
integral  \int _[a,b]f(t)dt converge, and  \int _[a,b]f(t)dt = k

Example:

f:]0,1] -->R, f(t) = 1/ \sqrt t is unbounded on ]0,1]

 \lim (x->0+) \int _[x,1]1/ \sqrt t dt = \lim (x->0+) 2 (1 -  \sqrt x) = 2

[quote="Moubinool"]Yes Grobber, I don't know how to say in english in french "intgrale impropre" maybe improper integral[/quote]
Hi Moubi, you got it right. It's said improper integral in here in US as well ;)


Angelina Joile and Brad Pitt are together or not?will the marry or not?
i heard that Brad is looking after Angelina's Children.(i think their name are Madox,Zahra).is it right?

what does this have to do with Music and Art? :?

I agree with you math92. Anyway,from what i have heard so far, it seems that they are togheter. More than that, Some people say that Angelina is pregnant. ;)

I'll move this to Games and Fun Factory.

Even better, move it to the trashy gossip factory. ;)

You should know considering your the moderator  :P  , jk , AoPs hasn't anticipated such things...

Let's ah...keep what belongs on People magazine out of the boards. :)


inequalities
real analysis
algorithm
number theory
calculus
calculus computations

1 Using the Axioms for real numbers
   a.) prove that $(-a)(-b) = ab$.
   b.) If $a < b$ and $0 < c < d$, then $ac < bd$.

2.Prove that if $0 \leq  a \leq  \frac{1}{n}$, for $\forall n \in Z^{+}$, then $a = 0$.

I think these type of excercises are boring, but for 1 use distributivity to show that $(-a)(b)+ab = 0$. SImilarly $(a)(-b)+ab = 0$. In conclusion $(-a)(-b) =-(-(ab))$. For any $x$, $-(-x))+(-x) = 0$ so $-(-x) = x$.

#1, which Kalle has dealt with, is actually an algebra question rather than an analysis question. The background you're assuming is the axioms of a field.

#2 is an analysis question. Here's my hint: try to write out the contrapositive, and pay particular attention to what happens to the quantifiers $\forall$ and $\exists$ when you negate a statement.

The contrapositive is "If $a>0,$ then ____ "

(This also has something to do with the Archimedean property of $\mathbb{R}.$)

The inequality is equivalent to $0\le an\le 1$.

The Archimedean property of real numbers states that for real $a, b$, such that $a>0$, there exists a natural number $n$, such that $an>b$.

[hide="Proof"]Let $A$ be the set of all number of the form $an$, and let $b$ be an upper bound of $A$, then $A$ is bounded above and therefore has the least upper bound property, let $\alpha =\sup A$, then $\alpha-a<\alpha$, so $\alpha-a$ is not an upper bound of $A$, and thus $\alpha-a<am$ for some $m\in\mathbb{N}$, but that implies $\alpha<am+a=a(m+1)$,  a contradiction.  (If I remember correctly, this is the same way Rudin proves the theorem.) [/hide]

Anyway, assuming $a>0$, we have $an>1$ for some $n\in\mathbb{N}$, a contradiction, so $a=0$.

Jimmy: you proved the $\mathbb{R}$ had the Archimedean property by using the completeness of the real numbers.

New challenge: prove that $\mathbb{Q}$ has the Archimedean property. (Note that I took away your "least upper bound" tool but may have given you some other things to work with.)

I'm not sure this is the best argument, but here it is: The Archimedean property can be restated as saying there are no non-zero infinitesimals in $\mathbb{R}$.

So, assume that the Archimedian property does not hold on $\mathbb{Q}$, then there exists some non-zero infinitesimal $p$ in $\mathbb{Q}$, but $p\not\in\mathbb{R}$, a contradiction.

Edit:  Here's another approach, because $\mathbb{Q}$ is dense in $\mathbb{R}$, for some rationals $p$ and $q$, we have:

$an>pn>b>q$ for real $a, b$ and some $n\in\mathbb{N}$.

It's not very satisfying to go back and rely on the real numbers as a crutch. This is essentially a number theory argument and is equivalent to proving the division algorithm: if $a$ is an integer and $b$ a positive integer, then there exist unique integers $q$ and $r$ such that $a=qb+r$ and $0\le r<b.$


[quote="Interval"]We read miles per hour in many word problems.

What exactly does that mean?  I bet there are many students that have no idea what they are reading.

Sample:

A car travels 55 miles per hour.

Does that mean that the car travels the distance of 55 miles every hour that passes while driving?[/quote]

Yes.

[quote="Interval"]We read miles per hour in many word problems.

What exactly does that mean?  I bet there are many students that have no idea what they are reading.

Sample:

A car travels 55 miles per hour.

Does that mean that the car travels the distance of 55 miles every hour that passes while driving?[/quote]
[hide]Yes, that means a car can travel 55 miles in the time of one hour.

This comes from the equation rate equals distance over time $r=\frac{d}{t}$. In units this is $\text{miles per hour}=\frac{\text{miles}}{\text{hour}}$.

Miles per hour is just another way of saying miles/hour.[/hide]
I guess it's kinda pointless to hide it...... :P

[quote="Interval"]We read miles per hour in many word problems.

What exactly does that mean?  I bet there are many students that have no idea what they are reading.

Sample:

A car travels 55 miles per hour.

Does that mean that the car travels the distance of 55 miles every hour that passes while driving?[/quote]

Those problems kinda like assume you are travelling constant speed unless otherwise mentioned.


It is given that the polynomial $p(x)=x^3+ax^2+bx+c$ has three distinct integer roots and $p(2002)=2001$
Let $q(x)=x^2-2x+2002$
It is also given that the polynomial $p(q(x))$ has no real roots.

Determine the value of $a$

There doesn't seem to be a unique answer.  Maybe I am wrong, but you might want to recheck it.

The problem is correct, only that i don't know how to do it.   :D

Nice problem.

[hide]
Let $x_1,x_2,x_3$ be the three distinct integer roots of $p(x)$, then $(2002-x_1)(2002-x_2)(2002-x_3)=p(2002)=2001=3\cdot23\cdot29$. We will prove that $2002-x_i  > 1$ for $i=1,2,3$. Therefore, $6006+a = (2002-x_1)+(2002-x_2)+(2002-x_3)=3+23+29 = 55$. So $a= -5951$.

If $2002-x_i \leq 1$, then  $x_i\geq 2001$. Then $q(x)=x_i$ has a real root since $q(x)=(x-1)^2+2001$. Contradicting to the assumption that $p(q(x))$ has no real roots.
[/hide]

[quote="probability1.01"]But $3 \cdot 23 \cdot 29$ is not the only factorization of 2001.  You also have $1 \cdot 69 \cdot 29$ and other such things.  And besides, the roots can be negative.[/quote]

That's why we need to show $2002-x_i > 1$.

[quote="probability1.01"]2002 - 1 = 2001 > 1, no?[/quote]

???

Three distinct integers, each > 1, multiplying together is a product of three distinct primes. What is the sum?

[quote="probability1.01"]Err... where does it say that the three distinct integers are greater than one?  :?[/quote]

Prove it if you didn't see it in my solution. Hint: use the assumption that p(q(x)) has no real roots.

You proved that 2002 - x > 1 though.. which isn't the same as x > 1...

[quote="probability1.01"]You proved that 2002 - x > 1 though...[/quote]

This is exactly what we need.

Oops.  I can't think straight :blush: .  Sorry.


can you help me with this ineq please?

$\left(a+\frac{2}{a}\right)^2+\left(b+\frac{2}{b}\right)^2 \geq \frac{81}{2}$

$a+b=1$

$a,b>0$

We want to find the minimum of the LHS. From AM-QM we have that $a^2 + b^2 \geq \frac{1}{2}$.
Rewrite the LHS as $a^2 + b^2 + 4\left(\frac{a^2 + b^2}{\left(\frac{1 - (a^2 + b^2)}{2}\right)^2}\right) + 8$.
Then the minimum is $\frac{81}{2}$.

Take a = (sinß)^2
hence
b = (cosß)^2

now open the square
for (sinß)^4+(cosß)^4 = 1- ((sin2ß)^2)/2
     convert (cosecß)^2 into (cotß)^2 +1 similarly sec into tan
      now for cot and tan use A.M > G.M
    You will automatically get the answer[/code]

[hide]
By RMS-AM Inequality, $\left( a+\frac 2a \right)^2 +\left( b+\frac 2b \right)^2 \geq \frac{\left( a+\frac 2a +b+\frac 2b \right)^2}{2}=\frac{\left(1+2\left( \frac 1a +\frac 1b \right)\right)^2}{2}$.

Now AM-HM gives $\frac 1a +\frac 1b \geq \frac{4}{a+b}=4\Rightarrow \left( a+\frac 2a \right)^2 +\left( b+\frac 2b \right)^2\geq \frac{(1+2\cdot 4)^2}{2}=\frac{81}{2}$.[/hide]


Solve in integers the equation $y^2(x^2+y^2-2xy-x-y)=(x+y)^2(x-y)$

The only solutions are (0,0), (9,27) and (12,24).

We note the solution (0,0).

Now we substitute $y=dy'$ and $x=dx'$ with $(y',x')=1$ and then we see that $y|(x'+y')^2(x'-y')$ so $y'=1$.

Then we'll get after some calculations: $d(x'-1)^2=(x'+1)x'^2$ and so $(x'-1)^2|x'+1$ and so $x'-1|2$ and so $x'=2,3$ and we will get the solutions (9,27) and (12,24).

It can't be $x'=-1,0$ because we will get $d=0$.


We have lots of apples, bananas, oranges and pears. How many ways can we can we pick $n$ fruit subject to:

The number of apples is even.
The number of bananas is a multiple of 5.
There are at most 4 oranges.
There is at most one pear.

[hide]Answer: $n+1.$
I will wait for others to post their solutions.

[Edit: I initially wrote $n$ which is wrong.]
[/hide]


geometry
circumcircle
parallelogram
trapezoid
congruent triangles
geometry unsolved

Let $ B,C$ be two fixed point on circle $ (O)$ and $ A$ is an animating point on arc $ BC$ (the greater one). $ E$ is an animating point inside $ \triangle ABC$ such that $ \widehat{EBA} \equal{} \widehat{ECA}$. Let $ M,N$ be the perpendicular projection of $ E$ on the inner and outer angle bisectors from vertex $ A$ of $ \triangle ABC$. Prove that the line $ MN$ always passes through a fixed point when $ A$ and $ E$ animating as described.

[b]HINT: [/b][hide]The fixed point is the midpoint of $ BC$. [/hide]

Sorry for my bad English, [b]mashimaru[/b], but I cannot understand clearly the statement of the problem :blush: . Could you give me the figure or sth :lol: ??

OK, I will give you the most useful one: the problem in Vietnamese: :lol:

Cho $ BC$ là dây cung cố định của đường tròn $ (O)$ và $ A$ di động trên cung lớn $ BC$ của $ (O)$. $ E$ là một điểm di động trong tam giác $ \triangle ABC$ sao cho $ \widehat{EBA}\equal{}\widehat{ECA}$. Gọi $ M,N$ là hình chiếu của $ E$ trên phân giác trong và ngoài từ $ A$ của $ \triangle ABC$. Chứng minh rằng $ MN$ luôn đi qua một điểm cố định khi $ A,E$ thay đổi như đã nói trên.

[b][size=100][color=DarkBlue]EQUIVALENT  PROBLEM.- A triangle $ \bigtriangleup ABC$ is given and let $ P$ be, the point inwardly to it, such that $ \angle PBA = \angle PCA$ and we denote as $ X,\ Y,$ the orthogonal projections of $ P,$ on the inner and outer angle bisectors of $ \angle A,$ respectively. Prove that the line segment $ XY,$ passes through the midpoint of $ BC.$[/color][/size][/b]

[b][size=100]PROOF.[/size][/b] – Because of $ \angle PBA = \angle PCA$ we conclude that the circumcircles $ (O_{1}),\ (O_{2}),$ of the triangles $ \bigtriangleup APB,\ \bigtriangleup APC$ respectively, are congruent.

We denote the points $ D\equiv (O_{1})\cap PX,\ E\equiv (O_{2})\cap PX$ and $ F\equiv (O_{1})\cap AY,\ Z\equiv (O_{2})\cap AY$ and it is  easy to show that $ DEZF$ is a parallelogram, from $ DE\parallel FZ$ and $ \angle DEZ = \angle APE = \angle DFZ.$

Also, it is easy to show that $ X,\ Y,$ are the midpoints of the segments $ DE,\ FZ$ respectively, from the isosceles triangle $ \bigtriangleup ADE$ $ ($ $ \angle ADE = \angle AED$ and $ \angle DAX = 90^{o} - \angle DAF = 90^{o} - \angle EAZ = \angle EAX$ $ )$ and the parallelogram $ XEZY$ $ ($ $ \angle PXY = \angle PAY = \angle PEZ$ $ ).$

$ \bullet$ Because of now, $ \angle BAF = \angle CAZ,$ we have $ BF = CZ$ and because of $ DF = EZ,$ we conclude that $ BD = CE$ and then, the triangles $ \bigtriangleup BDF,\ \bigtriangleup CEZ,$ are congruent.

Hence, based on the below [b][size=100]Lemma[/size][/b], in the configuration of the quadrilateral $ BCZF,$ with $ BF = CE$ and $ \angle DBF = \angle ECZ$ and $ \angle DFB = \angle EZC,$ we conclude that the line segment $ XY,$ passes through the midpoint $ M$ of $ BC$ and the proof is completed.

[b][size=100][color=DarkBlue]LEMMA. – A quadrilateral $ ABCD$ is given, with $ AD = BC$ and let $ \bigtriangleup ADE,\ \bigtriangleup BCF$ two congruent triangles with $ \angle EAD = \angle FBC$ and $ \angle EDA = \angle FCB,$ erected on its side-segments $ AD,\ BC$ respectively, outwardly ( or inwardly ) to it.  Prove that the line segment $ MN,$ where $ M,\ N$ are the midpoints of $ AB,\ CD$ respectively, bisects the segment $ EF.$[/color][/size][/b]

Kostas Vittas.

PS. I will post here later the easy proof ( by only the schema ) of the above [b][size=100]Lemma[/size][/b], I have in mind.

[quote="vittasko"][b][size=100][color=DarkBlue]LEMMA. – A quadrilateral $ ABCD$ is given, with $ AD \equal{} BC$ and let $ \bigtriangleup ADE,\ \bigtriangleup BCF$ two congruent triangles with $ \angle EAD \equal{} \angle FBC$ and $ \angle EDA \equal{} \angle FCB,$ erected on its side-segments $ AD,\ BC$ respectively, outwardly ( or inwardly ) to it.  Prove that the line segment $ MN,$ where $ M,\ N$ are the midpoints of $ AB,\ CD$ respectively, bisects the segment $ EF.$[/color][/size][/b][/quote]
I post only the schema, because of the proof of the above Lemma is very easy.

Kostas Vittas.

[quote="vittasko"][b][size=100][color=DarkBlue]EQUIVALENT  PROBLEM.- A triangle $ \bigtriangleup ABC$ is given and let $ P$ be, the point inwardly to it, such that $ \angle PBA \equal{} \angle PCA$ and we denote as $ X,\ Y,$ the orthogonal projections of $ P,$ on the inner and outer angle bisectors of $ \angle A,$ respectively. Prove that the line segment $ XY,$ passes through the midpoint of $ BC.$[/color][/size][/b]
[/quote]
Another proof: http://www.mathlinks.ro/viewtopic.php?t=256032

Lemma  [b]ABCD[/b] is a convex quadrilateral   AB=CD , E,F are the midpoint of AD,BC  EF // the bisector of angle [b] (AB,CD)[/b]

1.It is easy to acquire LKIJ is a parallelogram      KLPA,PAIJ are isosceles trapezoids
2. ∠IAB=∠KAC => BI=KC  ∠JAB=∠LAC => JB=CL
3.By angle chasing we get  ∠BQC=180-∠A  ∠BNC=2∠JAB=2∠LAC
 ∠KLC=180-CAK=180-(90-1/2∠A)=90+1/2∠A   1/2∠BQC+∠KLC=180
 1/2∠BNC=∠JAB=∠LAC    =>  the bisector of ∠BQC, ∠BNC are parallel to
Based on the lemma   the bisector of ∠BQC, ∠BNC are parallel to MX,MY respectively
Thus M,X,Y are collinear


function
geometry
geometric transformation
reflection
algebra
domain
conics

These are from a practice test on Functions. Totally confusing. :/

Help would be appreciated. Thanks in advance. :]

Here's the link. :O

http://img12.imageshack.us/img12/391/mathprep.png

[hide="1."]
1. $ f\left(\frac{2}{x+3}\right) = \frac{2}{x+3}+1$
You replace all the x's in the original equation with $ \left(\frac{2}{x+3}\right)$.
[/hide]
[hide="2."]
2.
$ f\left(\frac{1}{4x}\right)=\left(\frac{1}{4x}\right)^2-4\left(\frac{1}{4x}\right) \\
= \frac{1}{16x^2}-\frac{1}{x}$
[/hide]
[hide="3."]
3. To find the inverse of a function, you can reverse the x's and y's. (since inverse functions are reflections of each other across the line y=x).
If you let f(x)=y, you have the equation $ y=2\sqrt{x+4}$. The domain is $ x\ge-4$ and the range $ y\ge0$.
The inverse function will have the domain and range switched.
So the domain of the inverse function will be $ x\ge0$ and the range $ y\ge-4$.
Switching the x's and y's,
$ \usepackage{amsmath}
\begin{align*}
x&=2\sqrt{y+4} \\
x^2&=4(y+4) \\
x^2&=4y+16 \\
x^2-16&=4y \\
\frac{x^2-16}{4}&=y
\end{align*}$
However, the restriction on the domain is that $ x\ge0$
So $ f^{-1}(x)=\frac{x^2-16}{4}$ for $ x\ge0$.
[/hide]
[hide="4."]
4. You have the equation $ y=\frac{x+1}{x+2}$.
Domain is $ x\ne2$, range is $ y\ne1$.
So the domain of the inverse function is $ x\ne1$ and the range $ y\ne2$.
Switching the x's and y's,
$ \begin{align*}
x&=\frac{y+1}{y+2} \\
(y+2)x&=y+1 \\
yx+2x&=y+1 \\
yx-y&=-2x+1 \\
y(x-1)&=-2x+1 \\
y&=\frac{-2x+1}{x-1}$

So $ f^{-1}(x)=\frac{-2x+1}{x-1}$ and $ x\ne1$.
[/hide]
[hide="5."]
5. The function $ y=x^2-2x$ does not have a function as an inverse.
It's a parabola, and its inverse is a sideways parabola which is not a function.
However, you can still find the equation of the inverse, but it's not a function.
Switching the x's and y's,
$ x=y^2-2y$, a sideways parabola.
[/hide]


inequalities
algebra
polynomial
inequalities proposed

Find the greatest constant $ k$ such that the following inequality holds for $ a,b,c \in [1;k]$
$ 2(a^{3}b+b^{3}c+c^{3}a) \ge (ab^{3}+bc^{3}+ca^{3})+abc(a+b+c)$

The best possible maximal const k=3.89649276...,it is a root of the following polynomial :

32-48*k-115*k^2+56*k^3+342*k^4-100*k^5-259*k^6+36*k^7+8*k^8.

I found the best constant is $ k_{0}\approx 2.358088436$.
Can you post your solution? Thank you.


Let $ 2n$ distinct points on a circle be given. Arrange them into disjoint pairs in an arbitrary way and join the couples by chords. Determine the probability that no two of these $ n$ chords intersect. (All possible arrangement into pairs are supposed to have the same probability.)

The total number $ a_n$ of "good" pairings of $ 2n$ vertices is given by the $ n$th Catalan number $ \frac{(2n)!}{n!(n\plus{}1)!}$: it's quite clear that $ a_0 \equal{} a_ 1 \equal{} 1$, and then choose a fixed vertex and connect it to in all possible ways to see that $ a_{n \plus{} 1} \equal{} \sum_{i\equal{} 0}^n a_i a_{n \minus{} i}$.  The total number of pairings is just $ (2n \minus{} 1)!! \equal{} \frac{(2n)!}{2^n n!}$, so the answer is the ratio of these two, $ \frac{2^n}{(n \plus{} 1)!}$.


Consider six arbitrary points in space. Every two points are joined by a segment. Prove that there are two triangles that can not be separated.
[img]http://i38.tinypic.com/35n615y.png[/img]

Sketch:
Assume the contrary and after that consider a triangle of a minimum area,denote it as $ \phi$.The other three points must be outside the
$ \phi(DEF)$.Denote the trianlge formed by other three points as $ \gamma(ABC)$.Now consider two cases:
If $ \gamma$ contains $ \phi$ and if it doesn't.First case:
suppose that ray $ FE$ intersects $ BC$ at some point.Then clearly $ \triangle BFC$ contains $ E$ but it does not contain $ A$.Contradiction.
Second case:similar approach works here...some boring work with considering many cases.

We can consider the convex closure and work in cases. It's not hard to imagine that.


[quote="now a ranger"]UNC will win.

Duke always is overrated and at the end of the year loses to some team.[/quote]

see I like this guy HE KNOWS WHICH WAY IS UP

seems like you both know which way is DOWN

dude you do not have your head screwed on right

it is screwed on WRONG

I think having my head on right implies that it is screwed on wrong. Anyways, we all know that UNC just pulled off some voodoo magic or something last year. pretty sure that's not happening again. so i guess it's duke turn to win once again :)

[quote="Inspired By Nature"][quote="MysticTerminator"]wtf? we, uh, didn't win last year
I think it was the year before that we OWNED everybody[/quote]
Quick question, does BC stand for British Columbia? :maybe:[/quote]

No, Boston College. :)

oh I see, so all these teams are from colleges?  :)
btw, I was kidding when I said British Columbia, how can a province be a team? :lol:

[quote="not_trig"]well, ACC sucks this year so NO ONE!!!! MWAHAHAHAHAHA!!!

(except Duke, of course, which is not even up there  :mad: )[/quote]

if the ACC sucks, then the other leagues are basically elementary school teams.

um... Florida?

Ohio State?

Gonzaga? (wait didn't they beat UNC)

I don't think Ohio State does much in basketball.

Football is enough  :D

boy UNC vs. Georgetown what fun!

(sorry Arnav, but I have G-town winning in my bracket :wink: but i'll probably be wrong)

UNC just lost...

hahahahahahahahhaaha
 :rotfl:

hmm we apparently suck at overtime

it's like "oh no it's overtime we'd better stop making shots, huh"

oh well; at least got 3 rounds further than duke did

I THINK UCLA WILL PWN FLORIDA

(that's what I think...)

and g-town will pwn ohio st.

and g-town will pwn ucla, kinda

What is wrong with you?
don't worry you'll see on Saturday.

PSH

BTW ZOMG WE HAVE 2 PAGES ON THE FORUM NOW W00T

[quote="MysticTerminator"]unc women all the way![/quote].

can't disagree with that

erm okay w/e

...

at least they're ACC and in NC... -_-

(zomg these stupid Indiana middle schoolers are getting to my head!!)

i dunno man, rutgers owned like everybody they were supposed to lose to and fla is currently winning the ncaa mens championship game and owning osu by 11 at the half but what this has to do with womens basketball i don't know but i think that this is the year for black coaches i.e. the super bowl and i think the rutgers womens coach is black so they have to win.

i need to go to bed.  i need to stop disagreeing with arnav.

erm... wtf

florida won i'm so pissed cuz they won last year+football+again... WTF NO FAIR :rotfl:

and rutgers vs. tennessee - hopes rutgers wins cuz they beat duke which makes them pretty darn 1337

I told all of you that Florida will win the whole thing. Now what do you have to say?

that's what I thought


[i]These two problems are the algebra subject  from the Greek HMS phase one, which was held today[/i]

Okay, well considering that these problems are year 10 level, they shouldn't be hard at all for you guys.
So basically try to find more than one solution to each problem if you can (if there exist more than one solution)

[hide]
[u]Problem 1[/u]
Determine integers x,y,z such that 0=<x=<y=<z  (that is supposed to mean '0 is equal or less than x, x is equal or less than y.. and so on)    and
[b]xyz + xy + yz + zx + x + y + z = 44[/hide][/b]

[hide][u]Problem 2[/u]
If the real numbers x,y,z satisfy:
                            [b]x^2 - y = z^2   ,    y^2 - z = x^2    ,    z^2 - x = y^2 ,[/b]
Show that at least one of x,y,z is equal to zero[/hide]

Sorry if it looks messy or unorganized, I'm new here and i haven't got Latex yet.

For problem 1 you may write:
$ (x\plus{}1)(y\plus{}1)(z\plus{}1)\equal{}45$ so you just have to look up the divisors of $ 45$
For problem 2
Summing the expression we have $ x\plus{}y\plus{}z\equal{}0$
Then replace in the equations and it is easy to find that one is $ 0$
If you want ask for the detailed solutions

Daniel

I understand how you did the 1st one but could you go into detail for the second one?
So there is only one solution for each problem i suppose? What I'm trying to say is that there is no other different method i can use to approach these 2 problems..?

Thanks in advance.

Replace $ y\equal{}\minus{}x\minus{}z$ then
And we get $ (x\minus{}z\plus{}1)(x\plus{}z)\equal{}0$ if $ x\plus{}z\equal{}0$ $ y\equal{}0$
If $ x\minus{}z\equal{}\minus{}1$ then replacing $ y$ in the second equation
$ z(z\minus{}1\plus{}2x)\equal{}0$ if $ z\equal{}0$ we are finished. If not $ 1\minus{}z\equal{}2x\equal{}\minus{}x$ so $ x\equal{}0$
The proof is finished
Daniel

So in order for the proof to be complete, it is  enough to just take cases for when one of y,z,x is equal to 0?
I reached to that point by a different approach today while i was taking the exam but i wasn't sure that by just taking cases (i took for all y,x,z) i would provide a complete proof. So i tried to get to a contradiction assuming that neither of x,y,z = 0 , thus proving that one of the above cases that i showed must be correct

I showed that the only posibility is that at least one of $ x,y,z$ is $ 0$
Daniel


wat kind of a math problem is this? where did u get it?it doesnt like one. :maybe:

it looks like a chinese math problem. post in chinese country

refer to [url=http://www.artofproblemsolving.com/Forum/index.php?f=252]this link[/url] and post your question there.


Given Segment AB, with length $n$. Draw segments AC and BD, also with length $n$ which make $30^\circ$ angles with AB and intersect at E. Continue with this process, drawing segments from CD at $30^\circ$ angles, connecting their endpoints, repeating forever. Each time you construct these lines, two triangles ($\triangle ABE,  \triangle CDE$) are created. Is it possible to give a formula for the sum of the area of all of these triangles?

(this is what i do alot when im bored... i draw these little triangles in the margins. but i dont do the math :P )

[hide]Consider the first two triangles.

First triangle - $A_1=\frac12\cdot n\cdot\frac{n\sqrt3}6=\frac{n^2\sqrt3}{12}$

Second triangle - The two shorter sides are $\frac{(3-\sqrt3)n}3$, so the height is $\frac{(3-\sqrt3)n}6$ and the base is $(\sqrt3-1)n$. So $A_2=\frac12\cdot(\sqrt3-1)n\cdot\frac{(3-\sqrt3)n}6=\frac{(4\sqrt3-6)n^2}{12}$

So, the sum of these two is $\frac{(5\sqrt3-6)n^2}{12}$.

The sum of an infinite geometric sequence is $\frac a{1-r}$. We know $a=\frac{(5\sqrt3-6)n^2}{12}$ and $r=(\sqrt3-1)^2$ because the ratio of the areas of two similar parts is the ratio of corresponding sides squared.

So $\frac a{1-r}= \frac{\frac{(5\sqrt3-6)n^2}{12}}{1-(\sqrt3-1)^2}=\frac{\frac{(5\sqrt3-6)n^2}{12}}{2\sqrt3-3}=\boxed{\frac{(4+\sqrt3)n^2}{12}}$[/hide]

[quote="cincodemayo5590"][quote="nat mc"]that right?  [/quote]

Yep! That's right :D[/quote]
Cool! that is a weird problem

[quote="nat mc"]Cool! that is a weird problem[/quote]

:D yea, i thought of it while doodling in my notebook (not paying attention in english class  ;) ). Is it wierd in a good way?

hmm... maybe i should make more of these problems  :D