Please refer to the [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=10857]Getting Started Series Challenge Problems Introduction[/url]for an explanation of my objectives for this series of messages.

I hope this is fairly easy for most people visiting this forum, but let's make sure by trying to solve the problem. I can find much harder (and somewhat easier) problems if need be, so please let me know if this level is appropriate for you, by public post or by private message. This problem is adapted from Beginning Algebra 8th Edition by Margaret L. Lial and John Hornsby. Very similar, and even harder, problems can be found in the fourth grade volume of the Hua Loo-Keng School Mathematics Textbook series.

Problem One:

On the first day of summer tokenadult flies southwest from Minneapolis on an airplane that took off at the same time as A+MATH's airplane, which flies northeast. The plane flying A+MATH to the northeast flies 50 miles per hour faster than tokenadult's airplane. In thirty minutes, the planes are 275 miles apart. What is the speed of each airplane?

(For extra challenge, try to solve the whole problem without using any literal algebra, using only the block diagram problem-solving taught in Singapore, for example.)

Please show steps to your solution, and please put your solutions and steps in spoiler text. Have fun.

[hide]This is the same as if tokenadult was staying put and a+math was flying at 2x+50 mph.  2x+50 = 275*2.  x+25=275.  x=250.  Therefore a+maths speed is 300.  Tokenadult's is 250. [/hide]

I thought the simpifying (?) assumption at the start of Scrambled's solution was interesting.


function
calculus
derivative
limit
integration
real analysis
real analysis unsolved

Let $ f$ be any function convex and continuous over $ [a,b]$. Let $ S$ be the set of points for which $ f$ is not differentiable over $ [a,b]$. Is it necessary that $ S$ is discrete over $ [a,b]$?

We can show that $ S$ is a subset of a countable set, hence countable, provided we accept two easily proven facts about left and right derivatives of a convex function:

(1) $ D_l f \leq D_r f$ on $ [a, b]$.
(2) $ D_l$ and $ D_r$ are monotone increasing on $ [a, b]$.

The proof is then as follows. Since $ D_l f$ is monotone increasing on $ [a, b]$, it is continuous at all but a countable number of points in $ [a, b]$. Denote the set of all such points by $ A_l$. Similarly, we have the countable set $ A_r$ of points of discontinuity of $ D_r f$. Now define $ A \equal{} A_l \cup A_r$. Then both $ D_l f$ and $ D_r f$ are continuous on $ [a, b]\backslash A$. Take $ x_0 \in [a, b]\backslash A$ and let $ x \in [a, b]$ be such that $ x_0 < x$. Then we have that $ D_l f(x_0) \leq D_r f(x_0) \leq D_l (x)$. $ D_l f$ is increasing and hence $ \lim_{x \rightarrow x_0^\minus{}} D_l f(x)$ exists, with $ D_r f(x_0) \leq \lim_{x \rightarrow x_0^\minus{}} D_l f(x)$. Furthermore, since $ D_l f$ is continuous at $ x_0$, $ \lim_{x \rightarrow x_0^\minus{}} D_l f(x) \equal{} D_l(x_0)$. Hence $ D_l f(x_0) \leq D_r f(x_0) \leq D_l (x_0)$ for all $ x_0 \in [a, b]\backslash A$, or $ D_l f \equal{} D_r f$ on $ [a, b]\backslash A$. Hence the derivative of $ f$ exists for all points outside the countable set $ A$. The set of possible points of nondifferentiability $ S$ is a subset of $ A$ and thus is countable.

Thanks. But how does the countability of $ A$ imply that it is discrete? For example, the rationals are countable but not discrete.

It does not imply, because this is not true for convex function in general :wink:

Could you please provide me with a counterexample?

One can give ''analytical'' representation, but in general, you can take countable number straight (piecewise linear function) lines with increasing (but bounded!)  sequence of  line slopes.

Sorry, I'm not getting this; could you please construct an explicit example for me? The only constructions from linear functions that I can obtain are not dense over the reals... what am I missing?

An explicit example: let $ q(n)$ for $ n\equal{}1,2,\cdots$ be an enumeration of the rational numbers. Define $ g(x)\equal{}\sum_{q(n)\le x}2^{\minus{}n}$. This $ g$ is increasing, takes values in $ (0,1)$, and has a jump discontinuity at every rational number. Let $ f(x)\equal{}\int_0^x g(t)\,dt$. This $ f$ is convex, and $ f'$ has a jump discontinuity at every rational number.


algebra
polynomial
inequalities unsolved
inequalities

Let $P(z)= z^n + c_1 z^{n-1} + c_2 z^{n-2} + \cdots + c_n$ be a polynomial in the complex variable $z$, with real coefficients $c_k$. Suppose that $|P(i)| < 1$. Prove that there exist real numbers $a$ and $b$ such that $P(a + bi) = 0$ and $(a^2 + b^2 + 1)^2 < 4 b^2 + 1$.

http://www.kalva.demon.co.uk/usa/usoln/usol893.html

[b]Alternate solution :[/b]
Let $r_1, r_2, \ldots, r_n$ be the real roots of the polynom $P$ in $\mathbb{C}$. Thus, we may write :
\[ P(i) = (i - r_1)(i - r_2) \ldots (i - r_n), \]
hence,
\[ |i - r_1| \cdot |i - r_2| \cdot \ldots \cdot |i - r_n| < 1. \]
Since $P$ has real coefficients, its non-real roots can be pairwise gathered, each pair being constituted of two conjugate numbers. But, if $r \in \mathbb{R}$, $|i - r| = \sqrt{1 + r^2} \ge 1$. So, there exist two reals $a$ and $b$ such that $P(a + ib) = 0$ and
\[ 1 > |i - (a + ib)| \cdot |i - (a - ib)| = \sqrt{(a^2 + b^2 + 1)^2 - 4b^2}, \]
hence :
\[ 4b^2 + 1 > (a^2 + b^2 + 1)^2. \]


Define $ f(x) \equal{} x^3$ for all x. Verify the $ \epsilon \minus{} \delta$ criterion for continuity at each point $ x_0$.

fix $ \epsilon >0$ and $ x_0$, define $ M\equal{}(|x_0|\plus{}1)^2$ and let

$ \delta \equal{} \min( 1, \frac{\epsilon}{3M})$, so $ |x\minus{}x_0|<\delta$ implies

$ |f(x)\minus{}f(x_0)|\equal{}|x^3\minus{}x_0^3|\equal{}|(x\minus{}x_0)(x^2\plus{}xx_0\plus{}x_0^2)|<3M|x\minus{}x_0|< \epsilon$

[quote="kenn4000"]fix $ \epsilon > 0$ and $ x_0$, define $ M \equal{} (|x_0| \plus{} 1)^2$ and let

$ \delta \equal{} \min( 1, \frac {\epsilon}{3M})$, so $ |x \minus{} x_0| < \delta$ implies

$ |f(x) \minus{} f(x_0)| \equal{} |x^3 \minus{} x_0^3| \equal{} |(x \minus{} x_0)(x^2 \plus{} xx_0 \plus{} x_0^2)| < 3M|x \minus{} x_0| < \epsilon$[/quote]

where does M and $ 3M$ come from

How big can $ x^2\plus{}xx_0\plus{}x_0^2$ be?

[quote="jmerry"]How big can $ x^2 \plus{} xx_0 \plus{} x_0^2$ be?[/quote]

I suppose when $ x\equal{} x_0 \plus{} 1$


modular arithmetic
number theory unsolved
number theory

Let $ a,b,n$ be positive integers such that $ n$ divides $ a^n \minus{} b^n$.  Prove that $ n$ also divides $ (a^n\minus{}b^n)/(a\minus{}b)$

[quote="SaYaT"]1case if $ n$ doesn't divide $ a \minus{} b$ then it's clear that $ n|(a^n \minus{} b^n)/(a \minus{} b)$
2case $ a \equiv b (\mod n)$[/quote]It seems not so clear. So I'll write my proof.

[hide]It is enough to prove that for any prime divisor $ d$ of $ n$, the greatest power of $ d$ which divides $ a \minus{} b$ must also divide $ a^n \minus{} b^n$. Assume that $ d^k$ divides $ a \minus{} b$ but $ d^{k \plus{} 1}$ does not divide $ a \minus{} b$. Hence $ a\equiv b\pmod{d^k}$, and thus $ a^n\equiv b^n\pmod{d^k}$. So $ a^n \minus{} b^n$ is divisible by $ d^k$, as desired. Q.E.D.[/hide]

edit: Don't know what I was thinking. This solution is wrong! :oops:

[quote="arcsin1.01"]

It is enough to prove that for any prime divisor $ d$ of $ n$, the greatest power of $ d$ which divides $ a \minus{} b$ must also divide $ a^n \minus{} b^n$. Assume that $ d^k$ divides $ a \minus{} b$ but $ d^{k \plus{} 1}$ does not divide $ a \minus{} b$. Hence $ a\equiv b\pmod{d^k}$, and thus $ a^n\equiv b^n\pmod{d^k}$. So $ a^n \minus{} b^n$ is divisible by $ d^k$, as desired. Q.E.D.[/quote]

I think your solution is wrong, if for every such $ d$,   $ d^k|a\minus{}b$ and $ d^k|a^n\minus{}b^n$ then it doesn't mean that $ d^k| \frac{a^n\minus{}b^n}{a\minus{}b}$ or $ n| \frac{a^n\minus{}b^n}{a\minus{}b}$


Find all functions $ f: \mathbb{R} \rightarrow \mathbb{R}$ such that for all $ x,y,z$ it holds that:

$ f(x\plus{}f(y\plus{}z))\plus{}f(f(x\plus{}y)\plus{}z)\equal{}2y.$

[quote="moldovan"]Find all functions $ f: \mathbb{R} \rightarrow \mathbb{R}$ such that for all $ x,y,z$ it holds that:

$ f(x \plus{} f(y \plus{} z)) \plus{} f(f(x \plus{} y) \plus{} z) \equal{} 2y.$[/quote]

Let $ x\equal{}z\equal{}t\minus{}f(0)$, $ y\equal{}f(0)\minus{}t$. The equation becomes $ f(t)\equal{}f(0)\minus{}t$

Plugging back in the equation, we verify that this solution fits the requirements and so $ \boxed{f(x)\equal{}a\minus{}x}$

my solution:
1. $ x\equal{}z\equal{}0$
2. $ x\equal{}z\equal{}\minus{}y$


probability
logarithms
factorial
binomial coefficients
probability and stats

Let $ (X_j)_j$ be i.i.d and $ \pm 1$ each with probability $ 1/2$.  I want to show that for all $ \alpha\in (0,1)$,
\[ \frac {1}{2n}\log P(S_{2n}\geq 2n\alpha) \to \minus{} \gamma(\alpha)
\]
where $ \gamma(\alpha) \equal{} \frac {1}{2}[(1 \plus{} \alpha)\log(1 \plus{} \alpha) \plus{} (1 \minus{} \alpha)\log(1 \minus{} \alpha)]$.

edited: fedja never misses anything :)

Why don't you just use Stirling's formula for the factorials in the binomial coefficients? Also, you are missing $ \log$ in your limit relation ;)

o.k. I got it :)

I was trying to be much too cute with the estimates when you really need to be looking at which terms are big and which are not.

This may an old post. But I have a doubt here.
Cramer's theorem says that $ \minus{} \frac{1}{2n}\log P(S_{2n}\geq 2n\alpha)\to \lambda^* \alpha \minus{}\mu(\lambda^*)$ where $ \lambda\equal{}\lambda^*$ maximises $ \mu(\lambda)\equal{}\log E\left(e^{\lambda X}\right)$

Now $ \log E\left(e^{\lambda X}\right)\equal{}\frac{1}{2}\left(e^{\lambda}\plus{}e^{\minus{}\lambda}\right)$ and I get $ \lambda^*\equal{}\tanh^{\minus{}1}(\alpha)$ maximises $ \mu(\lambda)$.
Isn't it different from what blahblahblah has?

For Cramer's theorem, you want to choose $ \lambda^*$ to minimize
\[ \lambda \alpha \minus{} \log (E (e^{\lambda X})) \equal{} \lambda \alpha \minus{} \log (\frac{e^{\lambda}\plus{}e^{\minus{}\lambda}}{2})\]
I think this does get you $ \lambda^{*}\equal{}tanh^{\minus{}1}(\alpha)$, but you can also write this as
\[ \lambda^{*}\equal{} \frac{1}{2} \log (\frac{1\plus{}\alpha}{1\minus{}\alpha})\]

Plugging this back in and doing a bit of algebraic simplification gives the same answer as in the original statement of the problem.


1. Adab + Cbb + Caa = Abda
2. Abab - Cdd = Bac
3. Abab - Ccba = Ccdc
4. Efg + Gf + Gef = Bdfg
5. Abcb - Deac = Eadd

Note that A = a, B = b and so on.

The third one:

The left shows a-c=c. 2-1=1. Let's try a=2, c=1.

we have 2b2b-11b2=11d1

the right column, b-2=1. b=3.

Second column, 2-3=d. Carry, d = 9.

2323-1132 = 1191.

These should be in the puzzles and brainteasers section.

The  1st one is 3235 + 155 + 133 = 3523.

The rest are still fairly basic. Use intelligent guessing (not just random guess-n-check), and give yourself a lot of time!  :lol:


Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]introduction for the IMO ShortList/LongList project[/url] and regarding[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]solutions[/url]  :)

Just an idea. Let $A_{1},A_{2},...,A_{n} \in F$. There is $X \in F$ which is not a subset of $\bigcup_{i=1}^{n}{A_{i}}$ (since $F$ is infinite), so $X'=X-\bigcup_{i=1}^{n}{A_{i}}$ has at most $r-1$ elements and also has noneempty intersection with all $A_{i}$. So, I've proved that for all finite subfamilies $F' \subset F$, there is a set with $r-1$ elements which meets all elements in $F'$.
Can you see a nice way to finish it from this point? I think I found one, but it's quite boring, so I won't post it now.

:) consider the union of all sets in the family, call it X. For any set B with at most r-1 elements, we can find a set in the family, A, outside B (not intersecting with B).

Now, take any set in the family, there is an element ,a1, in that set, that is contained in infinitely many sets in the family. Consider this infinite family, I1. Take a set ,A1, in the family but outside (not containing)  a1,now  there is an element a2 in A1 that is contained in infinitely many sets in the family I1, lets call it I2. Inductively, outside of  the constructed set {a1, a2, ... a(r-1)} there is a set in the family, with an element ar  that is in infinitely many sets in the family I(r-1), lets call it Ir, thus we have infinitely many sets(Ir family of sets) each contains a1...ar   we reach a contradiction, as sets in the family are all distinct...
  I think this does it.. it's a lovely problem indeed..

[quote="Raúl"]What if we put $F_1=\{r_1, r_2\}, F_2=\{r_2, r_3\}$ and $F_a=\{r_3, r_1\}$, $a\geq 3$. It contradicts the problem :o[/quote]
the problem said " let  be an infinite family of sets" .....it's a set and cannot have two similar element!!

 i think i solved it but i'm not sure..!!
let $k \in F$ so  every other element of $F$ has a subset of $k$ as it's intersection with $k$ so because the subset's of $K$ are finite so there are infinitely set of $F$ such that their interesction with $K$ is a subset of $K$ like $A_1$ and $K=A_1 \cup X_1$ ....so we can show them like $\{A_1 \cup X_1 , A_1 \cup Y_1,A_1 \cup Y_2,A_1 \cup Y_3,.... \} $and $X_1 \cap Y_i = \emptyset $ ...also $\mid A_1\mid \leq r-1 $ (because $F$ is a set and it's elements are different!)
if we repeat this steps for $Y_1,Y_2,Y_3,...$ and do this $r+1$ times ...i mean that each of $Y_2,Y_3,Y_4,... $ have intersection with a subset of $Y_1$ (maybe empty!) so infinitely of them have intersection with a subset of $Y_1$ call it $A_2$ that $ Y_1= A_2 \cup X_2$ so we show them as : $A_1 \cup A_2 \cup X_2,  A_1 \cup A_2 \cup Z_1 ,A_1 \cup A_2 \cup Z_2 ,......$ and so $X_2 \cap Z_i = \emptyset $ and $\mid A_1 \cup A_2 \mid \leq r-1$ now repeat this for$ Z_1 , Z_2,Z_3,.....$

 then we arrive to $A_1 \cup X_1 , A_1 \cup A_2 \cup X_2 , A_1 \cup A_2 \cup A_3 \cup X_3 ,..., A_1 \cup A_2 \cup....A_{r+1} \cup X_{r+1} $ and we konw that  $X_i \cap X_j =\emptyset$
$P= A_1 \cup ...A_{r+1} $ thjat because of the last step and difference between the elements of $F$ so $\mid P \mid \leq r-1$ and if $T \in F , T \cap P=\emptyset  \Rightarrow   T \cap X_i $ is nonempty and  because
1. $x_i$ are disjiont
2.$\mid P \mid \leq r-1 \Rightarrow \mid X_i \mid \geq 1 $
so $\mid T \mid \geq r+1$ this is contradiction!!

Lemma: Say all elements of an infinite family of (finite) sets $F$ intersect an infinite bunch $G$ of distinct $r$ sets (any $f$ in $F$ and any $g$ in $G$ intersect).  Then $F$ also intersects an $r-1$ set.  This lemma kills the problem because we just take $G=F$ and we are done.

We do this by induction.  First we do $r=2$.  Note that there is some element that appears infinitely many times in $G$, else we have infinitely many disjoint sets in $G$ and all elements of $F$ must intersect all of them and have infinite size, contradiction.

Say it is true for $r=k$.  Now we look at $r=k+1$.  All elements of the infinite family of $F$ intersect each of an infinite family $G$ of $k+1$ sets.  Now some element must show up infinitely many times in $G$ by the exact same argument as for the $r=2$ case.  Call this element $1$.  Say $H$ is the infinite subfamily of $G$ with $1$'s, and $I$ is the infinite family of $k$ elements formed by removing the $1$'s from the sets in $G$.  Now, every member of $F$ that lacks a $1$ must intersect every element of $I$. Hence, by induction some set of $k-1$ elements meets everything in $F$ without a $1$.  Then take the union of $1$ and this set, and we have a set of $k$ elements that meets everything in $F$.

The lemma is proved by induction, and the statement follows.

Let a number $k \le r$ be "good" if, for any $k$ things, only a finite number of the sets of $F$ contain these $k$ things. Clearly $r$ is good since the sets are distinct. Now, assume $k$ is good, and $k \ge 2$.

Then take any $k-1$ things, and assume an infinite number of sets of $F$ contain these $k-1$ things. Call these sets "good" sets, and let $X$ be the set of the $k-1$ things. Consider one of these good sets, $X \cup \{ t_1, ..., t_{r-k+1} \}$. By the goodness of $k$, only finitely many good sets contain one of the $t_i$. So take one good set without any $t_i$, say $X \cup \{t_1', ..., t_{r-k+1}'\}$. By the goodness of $k$, only finitely many good sets contain one of the $t_i$ or $t_i'$, so take one good set without any of those. Continue until I have $r+1$ good sets that only share elements in $X$. Let them be $G_1 \cap X, G_2 \cup X, ..., G_{r+1} \cup X$.

If every set intersects $X$, then the problem is proven. Otherwise, there exists a set in $F$ that doesn't intersect $X$. Then it must intersect $G_1, ..., G_{r+1}$. But all the $G$'s are coprime, so this set has cardinality $r+1$, contradiction!

Thus, $k-1$ is good. By induction, $1$ is good.

Take any set of $r$ things $a_1,...,a_r$. Finite sets contain $a_i$ for any $i$, and thus finite sets intersect $\{a_1,...,a_r\}$. But all sets of $F$ intersect $\{a_1,...,a_r\}$, contradiction!

For a set $A\in F$ and a subset $B$ of $A$, let $S(A,B)$ denote the set of sets $T\in F$ with $A\cap T=B$.

Let $|B|=1$ is a subset of $A\in F$. If $S(A,B)$ is empty, then we take all elements in $A$ except for the element in $B$ as our set of size $r-1$ and this clearly intersects all sets in $F$. Hence, we may suppose that $S(A,B)$ is nonempty for all such sets $A$ and $B$.

Now, we will prove that $S(A,B)$ is finite for all $B\subseteq A\in F$. We will strong induct on $|B|$. Clearly, the statement is true for $|B|=r$, since $S(A,B)=\{A\}$. Now, suppose that the statement is true for $|B|=k,k+1,\ldots,r$. We will now prove it for all $|B|=k-1$. Consider a set $C\in F$ such that $|A\cap C|=1$ and $B\cap C\cap A=\emptyset$. Such a $C$ exists by the previous paragraph, and let $C'$ be the subset of $C$ consisting of all elements of $C$ except the element it shares with $A$. Now, suppose that infinitely many sets in $F$ intersect $A$ at $B$. Let $T$ be the set of those sets. Now, all sets in $T$ intersect $C'$, so since there are infinitely many of them, some subset $X$ of $C'$ is the set of intersection infinitely many times. Now, take some $D$ such that $D\cap C'=X$, and note that infinitely many sets intersect $D$ at $B\cup X$. But since $|B\cup X|=|B|+|X|\geq k$, we have a contradiction by strong induction.

Since finitely many sets intersect at $A$ at each one of its subsets, there are finitely many sets in $F$, a contradiction. Hence, the only possibility is the one described in the second paragraph, and we have already found the set of size $r-1$, so we're done.

I'll prove the generalized HMMT formulation:

[quote="HMMT 2016 Team Round #9"]Fix positive integers $r>s$, and let $\mathcal F$ be an infinite family of sets, each of size $r$, no two of which share fewer than $s$ elements. Prove that there exists a set of size $r-1$ that shares at least $s$ elements with each set in $F$.[/quote]

We consider the following algorithm. Initially, let $X = \varnothing$ and $\mathcal G = \mathcal F$. Then, perform the following: [list] 	[*]If there exists $x \notin X$ which lies in infinitely 	elements of $\mathcal G$, 	then add $x$ to $X$ and remove all sets in $\mathcal G$ 	not containing $x$. 	[*]Otherwise, stop. [/list] The end result is an infinite sub-family $\mathcal G$, such that each $S \in \mathcal G$ contains every element of $X$, while $|\mathcal G| = \infty$ still.

We claim that this $X$ works. Evidently, $|X| \le r-1$.

We can take a subset $G_1$, \dots, $G_r$ of sets in $\mathcal G$ such that $G_i \cap G_j = X$ for $i \neq j$, since each element of $G_i \setminus X$ is in finitely many guys. In particular, $|X| \ge s$.

Crude picture:
[asy] 	size(6cm); 	draw( (0,0)--(3,0)--(3,1)--(0,1)--cycle ); 	label("$X$", (3,1), dir(45)); 	dot( (0.5,0.5) ); 	dot( (1.5,0.5) ); 	dot( (2.5,0.5) ); 	dot( (-0.5,1.2), blue ); 	dot( (-1.2,1.2), blue ); 	dot( (-0.5,0.6), red ); 	dot( (-1.2,0.6), red ); 	dot( (-0.5,-0.2), heavygreen ); 	dot( (-1.2,-0.2), heavygreen ); [/asy]
($G_1$ is blue plus $X$, et cetera)

Then any $S \in \mathcal F$ must meet each $G_i$ in at least $s$ places. It thus has to meet $X$ in at least $s$ places, since otherwise it would have to meet each $G_i$ in at least one element outside of $X$, but those are disjoint.

Suppose a set $X \in F$ has elements $\{1, 2, \cdots n\}$. For each other set in $F$, its intersection with $X$ is a subset of $X$. Now consider all the subsets of $X$, there is a finite number of them. There are infinitely many  sets in $F$, so there exists some set $Y \subset X$ with such that the set $S$ containing all sets in $F$ with precisely $Y$ as the intersection with $X$ is infinite.

First suppose the size of $Y$ is less than $n-1$. If all the subsets in $F$ meet $Y$, then we are done. Otherwise, take a set $Z$ in $F$ that is disjoint with $Y$. For each set in $S$, they must also intersect with $Z$ at another element not in $Y$. Let $Y_1$ be the set containing $Y$ and this element. Since $|S|$ is infinite, there exists an infinite set $S_1 \in S$ such that all the elements in $S_1$ contain $Y_1$.

Now do the same thing again to get an infinite set $S_2$ such that all sets in $S_2$ contain $Y_2$ where $|Y_2| > |Y_1|$. We can continue to do so until we get to some infinite set $S_i$ such that all sets in $S_i$ contain $Y_i$ where $|Y_i| = n-1$ (For the case when $|Y| = n-1$, we can just  jump to this step and let $Y_i = Y$).

But now there can't exist another set in $F-S_i$ which doesn't meet $Y_i$ as otherwise an infinite subset of $S_i$ must contain the same $n$ elements and so we're done.

The transfinite induction that tastymath references is rather straightforward.  In any case, there is something else very interesting about this problem.

Amusingly in my research I am reading a paper by mathematician (and IMO 1971 gold medalist) Peter Frankl ([url]https://www.renyi.hu/~pfrankl/2017-4.pdf[/url]) that asks what the right bound on $F$ is (it is known that we need $F$ to be bigger than $r^r/2^r$ and it cannot be bigger than $r^r/(1+o(1))^r$).  My solution in this thread is reminiscent of some of the lemmas in this paper (in particular the ones about $A$ and $G$).

[quote=orl]Let $r\geq2$ be a fixed positive integer, and let $F$ be an infinite family of sets, each of size $r$, no two of which are disjoint. Prove that there exists a set of size $r-1$ that meets each set in $F$.[/quote]

	We denote the family of sets by $\mathcal{F}$. Let $X:=\bigcup_{F\in\mathcal{F}}F$ be the underlying set. $X$ is infinite set, since $\mathcal{F}$ is infinite. For some $x_1\in X$ we choose a set $F_1$ of $k-1$ elements such that $\{x_1\}\cup F_1\in \mathcal{F}$. Then we choose $x_2\in X, x_2\notin \{x_1\}\cup F_1$ and a set $F_2$ with $\{x_2\}\cup F_2\in \mathcal{F}$.

	Proceeding this way, we obtain (disjoint) sets $ U_i:=\{x_i\}, i\geq 1$, and sets of $r-1$ elements $F_i, i\geq 1$ such that $U_i\cup F_i \in \mathcal{F}, i=1,2,\dots$ and $\left(\bigcup_{i} U_i\right) \bigcap \left(\bigcup_i F_i\right)=\emptyset$.
	Consider $X':=\bigcup_i F_i$. If $X'$ is infinite we run the same process again and obtain mutually disjoint sets (we use the same notations again) $U_i,i\geq 1$, each one consisting of two elements and sets $F_i,i\ge 1$, each one of $r-2$ elements, such that $U_i\cup F_i\in\mathcal{F}$ and $\left(\bigcup_{i} U_i\right) \bigcap \left(\bigcup_i F_i\right)=\emptyset$.

	In case $X':=\bigcup_i F_i$ is infinite, we proceed with this process further until we come to a moment we have disjoint sets $U_i,i\in\mathbb{N}$ each with $k,k<n$ elements and sets $F_i$, each with $r-k$ elements, such that $U_i\cup F_i\in \mathcal{F}$ and $\left(\bigcup_{i} U_i\right) \bigcap \left(\bigcup_i F_i\right)=\emptyset$ [b]and [/b]$ X':=\bigcup_{i}F_i$ [b]is finite[/b]. (Such moment certainly will come, since otherwise we finally get $F_i=\emptyset$ and disjoint set of $U_i$ of $r$ elements, $U_i\in\mathcal{F}$, which contradicts that any two sets in $\mathcal{F}$ meet.)

	Now, $X'$ being finite means there exist finitely many subsets of $X'$ with $r-k$ elements, implying infinitely many sets among $F_i,i\geq 1$ coincide with some $F_0\subset X', |F_0|=r-k$.
	We claim [b]the elements in[/b] $F_0$ [b]satisfy the requirement[/b]. Indeed, suppose there exists $F\in\mathcal{F}, F\cap F_0=\emptyset$. But $U_i\cup F_0\in \mathcal{F}$ for infinitely many $i$, and since $U_i$ are disjoint, some $U_i$ does not meet $F$, thus $U_i\cup F_0$ does not meet $F$, contradiction.

	[b]Remark[/b]. The fact exploited is that the family $\mathcal{F}$ is too large. There is no need $\mathcal{F}$ to be infinite. One can go through and estimate how large should be $|\mathcal{F}|$, if finite, in order to apply the same arguments.

[quote=tastymath75025]Here is a solution with [b]StoryScene[/b] that only works when $F$ is countable. [b]yugrey[/b] says this should be generalizable to all $F$ with transfinite induction, but I'm not knowledgeable enough on the subject to verify this.

Let $F=\{S_1,S_2,\dots\}$. For any $t$ and any $1\le i\le r$ let $X_i(t)$ be the set of all sets of size $i$ which meet each of $S_1,S_2,\dots, S_t$. Note that $X_r(t)$ is always infinite, since every element of $F$ lies in it. Let $f(t)$ be the smallest $i$ so that $X_i(t)\neq \emptyset$. Since $X_i (t+1)\subseteq X_i(t)$ for all $t$, it's clear that $f(t)$ is nondecreasing, but $f(t)$ only takes values in $\{1,2,\dots, r\}$, so it eventually becomes some constant $k$.

Now I claim that if $f(t)=k$, then $|X_k(t)|$ must be finite. Suppose otherwise, so $X_k(t)$ is infinite. Then there exists some $S\in X_k(t)$ so that $S$ isn't in $S_1\cup S_2\cup \dots \cup S_t$, so $S$ contains some element $e$ not in any of the $S_i$ for $1\le i\le t$. Now consider $S' = S\backslash e$, which has size $k-1$ and meets $S_1,S_2,\dots, S_t$. This implies $X_{k-1}(t)\neq \emptyset$, contradiction.

Now since $|X_k(t)|$ is finite but nonzero for all large $t$ and $X_k(t+1)\subseteq X_k(t)$, it follows $X_k(t)$ eventually becomes constant for $t\ge T$. Now take any $S\in X_k(T)$; it follows that $S$ meets all sets in $F$, and since $X_r(t)$ is infinite, we have $k\le r-1$, so $|S|\le r-1$ as desired.[/quote]
Nice! No need for transfinite induction in case the family is uncountable. But, if you use it, it usually is made by indexing the sets in $F$ with ordinals, like $\{S_{\alpha}:\alpha <\beta\}$, where $\beta$ is some ordinal. In case $\beta$ is countable, one can arrange $S_{\alpha},\alpha <\beta$ in a sequence and apply the same argument. But, if $\beta$ is uncountable, for example the first uncountable ordinal $\omega_1$ (when you take the limit, and $\omega_1+1$,....etc.), one should use some other argument like the one used below. Not that it is of any difficulty, but it makes the induction pointless.

Suppose $\mathcal{F}$ is uncountable family satisfying the condition. As you proved, for any countable subfamily $F\subset \mathcal{F}, F=\{S_1,S_2,\dots\}$, there exists a finite collection $X_k(T),k\leq r-1$ of sets with $k$ elements (eventually depending on $F$ ), as described in post N12. We simply denote $X_k(T)$ as $X_k$ or rather $X_k(F)$ (to mark it may depend on $F$).
Let $\ell$ me the maximal possible $k$ in $X_k(F)$ when $F$ varies. Note that for any two countable subfamilies $F_1,F_2\subset \mathcal{F}$ with $X_{\ell}(F_1)$ and $X_{\ell}(F_2)$, $X_{\ell}(F_1)\cap X_{\ell}(F_2)\neq \emptyset$. Indeed, $F_1\cup F_2$ is also countable, and arranging those sets in a row it easily follows $X_{\ell}(F_1\cup F_2)=X_{\ell}(F_1)\cap X_{\ell}(F_2)$.

So, we take minimal $X_{\ell}(F)$ when $F$ varies (but providing in $X_k(F)$ we have $k=\ell$). Denote it with $X(F_0)$. I claim, all sets in $X(F_0)$ (which consist of exactly $\ell<r$ elements) do the job. Indeed let $S_0\in X(F_0)$. Take any set $S\in\mathcal{F}$. We may consider $F:=\{S\}\cup F_0$. Since $X_\ell(F)\subset X_{\ell}(F_0)$ and $X_{\ell}(F_0)$ is the minimal one, we get $X_\ell(F)=X_\ell(F_0)$ or $S\cap S_0\neq \emptyset$. $\blacksquare$

[b]Remark[/b]. The idea in post #12 may be applied in slightly different way, working only with f[b]inite sets[/b]. For any collection $F$ of finite sets $S_1,S_2,\dots,S_n$, let $X(F)$ denotes the collection of all sets of size at most $r-1$ that meet any set in $F$, and there aren't two sets in $X(F)$ one is the subset of the other. In the same way, as you proved it in #12, there exist finite collection $F$ with $X(F)$ of finite size. So, you take a minimal $X(F)$, under inclusion, and further apply the same method as above.

See  https://arxiv.org/abs/2010.02541 for new bounds on this problem.

Suppose on the contrary that such set does not exist.

[b][color=#00f]Claim.[/color][/b] For each $1\leq n\leq r-1$ there exists some $\{a_1,...,a_n\}$ which is contained in an infinite number of sets in $F$.
[u]Proof. [/u]Induct on $n$. For $n=1$, suppose $S_0\in F$. Then every $S$ in $F$ intersect $S_0$, hence by pigeonhole principle, there exists infinitely many sets intersecting the same element in $S_0$, so we are done.

Now for the general case $n$ we can find some $\{a_1,...,a_{n-1}\}$ contained in an infinite number of sets $S_1,S_2,...$ in $F$. If this set intersects every other set in $F$ then we are done. Otherwise consider a set $S_0$ not intersecting it. Then each of the $S_1,S_2,...$ intersect $S_0$. By pigeonhole principle an infinite number of them intersect at the same element $a_n$, hence taking $\{a_1,...,a_n\}$ we are done. $\blacksquare$

Now we can take $T=\{a_1,...,a_{r-1}\}$ satisfying the condition in the Claim, being contained in sets $S_1=T\cap \{b_1\},S_2=T\cap\{b_2\} ,...$, where the $b's$ are all distinct. Suppose on the contrary that some set $S_0$ in $F$ do not intersect $\{a_1,...,a_{r-1}\}$. Then it must contain all $b_1,b_2,...$, contradiction.

FTSOC, assume problem statement is false.

Let $S$ be the set of largest size which is a subset of infinitely many elements of $F$. If there are many such $S$, then pick any of them. Now, we claim $|S|=r-1$.
Proof: Assume not, clearly $|S|<r$. Now, we can find $f\in F$ such that $f\cap S=\Phi$(else, problem statement follows). Thus, there must be some element $t\in f$, such that $t$ is in infinitely many of the sets that contain $S$. Thus, $S\cup \{t\}$ would be a larger set satisfying problem conditions.

Thus, we have found an $r-1$ set which is a subset of infinitely many sets in $F$. But, observe that we should still be able to apply the above algorithm if problem statement is false. But, we cannot have $|S|=r$. Thus, we are done.

Clearly, there must exist at least one element $x$ that appears in infinitely many sets $F$. Otherwise, consider any $S\in F$. For each $x\in S$, finitely many sets $T\in F$ have the property that $x\in T$. However, this means that only finitely many sets $T\in F$ can meet $S$, so infinitely many sets are disjoint from it, contradiction.

Now, let $U$ be the maximal set, selected from a greedy algorithm, such that $U$ is a subset of infinitely many $S\in F$. Clearly, $|U|\le r-1$. Let $F_0$ be the maximal subfamily of $F$ such that $U\subset S$ for all $S\in F_0$. Since $U$ is maximal, for any $V_1,V_2,\dots, V_n\in F_0$, there is infinitely many $W\in F_0$ such that $V_i$ and $W$ only intersect at $U$ for all $i$. Otherwise, there is infinitely many $W\in F_0$ such that $V_i\setminus U$ and $W\setminus U$ aren't disjoint for some $I$. Since the union of $V_i$ is finite, though, there must exist a particular element that appears in infinitely many $W\in F_0$, contradiction.

Thus, let $V_1,V_2,\dots,V_{r+1}$ all be mutually disjoint except at $U$. For all $S\in F$, $S$ and $V_i$ are not disjoint for all $i$. If $S$ is disjoint from $U$, then it must reach one element from each $V_i\setminus U$, but that's $r+1$ distinct elements, absurd.


Show that a number is divisible by 3 if the sum of its digits is divisible by 3.

[hide]
$N=A_1A_2A_3A_4 \cdots A_n$ is the number, or
\[N=10^{n-1} \cdot A_1 + 10^{n-2} \cdot A_2 + \cdots + 10 \cdot A_{n-1} + A_n\]

If $N$ is divisible by 3, then
\begin{eqnarray*}
10^{n-1} \cdot A_1 + 10^{n-2} \cdot A_2 + \cdots + 10 \cdot A_{n-1} + A_n & \equiv & 0 \mod {3}\\
\end{eqnarray*}
Because $10^x \equiv 1 \mod {3}$, we have
\begin{eqnarray*}
A_1 + A_2 + \cdots + A_{n-1} + A_n & \equiv & 0 \mod {3}\\
\end{eqnarray*}
[/hide]

Just a few examples :):
[hide]Ex.
a)
123
Sum of digits=6
6 is divisible by 3
123/3= 41
Thus its divisible by 3

b)
548790312
Sum of digits=39
39 is divisible by 3
548790312/3= 182,930,104[/hide]

The solution posted by Chess64 is correct.


[quote="Beat"]Find all triples of positive integers $(p, q, n)$ with $p$ and $q$ prime, such that $p(p+1)+q(q+1) = n(n+1)$.[/quote]
I have a solution:assuming $p\geq q$
$p(p+1)=(n-q)(n+q+1)$
then $p|n+q+1$
$n-q|p+1$
thus $n\leq p+q+1$
thus $p|n+q+1\leq p+q+1+q+1\leq 3p+2$
so $n+q+1=1p,or,2p,or 3p$
first case
$n+q+1=1p$then $n=p+q+1$
and we know$q(q+1)=(n-p)(n+p+1)$so $n+q+1=p$
so p=q,a contraduction.
second:
$n+q+1=2p$
so $n=2p-q+1$
so $3(p-1)=4q$then $q=3$
$p=5$
$n=6$
I left the third case to the reader.
so the solution is (5,3,6),(3,5,6),(2,2,2)

Equation can be written in the general ideal:

$X(X+a)+Y(Y+a)=Z(Z+a)$

Reshniya can be written:

$X=ps$

$Y=\frac{(p^2-1)s+(p-1)a}{2}$

$Z=\frac{(p^2+1)s+(p-1)a}{2}$

$p,s$ - integers corresponding parity.

If we use the solutions of Pell's equation: $p^2-2s^2=1$
Solutions can be written:

$X=2(s+p)sL+as(2s+p)$

$Y=(2s+p)pL+as(2s+p)$

$Z=(2s^2+2ps+p^2)L+2as(s+p)$

And more.

$X=2s(s-p)L+ap(s-p)$

$Y=(p-2s)pL+ap(s-p)$

$Z=(2s^2-2ps+p^2)L+ap(2s-p)$

$L$ - Any integer.


Find $ x\in R$ of this equation:

$ \boxed {2\left (5x \plus{} 3\sqrt {x^2 \plus{} x \minus{} 2} \right ) \equal{} 27 \plus{} 3\sqrt {x \minus{} 1} \plus{} \sqrt {x \plus{} 2}}$

$ x\equal{}2$ makes both sides $ \equal{}32$. So one solution is $ x\equal{}2$. I can't spot any others.

Squaring and squaring again might take some time.

Notice that $ A^2 \equal{} (3\sqrt{x\minus{}1} \plus{} \sqrt{x\plus{}2})^2 \equal{} 9(x\minus{}1) \plus{} 6\sqrt{(x\minus{}1)(x\plus{}2)} \plus{} (x\plus{}2) \equal{}$ $ 2(5x \plus{} 3\sqrt{x^2 \plus{} x \minus{} 2}) \minus{} 7$. Then $ A^2 \plus{} 7 \equal{} 27 \plus{} A$, so $ A \equal{} 5$ ($ A\equal{}\minus{}4$ is discarded, since $ A$ is a sum of square roots, hence non-negative).

Now it's easy. $ 2(5x \plus{} 3\sqrt{x^2 \plus{} x \minus{} 2}) \minus{} 7 \equal{} 25$ leads to $ 16x^2 \minus{} 169x \plus{} 274$, with roots $ x\equal{}2$ and $ x \equal{} \frac {137} {16}$, but the latter is parasitic (coming from  $ 2(5x \minus{} 3\sqrt{x^2 \plus{} x \minus{} 2}) \minus{} 7 \equal{} 25$).


induction
number theory unsolved
number theory

I don't remember where I saw this problem..

Let $p$ a prime number: $p = 4k+3$ for some $k \in N$. Let $a \in Z$.
Solve:
$3a^2 + 1 = p^2$

My proof is not yet complete so please help me..  :roll:

[quote="Rust"]Solution in natural x^2-3a^2=1
is x(n)=[(2+sqrt(3))^n+(2-sqrt(3))^n]/2, a(n)=[(2+sqrt(3))^n-(2-sqrt(3))^n]/(2sqr(3)), n=1,2,3,...
x(2k+1) is even, x(4k)=1(mod 4), only x(4k+2)=3(mod4).
If prime p(n) is divisor x(n) and Lejander simvol (3/p(n))=1, then p(n) is divisor x(kn) for any odd k.
This is help found primes x(4k+2). One of them x(2)=7.[/quote]

I post it in Tex:

Solution in natural $x^2 - 3a^2 = 1$ is:
$x(n)= \frac{1}{2} \cdot [ (2 + \sqrt{3})^n + (2 - \sqrt{3})^n ]$,
$a(n) = \frac{(2+ \sqrt{3})^n - (2 - \sqrt{3})^n}{2 \sqrt{3} }$, with n =1,2,3,...
$x(2k+1)$ is Even. $x(4k) \equiv 1 (mod 4)$ only if $x(4k+2) \equiv 3 (mod 4)$.
If $p(n) | x(n)$  and "Lejander simvol" (??) $\frac{3}{p(n)} = 1$, then $p(n) | x(kn)$ for any odd k.
This is help found primes $x(4k+2)$. One of them $x(2)=7$.

What do you mean by $x(n)$? In any case $x(n)= \frac{1}{2} \cdot [ (2 + \sqrt{3})^n + (2 - \sqrt{3})^n ]$ is to be proved.

[quote="mathmanman"][quote="Gauss_87"]
 and "Lejander simvol" (??) [/quote]

http://mathworld.wolfram.com/LegendreSymbol.html ;)[/quote]

You can type it like this: \left(\frac{a}{b}\right), giving $\left(\frac{a}{b}\right)$

[quote]
Solution in natural $x^2 - 3a^2 = 1$ is:
$x(n)= \frac{1}{2} \cdot [ (2 + \sqrt{3})^n + (2 - \sqrt{3})^n ]$,
$a(n) = \frac{(2+ \sqrt{3})^n - (2 - \sqrt{3})^n}{2 \sqrt{3} }$, with n =1,2,3,...
$x(2k+1)$ is Even. $x(4k) \equiv 1 (mod 4)$ only if $x(4k+2) \equiv 3 (mod 4)$.
If $p(n) | x(n)$  and "Lejander simvol" (??) $\frac{3}{p(n)} = 1$, then $p(n) | x(kn)$ for any odd k.
This is help found primes $x(4k+2)$. One of them $x(2)=7$.

What do you mean by $x(n)$?[/quote]

Can someone explain ??

[quote="Rust"]All solution x^2-3a^2=1 in natural can be expessed x=x(n),a=a(n), n=1,2,3,...
Sequence x(n) can be expressed x(0)=1,x(1)=2, x(n+1)=4x(n)-x(n-1) (4=2+sqrt(3)+2-sqrt(3),-1=-(2+sqrt(3))(2-sqrt(3)).
x(n)*x(m)=[x(n+m)+x(n-m)]/2, or x(n+m)=2*x(n)*x(m)-x(n-m). Let m=2, we have x(2k+1) is even for all k. If x(2k)=1 (mod 4) for 2|k and x(2k)=3(mod 4) for odd k. We interesting when x(n)=3(mod 4). Therefore n=4k+2. x(2)=7,x(4)=97. x(6)=14*97-7=7*193. Let m=4. We have x(n+4)=194x(n)-x(n-4), and 7|x(2), 7|x(6). By induction 7|x(4k+2) forr all k.[/quote]

How do you state: the sequence is $x(0)=1, x(1)=2, x(n+1) = 4x(n) - x(n-1)$ ???

[quote="Gauss_87"]I don't remember where I saw this problem..[/quote]
You could have seen it three days before: http://www.mathlinks.ro/Forum/viewtopic.php?t=74255


Sorry,I misunstand the meaning.
And I mean if the left side is what I wrote then the inequality will be true always.

[quote="conceive"][quote="zhaobin"]And I mean if the left side is what I wrote then the inequality will be true always.[/quote]

$x^{2}_{1}+\cdots+x^{2}_{n-1}+(n-1)x^{2}_{n}\ge x_{n}(x_{1}+x_{2}+\ldots+x_{n-1})$

Do u mean this is right? Using AM-GM we even have that

$a^{2}+b^{2}\ge2ab$, so $LHS\ge2x_{n}(x_{1}+x_{2}+\ldots+x_{n-1})$

and this is twice stronger than your ineq..

Note that this is not related to the Vietnam ineq..[/quote]
Maybe $x^{2}_{1}+\cdots+x^{2}_{n-1}+\frac{n-1}{4}x^{2}_{n}\ge x_{n}(x_{1}+x_{2}+\ldots+x_{n-1})$
is the proper .


Prove that any four points not on a circle can be inverted into a group of orthocentric points.

an orthocentric group of points is a triangle and its orthocenter.

A, B, C, D are 4 arbitrary non-concyclic points. Let $ \mathcal S_0$ be some similarity, not specified yet, taking (A, B, C, D) into $ (A_0,B_0,C_0,D_0),$ also non-concyclic. Inversion $\mathcal  I_{D0}$ centered at $ D_0$ takes $ (A_0,B_0,C_0)$ into $ (A_1, B_1,C_1)$ and the inversion center $ D_0$ to infinity. Since $ (A_0,B_0,C_0,D_0)$ are non-concyclic, $ (A_1,B_1,C_1)$ are non-collinear. Inversion $ \mathcal I_{I1}$ centered at the incenter $ I_1$ of the $ \triangle A_1B_1C_1$ takes $ (A_1, B_1, C_1)$ into $ (A_2, B_2, C_2)$ and the point at infinity ($ D_1$) into the inversion center $ I_1,$ identical with the orthocenter of the $ \triangle A_2B_2C_2,$ making $ (A_2,B_2,C_2,D_2 \equiv I_1)$ orthocentric.  $ \mathcal M \equal{} \mathcal I_{I1} \circ \mathcal I_{D0}$ is a Moebius transformation, which can be decomposed into a similarity $ \mathcal S_1,$ inversion $ \mathcal I,$ and another similarity $ \mathcal S_2,$ $ \mathcal M \equal{} \mathcal S_2 \circ \mathcal I \circ \mathcal S_1,$ hence $ \mathcal I \equal{} \mathcal S_2^{ \minus{} 1} \circ \mathcal M \circ \mathcal S_1^{ \minus{} 1}.$ If we choose the original similarity $ \mathcal S_0 \equal{} \mathcal S_1^{ \minus{} 1},$ then $ \mathcal I \equal{} \mathcal S_2^{ \minus{} 1} \circ \mathcal M \circ \mathcal S_0$ and

$ \mathcal I(A,B,C,D) \equal{} \mathcal S_2^{ \minus{} 1} \circ \mathcal M (A_0,B_0,C_0,D_0) \equal{} \mathcal S_2^{ \minus{} 1}(A_2, B_2,C_2,D_2) \equal{}$
$ \equal{} (A_3,B_3,C_3,D_3) \sim (A_2,B_2,C_2,D_2),$

where $ (A_2, B_2, C_2, D_2)$ are orthocentric, hence the similar points $ (A_3,B_3,C_3,D_3)$ are also orthocentric.


AMC
AIME
blogs
Putnam
conics
ellipse
Pythagorean Theorem

So, what does everyone think the best AIME problem is? On my blog I said it was 1997 #14, but everyone else disagreed :P Well, actually now I've changed it to 1991 #15.

For your reference:

http://www.kalva.demon.co.uk/aime.html

http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45

(BTW, by "best" I mean either it has a very elegant solution or is well-written...)

It was the 83, and it was either 12, 13, or 14. It was a cool problem.

[quote="sirorange"]2006 AIME I. Problem 1.

It was sooooo pretty. Who would have ever thought of using the Pythagorean Theorem in that problem?[/quote]

damnnnn son; using pythagorean theorem is so much more elegant than my method;

i think tho, aops's solution to 2006 #15 is quite genius, squaring to get rid of absolute values, i wouldn't have thought of it, heh

[quote="Iversonfan2005"]oh I can't remember the problem itself, but it was really cool

It was like there are two chords in a circle with lengths of opposite digits..

If anyone knows which one i'm talking about it, can someone post the year?

I can't seem to find it, it's like a number 13 from the 80s or 90s[/quote]

Hmmm... '95?

For my own reasons I liked 1987 #14.  I'm not sure if I'd call it the best (and comparably it seems significantly easier than the ones mentioned above) but I did like it.

[quote="krustyteklown"]
i think tho, aops's solution to 2006 #15 is quite genius, squaring to get rid of absolute values, i wouldn't have thought of it, heh[/quote]

Yea, the method was amazingly simple, too bad it really trivialized the problem (considering it's supposed to be a #15).

[quote="tongos"]in my opinion, the number 8 problem on last years aime1 test, with the logs, was the best problem.[/quote]

i didn't think it was very original though :P

the majority of aime problems are not that good then, if you want nice problems, that are original and motivating, look at some putnam problems.

I always like problems that I've gotten right, and are supossed to be hard.  Like number 12 on the 2005 AIME I, or 15 on the 1992 AIME.

[quote="amirhtlusa"]2005 AIME II, problem 15 :)[/quote]

yes, i got a rush when i saw the ellipse too

finding the tangent also correlates to AMC 12 2004 #21

Great problem, it appeared in ACOPS too. Even after reading to solution, it took a while for me to get a hang of reflection.

[quote="mysmartmouth"]2007 #3... oh never mind.  I forgot you people don't know the test questions ahead of time...[/quote]

um...i do, why?  :?

I don't know about other years, but I liked 15 and 10, I think (the one with the 8 circles) off this years test.  I solved them both during the test, but didn't actually get either right, becuase of mistakes


Does anyone know if LaTeX has a way to do the symbol for "such that"?  Thanks!

I just use | myself.  Occasionally I use : to spice it up a little :P

Thanks, t0rajir0u and Xevarion.  I'll just stick with $\mid$ and :. :-)

But, Xevarion, you mean "some positive $\delta$ greater than zero [b]such that[/b]," yes?

Best -- Catherine

[quote="Xevarion"]I use $|$ when I'm defining a set, such as $\{x | x^{2}-3 > 0\}$. (read: "the set of all $x$ [b]such that[/b] $x^{2}-3$ is positive")
Otherwise I usually do a colon, like in

$\forall x \in \mathbb{R}, \forall \epsilon > 0\, \exists \delta > 0 : |x-y|<\delta \Rightarrow |f(x)-f(y)| < \epsilon$

(read: "for all real $x$ and all positive $\epsilon$, there exists some positive $\delta$ [b]such that[/b] $|x-y|$ less than $\delta$ implies $|f(x)-f(y)|$ less than $\epsilon$")[/quote]

[quote="Xevarion"][quote="CatherineAsaro"]But, Xevarion, you mean "some positive $\delta$ greater than zero [b]such that[/b]," yes?[/quote]
Certainly, but I think saying both "positive" and "greater than zero" is a little redundant. ;)[/quote]

Hah!  Yes, I see your point.  I missed the word positive before, so I wanted to make sure I had the right symbol as such that.

[quote="Kent Merryfield"]There is \backepsilon . Some people use it as a logical "such that."

$\forall\,\epsilon>0\ \exists\,\delta>0\backepsilon\, |x-y|<\delta\implies|f(x)-f(y)|<\epsilon.$[/quote]

That's was the one I was looking for.

I've noticed, though, that people don't seem to use that one so much anymore.

[quote="leibniz"]And people use also \varepsilon for epsilon. \[\forall x \in \mathbb{R}, \forall \varepsilon > 0\, \exists \delta > 0 : |x-y|<\delta \Rightarrow |f(x)-f(y)| < \varepsilon\] [/quote]
The backward epsilon that looks like this $\ \ \backepsilon$: I did try that for "such that," but it looked too much like, well, a backward epsilon.  :-)

I'm remembering a symbol something like $\exists$ for such that, except it wasn't as squared off as the "exists."  I could have sworn, though, that it was larger than the $\ \ \backepsilon$.

When I was writing my doctorate, I had all these symbols memorized.  It's amazing how much you can forget in twenty-five years.

I probably should quit being lazy and just write the words.

But, Leibniz!  How does your penguin know so much about my machine? :-)


a,b,c,d £ IN  and a,b,c,d >= 2

prove that:

http://www.monsterup.com/image.php?url=upload/1238886985376.gif

[quote="thepunisher123"]Given $ a,b,c,d \ge 2$

prove that:$ \sqrt{(1\minus{}\frac{1}{a^2})(1\minus{}\frac{1}{b^2})(1\minus{}\frac{1}{c^2})(1\minus{}\frac{1}{d^2})} \ge \frac{\sqrt{2}}{2}$[/quote]
It 'swrong.Try $ a\equal{}b\equal{}c\equal{}d\equal{}2$ :maybe:

the right problem is,
let $ a,b,c,d \geq 2$ be a different integer numbers, prove that,
$ \sqrt{\left(1\minus{}\frac{1}{a^2}\right)\left(1\minus{}\frac{1}{b^2}\right)\left(1\minus{}\frac{1}{c^2}\right)\left(1\minus{}\frac{1}{d^2}\right)}\geq \sqrt{\frac{3}{5}}$
it's very easy!

Wlog $ a\ge b\ge c\ge d$. Then $ d\ge 2$, $ c\ge 3$, $ b\ge 4$, $ a\ge 5$. Also

$ 1\minus{}\frac{1}{d^2}\ge 1\minus{}\frac{1}{2^2}$ a.s.o. Then multiply them...


A number, N, divides each of 17 and 30 with the same remainder in each case. What is the largest value N can have?

P.S. No algebra or guessing allowed

[hide]N is congruent to x mod 17 and is congruent to x mod 30, so just throw out numbers that have a remainder greater than 17 when divided by 30 and go from there. You find that the largest possible number is 16.[/hide]

Don't think that works. Doesn't the problem say 17 and 30 divided by n has the same remainder? 17 divided by 16 is 1 r 1, while 30 divided by 16 is one remainder 14.

when u divide 17 by 13 u get a remainder of 4

and u also get a remainder of 4 when you divide 30 by 13.

 :D

And you get that since the difference of 17 and 30 is 13.

[quote="vicseb"]No algebra or guessing allowed[/quote]An interesting requirement... :)

$17\equiv30\mod{N}$
$kN+17=jN+30$
$(k-j)N=13$
$N$ can therefore be either $1$ or $13$ (since $13$ is prime); we want the largest value, so our answer is $13$.


Okay-here we go;

Box-and-Whisker Plots. I know how to find the quartiles and all; but how exactly am I supposed to set it up? And after setting it up; how would I be able to read it?

Any help is welcome.....

~Mathmadon

First I would puta line with a good scale along the bottom covering the range of your values. Then mark lines where the median and quartiles are and join them up to form the 'boxes'. Finally find the highest and lowest values in your data range, and mark them on. Join them up to your boxes with straight lines.
By looking at the box(es), you will be able to tell where your data is centred, and how densely it is packed in the middle. It should also be clear how symetrical the data is, as to whether the lines an dboxes are roughly symetrical. The lengths of the two lines show how much the extreme values differ from those near the median.

Attached is a document containing a picture of several box-and-whisker plots

wow! All that thinking actually hurt me!  :stretcher:

But it's all good now. :D  :coolspeak:

Anyhow-I wanna thank you guys for the help. I finally understand it now! (Wow! Ain't that a miracle!)

Anyways;
Thanks again... and that document wouldn't work on my computer- But I'm sure it will on one of the other three (not counting laptops that'll surely support it).

~Mathmadon


How do you problems like this:
A class has 4 students and we break everyone into 2 groups of 2 members each
How many different combinations of the 2 groups are possible?
If i list they are AB CD: AC BD: AD BC so 3 but how do you get that

ANd for a harder problem like this, you cant list themm all..
A class has 27 students and we break everyone into 9 groups of 3 members each
How many different combinations of the 9 groups are possible?

[hide="probably wrong :-("]
So, you can chose $\dbinom 4 2$ for the first group, and the second one is then obvious for the first one, so $\dbinom 4 2=6$, but you divide by two because then AB and BA would be counted twice so itd be 3 so you probably just apply that to the second[/hide]

Alright, I understand that. so for the 27 would that be
27C3*24C3*21C3*18C3*15C3*12C3*9C3*6C3*3C3 and that divided by 2^9?

Wait if you divide 4C2 by 2, for AB being switched what aoubt CD being switched?

you already considered that part by doing 4C2 instead of 4P2

Now, Im really confused.. so its 4C2*2C2 divided by 2?  I think I know why you divide by 2 is it because  AB CD and CD AB are the same, and it hsa nothing to do with AB and BA, so what would the answer to number two be?

Ya I think thats what you do.. because AB and CD can be switched.. so you divide by 2!, if its like AB CD EF, you divide by 3! but Im not really sure

I think for the 27 kids in groups of 3 problem, you divide by 9!.  You don't need to worry about the order of kids within the group.  As indianamath says, using the combination formula instead of the permutation formula accounts for that.  But there are 9 groups selected, and you could have selected those 9 groups in any of 9! orders, and since you also don't care which order you select the groups in, you divide by 9!.  So, I think the answer is:

$\frac{\dbinom{27}{3}\dbinom{24}{3}...\dbinom{3}{3}}{9!}$

mathmom is correct.  Every set of 9 groups can be rearranged in $9!$ different ways.  So, if you make the groups in this manner, you will be "double-counting" by a factor of $9!$.

If that's confusing, here's another way to make the groups:

Number each student from 1 to 27.  Pick the lowest-numbered student.  [There's exactly 1 way to do that.]  Pick 2 of the remaining 26 students to be in his group.  [There's ${26 \choose 2}$ ways to do this.]  Repeat, by picking the lowest-numbered student remaining.  [There's exactly 1 way to do that.]  Then pick 2 of the remaining 23 students to be in her group.  [There's ${23 \choose 2}$ ways to do this.  Repeat until all groups have been formed.  You have created the groups in a specific order, so there is no double-counting.  The number of ways we did this is:

$1{26\choose 2}\cdot 1{23\choose 2}\cdot 1{20\choose 2}\cdot \cdots \cdot 1{5 \choose 2}\cdot 1{2 \choose 2}$

Numerically, the result is identical to mathmom's solution.

Next time, try something in the middle of complexity between "2 groups of 2" (3 ways) and "9 groups of 3" $(2\thinspace 977\thinspace 546\thinspace 171\thinspace 600\thinspace 000 \text{ ways})$.  [That was a [b]huge[/b] jump in complexity.]  Maybe try "2 groups of 3" (10 ways) or "3 groups of 2" (15 ways).  Understand why the formulas and patterns you are discovering work on numbers you can count and comprehend, before jumping to gargantuan problems that are too big, even for your calculator.

[quote="rcv"]

$1{26\choose 2}\cdot 1{23\choose 2}\cdot 1{20\choose 2}\cdot \cdots \cdot 1{5 \choose 2}\cdot 1{2 \choose 2}$

Numerically, the result is identical to mathmom's solution.[/quote]

Want to convince me?  I mean logically it makes sense that your method would count the same thing as mine, but I'm having a hard time seeing why your resulting expression comes out to the same thing as mine.  Is there a way to see that, beyond trusting the logic?

Thanks!

[quote="mathmom"][quote="rcv"]

$1{26\choose 2}\cdot 1{23\choose 2}\cdot 1{20\choose 2}\cdot \cdots \cdot 1{5 \choose 2}\cdot 1{2 \choose 2}$

Numerically, the result is identical to mathmom's solution.[/quote]
Want to convince me?[/quote]
[quote="mathmom"]$\frac{\dbinom{27}{3}\dbinom{24}{3}...\dbinom{3}{3}}{9!}$[/quote] $=\frac{\dbinom{27}{3}}{9}\frac{\dbinom{24}{3}}{8}\cdots\frac{\dbinom{3}{3}}{1}$

One of the marvelous things I love about probability and combinatorics is that many diverse methods almost "magically" yield the same, correct answer.  In this particular case, your terms and my terms match up nicely, even without resorting to any "magic":

$\frac{\dbinom{27}{3}}{9}= \frac{27\times 26\times 25}{3\times 2\times 1\times 9}= \frac{26\times 25}{2\times 1}=\dbinom{26}{2}$

$\frac{\dbinom{24}{3}}{8}= \frac{24\times 23\times 22}{3\times 2\times 1\times 8}= \frac{23\times 22}{2\times 1}=\dbinom{23}{2}$

$\cdots$

[quote="rcv"]
$\frac{\dbinom{27}{3}}{9}= \frac{27\times 26\times 25}{3\times 2\times 1\times 9}= \frac{26\times 25}{2\times 1}=\dbinom{26}{2}$[/quote]

Wow, thanks, that's very cool!

I guess there's a lemma there:

$\frac{\dbinom{mn}{n}}{m}=\dbinom{mn-1}{n-1}$

which will always work becasue the $m$ and $n$ on the bottom of the expansion will cancel out the $mn$ in the expansion on the top.


inequalities
logarithms
inequalities unsolved

See the file attached to the post...

sorry for the inconvenience!!! :(

hello, do you mean $ 8\cdot27^{\log_6 x} \plus{} 27\cdot8^{\log_6 x} \minus{} x^3$?
Sonnhard.

yes!! :lol:

we have to find the max. value where x varies over positive integers...

Has someone tried this .. :?:
This is from Purple Comet Math Meet

Maximize $ 8\cdot27^{\log_{6}x}\plus{}27\cdot8^{\log_{6}x}\minus{}x^{3}\equal{}y$

Solution:

Let $ log_6 x\equal{}k$, then $ y\equal{}8 \cdot 27^k\plus{}27 \cdot 8^k\minus{}(8 \cdot 27)^k\equal{}216(27^{k\minus{}1}\plus{}8^{k\minus{}1}\minus{}27^{k\minus{}1} 8^{k\minus{}1})$

So $ 1\minus{}\frac{y}{216}\equal{}(27^{k\minus{}1}\minus{}1)(8^{k\minus{}1}\minus{}1)\equal{}z$

the question now becomes to minimize $ z$.

Clearly for $ k>1$ or $ k<1$ , $ z>0$

And for $ k\equal{}1$, $ z\equal{}0$.

So max. value of $ y$ attains when $ z\equal{}0$, i.e. max. value of $ y\equal{}216$


vector
advanced fields
advanced fields unsolved

So I'm studying a proof of the theorem:

[hide="Theorem"]If $ q < 1$ and $ \parallel{} f_{n\plus{}1} \minus{} f_{n} \leq q \parallel{}f_n \minus{} f_{n\minus{}1}\parallel{}$, then for every $ n \geq 1,$

\[ \parallel{}f_{n\plus{}k}\minus{}f_n\parallel{} \leq q^n(1\minus{}q)^{\minus{}1} \parallel{}f_1 \minus{} f_0\parallel{},\]

where $ k \geq 1$ and therefore $ (f_n)$ is Cauchy.[/hide]

What I don't get is that when the author says

[hide="this"]"Since $ q<1$, the right-hand side tends to zero as $ n \rightarrow \infty$, and it follows that $ (f_n)$ is Cauchy,"

he didn't explain why this implies Cauchy.[/hide]

One thing I don't like analysis is that sometime I find it hard when the author don't provide the exact proof words to words using the definition of something (in this case, Cauchy sequence) and explain things with words like "this tends to this because that tends to that."

I believe in your quote, your $ k$ is arbitrary (the author should be comparing with geometric series). Recall the definition of cauchy sequence, you want that for an arbitrarily small $ \epsilon > 0$, you can find $ N$, so that $ m,n > N$ implies $ \parallel{}f_n \minus{} f_m\parallel{} \leq \epsilon$. Choose $ n$ so that your R.H.S. expression is smaller than $ \epsilon$. That's the N you are looking for.


I divided x by y and got a quotient of 3 and a remainder of 7. I then divided x by 2y and got a quotient of q and a remainder of r. If x, y, q, and r are all positive integers, what is the least possible value of r?

is it 15?  :maybe:
because x = 3yq + 7 y>7
also on dividing by 2x the remainder is y + 7 min y = 8 so r = 15  :)

[hide="Solution"]$ x \equal{} (y)(3) \plus{} 7 \equal{} (2y)(q) \plus{} r$

Since x is divided by y to get a remainder of 7, $ y > 7$. Let $ y \equal{} 8$.
$ x \equal{} (8)(3) \plus{} 7 \equal{} 31 \\
31 \equal{} (16)(1) \plus{} 15$

When $ y \equal{} 9$,
$ x \equal{} (9)(3) \plus{} 7 \equal{} 34 \\
34 \equal{} (18)(1) \plus{} 16$

$ y > 7 \\
4y \equal{} (2)(2y) > 3y \plus{} 7$

Therefore, the quotient when $ 3y \plus{} 7$ is divided by $ 2y$ will always be 1. For every increase of y by 1, r increases by 1, hence r is minimum when y is minimum, that is, $ y \equal{} 8$ and $ r \equal{} \boxed{15}$.[/hide]

[quote="Construe"]For every increase of y by 1, r increases by 1.[/quote]
This implies $ x \equal{} \infty$ because $ \lim_{y\to\infty}r \equal{} \infty$ and $ x>r$.


Anyone here want to share their experiences/thoughts on Northeastern university for a potential compsci student?

Northeastern, at undergraduate level, is a school for off-campus working students and on-campus party animals, best known for engineering and riots during the Red Sox' better years.   It charges near-ivy league tuition for mush.      At graduate level, NEU has some good departments with some excellent individual s on the faculty as well as some young Harvard- or MIT-minted PhD's doing their postdocs;  they might pay you money to study there and that could be a very good deal.


linear algebra
matrix
inequalities
trigonometry
linear algebra unsolved

No Solutions ? :lol:  :lol:

Hey Guys, think on this problem. I have a great solution for it.

$=|det(A+iB)|^2$ with simple rows / columns manipulations ..

[quote="Omid Hatami"]Another beautiful problem from my Teacher.  :D  :D
Suppose $A,B$ are two $n\times n$ matrices with coefficents in $\mathbb R$. Prove that \[ det\left( \begin{array}{cc}A&B\\-B&A\end{array} \right)\geq 0  \][/quote]

As Alekk said, here are the possible manimpulations:
$det\left( \begin{array}{cc}A&B\\-B&A\end{array} \right) = det\left( \begin{array}{cc}A-iB & B+iA \\-B&A\end{array} \right) = det\left( \begin{array}{cc}A-iB & 0 \\-B & A+iB \end{array} \right) = |det(A+iB)|^2$

I added another section to the problem. Now solve this section. I solved the first section simliar as yours alekk.

[quote="Omid Hatami"]Another beautiful problem from my Teacher.  :D  :D

a) Suppose $A,B$ are two $n\times n$ matrices with coefficents in $\mathbb R$. Prove that \[ det\left( \begin{array}{cc}A&B\\-B&A\end{array} \right)\geq 0  \]

b) Prove that if $H=A+iB$ is a positive definite Hermitian matrix, $A,B,\in M_n(\mathbb R)$, then $\det H \leq \det A$[/quote]

Are you sure about the sign of the inequality, could you please check, because it seems i've proved the same but with the reversed inequality sign.

[quote="rustam"][quote="eugene"]$...det\left( \begin{array}{cc}A-iB & 0 \\-B & A+iB \end{array} \right) = |det(A+iB)|^2$[/quote]

why do we have that?
sorry, I have seen this fact a lot of times here but cant understand it :([/quote]
Ok, i'd like to undertstand what part you don't undertsand: Do you know that the deternminant of such a block matrix $det\left( \begin{array}{cc} C & 0 \\E & D \end{array} \right) = det(C)det(D)$, if you do, then our determinant is $det(A+iB)det(A-iB)$, but you may notice that  $\bar{A+iB}=A-iB$, so the matrices $A+iB$ and $A-iB$ are conjugated and so will be their determinants, thus $det(A-iB)= \bar{det(A+iB)}$ and $det(A+iB)det(A-iB)=det(A+iB) \bar{det(A+iB)}= |det(A+iB)|^2$.

Well I checked it. You  can easily use Fischer's inequality for positive-definite hermitian matrices.
[hide="Hint"]
Suppose $X=\left( \begin{array}{cc}A&B\\-B&A\end{array} \right)$. You see $\det X=(\det H)^2$. Now you use Fischer's inequality to prove that $(\det A)^2\geq \det X\geq (\det H)^2$

[/hide]

Yeah, really that's a direct implication of Fischer's inequality...

I must have done something wrong, at first my approach was: sine $H$ is hermitian, $A^*=A$ and $B^*=-B$, and since $H$ is positive-definite there exist a matrix $T$(not neccessary unitary) such that that $T^*HT=I$ and $T^*AT=D$-diagonal with real eigenvalues on this diagonal. Now multiplying $H=A+iB$ by $T^*T$ we get $I=D+iT^*BT$ and $D=I-iT^*BT$ (*), and now i must have done a mistake...since $B$ is skew-symmetric all of it's eigenvalues are of the form $i\alpha$ and since $B$ is also real we can pick them in pairs $(i\alpha,-i\alpha)$ and $det(I-iT^*BT)=\prod (1-i^2\alpha)(1+i^2\alpha)=\prod (1-{\alpha}^2) \leq 1$, which means that $det(D) \leq 1$, but $det(D)=|det(T)|^2 det(A)=\frac{det(A)}{det(H)}$ and $det(A) \leq det(H)$- yes, there should be a mistake somehwere but i don't see where exactly. Do you see it ?

[quote="Soarer"]May I know what is Fischer's inequality?[/quote]

Fischer's inequality:
If $P=\left( \begin{array}{cc} A & B \\B^* & C \end{array} \right)$ is positive definite matrix then $detP \leq detA \cdot detC$


$ a,b,c$ are lengths of triangle.prove that:
$ \frac{1}{(a\plus{}b\plus{}c)^2}\plus{}\frac{1}{(ab\plus{}bc\plus{}ca)^2}\geq \frac{1}{3(ab^2\plus{}bc^2\plus{}ca^2)}\plus{}\frac{1}{3(a^2b\plus{}b^2c\plus{}c^2a)}$

It is only killed by pqr my friend :lol:

yes,but Can U detail it? It is not very nice! :wink:

[quote="Math pro"]$ a,b,c$ are lengths of triangle.prove that:
$ \frac {1}{(a \plus{} b \plus{} c)^2} \plus{} \frac {1}{(ab \plus{} bc \plus{} ca)^2}\geq \frac {1}{3(ab^2 \plus{} bc^2 \plus{} ca^2)} \plus{} \frac {1}{3(a^2b \plus{} b^2c \plus{} c^2a)}$[/quote]
See my solution at: http://www.toanthpt.net/forums/showthread.php?t=12530
:)


Challenge: DONT LOOK AT THE HIDE AND TRY TO FIND OUT HOW NO deFinItELy nOT means 'YES'.

[hide]00001 = a
00010 = b
00011 = c
00100 = d
00101 = e
00110 = f
00111 = g
01000 = h
01001 = i
01010 = j
01011 = k
01100 = l
01101 = m
01110 = n
01111 = o
10000 = p
10001 = q
10010 = r
10011 = s
10100 = t
10101 = u
10110 = v
10111 = w
11000 = x
11001 = y
11010 = z[/hide]

and do it like this: Capital = 1, lowercase = 0
NO deFinItELy nOT means yes. find out and make up your own messages.

my guess...this belongs in puzzles and brainteasers


trigonometry
limit
calculus
calculus computations

Solve $ y'\equal{}y^2\plus{}1$ on $ (\minus{}\infty,\infty)$? Are there any solutions?

Separating variables,

$ \frac {dy}{y^2 \plus{} 1} \equal{} dx$, Integerate, $ y\equal{}\tan (x\plus{}C).$

There are no global solutions. In every neighborhood, this equation has well-behaved local solutions, but we cannot extend them to the whole line.

We can use separation of variables to get the implicit form $ \arctan(y)\equal{}x\plus{}C.$ By existence-uniqueness, this is the only solution through any specific point. Using the definition of the arctangent carefully, we see that the best we can do for any particular value of $ C$ is to have the solution $ y\equal{}\tan(x\plus{}C)$ valid on the interval $ x\in\left(C\minus{}\frac{\pi}2,C\plus{}\frac{\pi}2\right).$ We can see that the solution "blows up" as it approaches both ends of this interval.

----

Followup problem: prove that $ y'\equal{}y^2\plus{}x^2$ has no global solutions on $ (\minus{}\infty,\infty).$

Also: if $ y$ is the solution to $ y'\equal{}y^2\plus{}x^2;\ y(0)\equal{}0,$ estimate the value of $ a$ such that $ \lim_{x\to a^\minus{}}y(x)\equal{}\plus{}\infty.$


Thanks for your patience...the forum is now unlocked and you can discuss the 2007 USAMO.

Also, the [url=http://www.artofproblemsolving.com/Wiki/index.php/2007_USAMO]questions have been posted to the AoPSWiki[/url].


i was writing a solution to a contest and i was copying and pasting latex and text together onto a word document. When i copied something like "$ 9*6\equal{}42$ this statement is true", it would copy onto the word document looking like "$ 9*6\equal{}42$this statement is true" there wouldnt be any spaces after the latex.  how do i fix this? or if i cant, is there an alternate solution to copying and pasting?

I wouldn't copy and paste from $ \text{\LaTeX}$.  I would just use eqution maker (ideally 2007) since for the most part, it handles just as well as $ \text{\LaTeX}$ and it is pretty easy to make everything look the way you want it to.

I only have 2003, but I found that under Insert, Object, and Microsoft Equation 3.0. There are lots of options there, however You an't put any spaces so I guess its the same as the $ \text{\LaTeX}$ problem.

EDIT: used the wrong slash.

I highly recommend you go for Word 2007 (if it's not too expensive for you).  There is a lot more control over the equations, including spacing, bolding, italicizing,... and there's no need to learn all of the $ \text{\TeX}$ syntax.


The polynomial $ P(x) \equal{} a_0 x^k  \plus{} a_1 x^{k \minus{} 1}  \plus{} ... \plus{} a_k$, where $ a_0 ,...,a_k$ are integers is said to be divisible by an integer m if P(x) is a multiple of m for every integral value of x. Show that if P(x) is divisible by m, then $ a_0.k!$ is multiple of m :lol:

[quote="mavropnevma"]I think that G. Polya proved first that polynomials $ \frac {x(x \plus{} 1)\cdots (x \plus{} n \minus{} 1)} {n!}$ generate over $ \mathbb{Z}$ all polynomials from $ \mathbb{Q}[x]$ that take integer values over integers.

So it's a simple corollary of this, since we are given that $ \frac {1} {m} P(x)$ is such a polynomial from $ \mathbb{Q}[x]$, hence we will have $ m \mid a_0\cdot k!$.[/quote]
It should be $ a\frac {x(x \plus{} 1)\cdots (x \plus{} n \minus{} 1)} {n!}$ generate over $ \mathbb{Z}$ all polynomials from $ \mathbb{Q}[x]$ that take integer values over integers.(a is a integer)


Prove, by mathematical induction, that any postage amount greater than or equal to 8 pence can be made up using 3 pence and 5 pence stamps
.

We can prove this instantly, because by the Chicken McNugget theorem, the largest number that can't be expressed as $ 3a\plus{}5b$ is $ 15\minus{}3\minus{}5\equal{}7$, so for all $ n\geq 8$ there exist $ a$ and $ b$ that satisfy $ 3a\plus{}5b\equal{}n$.

Not sure how to do it with induction though  :lol:

Basis step: 8 = 3 + 5.

Inductive step:

Case 1: A postage of k pence uses at least one 5 pence stamp. Replace this with two 3 pence stamps to get a new postage of (k+1) pence.

Case 2: A postage of k pence uses only 3 pence stamps. Replace 3 three pence stamps (which is possible since k > 8) with 2 five pence stamps to get a new postage of (k+1) pence.

shouldnt this be in the high school section?


June has 30 days.  One year, June has exactly four Sundays.  On which two days of the week could June 30 not have occurred that year?

[quote="mtms5467"][hide]Sunday or Monday.[/hide][/quote]
I don't see how you got that.

[hide]There are only two ways to not have 4 Sundays in 30 days (or, in other words, have 5 Sundays): the first day is a Sunday or the second day is a Sunday. In the first case the last day will be a [b]Monday[/b], and in the second case the last day will be a [b]Sunday[/b].[/hide]


It takes an airplane the same amount of time to fly 1062 miles with the wind as it does to travel 738 miles against the wind. What is the speed of the wind?

This is a simple distance problem:

Since going against the wind is 1062 and going with the wind is 738, and if we set airspeed as y and planespeed as x, we get:
$ x\plus{}y\equal{}1062$
$ x\minus{}y\equal{}738$
Solve this to get x=900, y=[size=150]162[/size]


trigonometry inequalities algebra polynomial calculus integration

Find all values of n such that tan(Pi/n) is rational.  Prove your result.
I'm 99% positive n=1,4 are the only cases that work, but I am stuck as to how to prove this.

Do you mean integer values of n? Otherwise, there are infinite solutions.

They'll probably end up messy for $ \tan$, but you might be able to use Chebyshev polynomials somehow. (http://en.wikipedia.org/wiki/Chebyshev_polynomials) They can be used to prove, for instance, that the only rational values that $ \cos ( p\pi /q)$ can take are $ 0, \pm 1, \pm 1/2$.

Yes, my apologies.  I meant positive integral values for n.


You know that $x^2+y^2, x^3+y^3, x^4+y^4$ are rational (Q). Prove that also $x+y$ and $xy$ are rational numbers.

I'm going to go for the kalva-style solution.  Suffice it to say that I solved all the algebra during Econ today  :lol:

Let $x^2+y^2=a$, $x^3+y^3=b$, and $x^4+y^4=c$.  Then $xy=\frac{2b^2+a^3-3ac}{2(a^2-c)}$, and $x+y=\frac{b}{a-xy}$.

Magnara: I like you solution very much. Original solution has similar ideas, but it's written on much longer piece of paper :)


The interior angles of a convex non-equiangular polygon of 9 sides are ina arithmetic progression. Find the least positive integer that limits the upper value of the common difference between the measures of the angles

[hide]
I'm assuming we're working in degrees here

The sum of the angles in a 9 sided polygon is

$ 180(9-2) = 1260$

because the angles are in arithmetic series, the middle (5th) term must be exactly $ \frac{1260}{9}= 140$

also, because the polygon is convex, all angles must be less than 180.
There are four angles that are greater than the 5th one which is 140 so
let $ x$ be the common difference

$ 140+4x < 180$

$ x<10$

$ x_{max}= 9$
[/hide]


inequalities
geometry
geometric transformation
reflection

A point is placed on each side of a square of area 1. The four point are vertices of a quadrilateral with sides a, b, c, d. Prove that

2 :rt2: <= a + b + c + d

Thanks.

I have a proof. Help or challenge? If it's a challenge, I will leave it to other people.

I assume it is an help.

[hide]Place distances x,y,z,t on the four sides.  By Pythagoras for instance :

a = sqrt (x+y), b = sqrt ((1-y) + z), c = ....

Then use sqrt (x+y) >= (x+y)/ :rt2: [/hide]

belenos wrote:I assume it is an help...

Hey, My proof is different from yours! It's more geometric flavor.

[hide]

Make two points on the extension of the bottom edge so that they are the mirror images of the point on the bottom with respect to the two vertical sides. These two points together with the point on the top edge form a triangle of area 1.

a+b+c+d >= x + y (the sum of two sides of the triangle) >= 2 :sqrt: (xy) >= 2 :sqrt: (2 * area) = 2 :sqrt: 2.

[/hide]

[quote="trickdacy"]I'm not sure how rigorous this is, but:

If you had points on all four corners of the square, then the sum of the sides would be 4.  If you move each point counterclockwise around the square, then the sum would get smaller and smaller until each vertex is in the very center of each side.  Anywhere past that, and the sum of the side lengths would start getting bigger again.  By Pythagoras, each side of the smaller square has side length 1/ :rt2: , so the sum of the sides is 4/ :rt2: =2 :rt2:
This is as small as it can get, so a+b+c+d>=2 :rt2:

Am I allowed to say QED now?[/quote]

You would have to prove that a+b+c+d is the smallest in can get when the four points are at the midpoints of the sides of the square. What if from this position you moved the top point a little bit to the left? Then the top left side will be smaller and the top right side would be bigger. How do you know that the sum of the top left side and the top right side is bigger than what it was before?

[quote]Am I allowed to say QED now?[/quote]

I don't think so, since that is not very rigorous. But perhaps the general argument can be made rigorous with a smoothing argument, though I have little idea of how to use the smoothing principle myself (I usually just see it to prove AM-GM).

I thought about this problem a little more and found a  nice geometric proof.

[hide]

Make two points on the extension of the bottom edge so that they are the mirror images of the point on the bottom with respect to the two vertical sides.

Now, reflect these two points with respect to the top edge. We have four points which are the vertices of a new square with side length 2.

It's easy to see that a+b+c+d >= the diagonal of the new square = 2 :rt2:

[/hide]


I think it would be really cool to have a forum for AoPS beginners and people grades 4~8.
People could hang out and talk about whatever math/other activites they do.
This way the AoPS beginer could not be confused and kids like my age could talk about what we do.

This may not be the worlds best idea but I think it would be cool.

If you mean talk about the things/hobbies you like to do, there's always Games and Fun Factory or Polls.

ya, you could start a chat room or something in G&FF
most forums are math related, but if you want to just chat about other stuff G&FF is the best place for this

Actually I think I phrased this wrong.
I meant where we could discuss math problems for our age level without it being related to a competion or whatever.
Also AoPS begginers probably don't start off knowing about everything about AoPS and I remember poking around (and saddly I still kida do) looking for exactly how to use AoPS to it's full extent. This forum could be used so all those things could be written up in one nice neat place for a begginer to be able to enjoy AoPS at its full to start off with.
This AoPS begginer stuff may be on the AoPS wiki but the first time I ever went on the AoPS wiki was several months after I started AoPS.

[quote="levans"]The Classroom Math and  MOEMS forums are for grades 4 to 8.[/quote]
And every forum on this site, including those, tends to see the level of the questions posted on it rise inexorably, until eventually many of the questions asked are not appropriate for the originally intended audience. If you need to be convinced of this, just do a random browse of the Classroom Math forum and see what's actually there.

Adding onto levans; make sure you post in the right forum :wink:

i think there are already threads for grades 4-8


inequalities
logarithms
real analysis
real analysis unsolved

Let $x_i\ (i=1,2,\cdots,n)$ be positive numbers such that $\sum_{i=1}^n x_i=k$.
Prove the following inequality.

\[\sum_{i=1}^n x_i\ln x_i\geqq k\ln {\frac{k}{n}}\]

Isn't this just the convexity of $x\ln x$? :?

if it was:

$\sum_{i=1}^n x_i\ln x_i\geqq n\ln {\frac{k}{n}}$

then it'd be indeed trivial [just Jensen], but it seems a bit weird in this form...[b]kunny[/b] is it correct for sure?

To Megus:
No,it isn't.I can't understrand how you use Jensen's inequality.

[quote="grobber"]No, it looks just like Jensen as it is:

$\frac{\sum x_i\ln x_i}n\ge \frac kn\ln\frac kn$ (I divided the initial inequality by $n$). Am I missing something here? :?[/quote]

No,you aren't.You are right.


[quote="FAlin"]Let X1，X2...，Xn are positive real numbers
Prove that 1/X1 + 2/(X1+X2) + 3/(X1+X2+X3)+...+n/(X1+X2+...+Xn) < 2(1/X1 + 1/X2 + 1/X3 +...+ 1/Xn)[/quote]
Let me $ \text{\LaTeX}$ it for you and please next time try to use $ \text{\LaTeX}$  :wink:

Let $ x_1,x_2,\cdots,x_n$ are positive real numbers. Prove that:
\[ \frac {1}{x_1} + \frac {2}{x_1 + x_2} + \cdots + \frac {n}{x_1 + x_2 + \cdots + x_n} < 2 \left(\frac {1}{x_1} + \frac {1}{x_2} +  \cdots + \frac {1}{x_n}\right)\]

hello, in the case $ n\equal{}2$ we have to prove
$ \frac{1}{x_1}\plus{}\frac{2}{x_1\plus{}x_2}<2\left(\frac{1}{x_1}\plus{}\frac{1}{x_2}\right)$ this is equivalent with
$ 0<x_1(x_1\plus{}x_2)\plus{}x_1^2\plus{}x_2^2$ and the is true because of $ x_1,x_2$ are positive reals.
Sonnhard.

See here [url]http://www.mathlinks.ro/viewtopic.php?t=319781&start=100[/url] (Post no 104).


What is the area of the triangle with vertices $ (1, 4)$, $ (3, 1)$ and $ (11, 1)$?

we can easily see the length is 11-3=8 and the height is 4-1=3

8*3/2=12


A 4-digit square number is composed so the first 2 digits make up a square number and the last two digits make up a sqaure number.  What is this number?

  This problem can easily be solved with a systematic "guess-and-test" approach, however challenge yourself to find a another, non-guess-and-test solution.

The answer is very quick to find (one of the first I tested), but I will explain how to get it. Note that the way I solved it is not mathcounts level, but the problem was posted in a mathcounts forum, and I will solve it the only way I know how:

[hide]Quadratic residues mod 9 are 1,4,0,7. Since 100a+b (mod 9) :equiv: a+b (mod 9), we need to find two of these residues that add to another one. The only was to do this is for one of them to be 0. Therefore, one of the squares is either 9 (actually it can't be 9, because 9 is one digit), 36, or 81. If 36 went at the end, the square root would have to end in 4 or 6. If it ended in 81, the root would have to end in 1 or 9. The tens digit is determined by 20ab (a,b are the digits). If the tens had to be 30, and we already have 10 from the four, then a and b would be 1 (impossible). If we already have 30 from the 6, then a or b would be 0 (impossible). If 20ab=80 but we already got 80 from the 9, then a or b would be 0 (impossible). If 20ab=80 with nothing beforehand, ab=4, 2-2 is impossible, so try 41 2 =1681. Success!

I hope somebody understood that, at least.[/hide]

[hide]
Call the two numbers $p$ and $q$, so that $N = 100p^2 + q^2$. $p$ and $q$ are both $\geq 4 \text { and } \leq 9$ Now notice that:

\begin{eqnarray*}
N&=&100p^2+q^2\\
N-q^2&=&100p^2\\
\sqrt{N-q^2}&=&10p\\
\frac{\sqrt{N-q^2}}{10}&=&p\\
\frac{N-q^2}{100}&=&p^2\\
\end{eqnarray*}
So $N-q^2$ must be divisible by 100, and therefore must be $\geq 1600$. Suppose that $p=4$, and thus $N-q^2=1600$.
 Oh whatever, just use guess and check. :blush:
[/hide]

[quote="asdf4"]Wasn't that in the Chapter competition?
We missed it because we accidently put a point in the beginning. But it still made a perfect square, but they said that a perfect square is considered an integer.

If the recorder didn't put that decimal point we woulda won.  :(

But still 4 people from my school placed still went on to state as indivisuals and did fairly good on state.[/quote]

must've been a big chapter if you can send 4 individuals to state... wait... i think our chapter also sent 4... only 1 of them was from our school though, but our team went and dominated state... (beat the 2nd place team by like 6 or 7 points)

I was the only one from my school in the top
[hide]29[/hide]


function
algebra
polynomial
complex numbers
linear equation

Why do certain non-linear systems of equations have solutions when there are more variables than equations? Thanks.

well if you can cancel some of the terms by subtracting from each side or something.......give an example

Usually it's because they are on the verge of defying an inequality.

A simple example is:

$ x^2 \plus{} y^2 \minus{} 2x \minus{} 2y \plus{} 2 \equal{} 0$
$ (x\minus{}1)^2 \plus{} (y\minus{}1)^2 \equal{} 0$
So $ x \equal{} 1, y \equal{} 1$
This is because since $ a^2 \geq 0$,
$ a^2 \plus{} b^2 \geq 0$, with equality when a = b = 0.

Here's a visual reason for 3 variables, two equations, to try to help. Think of each equation as a surface in 3 dimensions. For instance if the equations are linear, the surfaces will be planes. A solution to the system is where the surfaces intersect. Now, you can have two surfaces that only touch in one point. This gives a unique solution to a system of three variables, in two equations.

The reasoning that shows that two linear equations cannot determine three variables is that two planes cannot intersect at a single point, its either no where or a line.

It depends a lot on how you restrict your solution space.

In the example given by [b]iniquitus[/b], if $ S$ is the unrestricted solution space, then $ S \cap \mathbb{R}^2 \equal{} (1,1)$ -- in other words, if you restrict your solution space to ordered pairs of real numbers, the only one that is still valid is $ (1,1)$. Of course, you can solve the equation for $ x$ and get infinitely many ordered pairs of complex numbers.

Here's a parallel situation. Say you want to find all positive integer solutions to $ xy \equal{} 1$. Obviously there are infinitely solutions in the complex numbers, or even in the real numbers, but the only one of these that satisfies our restriction is $ (1,1)$.

For most of the functions you will be dealing with in high school, you will only get such a small number of solutions if you restrict the solution space.

[quote="The Zuton Force"]$ S \cup \mathbb{R}^2 \equal{} (1,1)$[/quote]I think you meant \cap $ S\cap\mathbb{R}^2\equal{}(1,1)$

See my discussion [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=204068&search_id=460994992]here[/url].  Let me expound a little more.

A linear equation in $ n$ variables [b]always[/b] determines an $ n \minus{} 1$-dimensional hyperplane.  (This is easy to verify in the cases $ n \equal{} 2, 3$).  That's why we like linear equations; hyperplanes are extremely easy to study and linear equations always give hyperplanes.  The intersection of $ n$ independent $ n \minus{} 1$-dimensional hyperplanes has dimension $ 0$, so it is a finite set of points (this is linear algebra).

A nonlinear equation in $ n$ variables can determine a hypersurface of dimension less than $ n \minus{} 1$.  In the words of my other post, nonlinear equations can represent "two equations in one"; alternately, they can be "degenerate."

The second thing that can happen is that the intersection of two nonlinear equations in $ n$ variables can determine a variety of dimension less than $ n \minus{} 2$, and so forth.  This occurs, for example, if two surfaces (determined by equations when $ n \equal{} 3$) are tangent and determine a point (which has dimension less than $ n \minus{} 2 \equal{} 1$).

Edit:  The fundamental thing going on from an algebraic point of view, though, is that the real numbers are not [b]algebraically complete[/b] (in other words, there exist polynomials with no roots).  Much of this behavior disappears when you regard systems of polynomials over the complex numbers.

But examples of single Diophantine equations in two or even three variables can be found with only a single solution; those are more intuitive than real systems that have unique solutions when it seems like they shouldn't.

I understand it now, thanks for the responses.


(i) Given that $ b^{2}-c$ = $ -k^{2}$, where k>0; show that the roots of the eqn $ x^{2}-bx+c=0$ are $ x=b\+-ki$

(ii)If a,b and c are real and $ b^{2}<4ac$, show that the roots of $ ax^{2}+bx+c=0$ are complex conjugates.

Dont know how (i) and (ii) are related. I done (i) but not (ii)

let $ b^{2}\minus{}4ac\equal{}\minus{}k^{2}$. Show in similar way that he roots are
$ \frac{b}{2a}\pm\frac{ki}{2a}$. Real part of those roots is the same, imiginarz difers in sign => the roots are conjugate. [/b]

[hide="(ii)"]
\[ ax^{2}\plus{}bx\plus{}c\equal{}0\]
The Solutions to this equation are:

$ x \equal{}\frac{\minus{}b\pm\sqrt{b^{2}\minus{}4ac}}{2a}$ with $ a\neq 0$

Since $ b^{2}< 4ac$ the discriminant is negative and therefore:

$ x \equal{}\frac{\minus{}b\pm i\sqrt{\minus{}b^{2}\plus{}4ac}}{2a}$

So the equation have the roots:
\[ x\equal{}\frac{\minus{}b}{2a}\plus{}\frac{\sqrt{\minus{}b^{2}\plus{}4ac}}{2a}i\]
and
\[ x\equal{}\frac{\minus{}b}{2a}\minus{}\frac{\sqrt{\minus{}b^{2}\plus{}4ac}}{2a}i\]
[/hide]


Please excuse me if this is in the wrong forum, but i could not find a forum i saw relevant for this question.

"What is the probability that two different cards (of any suit) will be next to each other in a randomly shuffled deck of 52 playing cards" (no jokers)

for example, what is the probability that an Ace will be next to a King.

I realise that this is most likely a relatively simple probability question, although unfortunately i haven't studied probability before.

It is actually not particularly easy -- there are a number of different cases to check.  I think the easiest way to go about this is to consider the cases when the aces are all separated, when some of them are adjacent to others (there are several options here: they could be 1 2 1 or 2 2 or 3 1 or 4) and for each of these options consider seperately if there are aces at one or both ends of the deck.  In each of the dozen or so cases that result, you should be able to calculate the probability that none of the kings is next to any ace, and by counting the total number of ways each case can occur, you'll be able to get your answer.

Is that good enough for you?

[hide="this may be wrong, but if it is can someone explain why"]Why couldn't it just be the probability of drawing a king after drawing an ace plus the probability of drawing an ace after drawing a king?
You could go through the deck until you come across an ace and draw the next card. the probability that that card is a king is $\frac{4}{51}$
and then you could go through the deck until you come across a king and draw the next card. the probability that that card is an ace is also $\frac{4}{51}$
so the total probability would be $\frac{8}{51}$
If this is faulty logic i apologise in advance[/hide]


All of the lines are perpendicular to one another, so AB=8+6-4=10. AH+GF+ED=10, because you can shift them all up until they form a straight line, which is parallel and the same length as BC, which is 10. Thus, the perimeter is 10+10+8+4+6+10=48


When I clicked the Memberlist, it sent me to the URL

http://www.artofproblemsolving.com/Forum/memberlist.php?level=2

whereas the "real" Memberlist was shown after I refreshed the page.

[hide="Real Memberlist"]
http://www.artofproblemsolving.com/Forum/memberlist.php
[/hide]

[hide="Modded Memberlist"]
http://www.artofproblemsolving.com/Forum/memberlist.php?level=2
[/hide]

My question is, what is the difference between these two lists, is it just because one is a list of active users?

My support question is, why did the the URL bring me to the "level 2" list, instead of the usual memberlist?

I'm also using Firefox 2.0.0.13, along with XP, but the modded memberlist only appears every once in a while, and it is usually a random time when I see it.

The second list appears to be all moderators.


geometry
trigonometry
rotation
circumcircle
vector
geometry unsolved

Let $ ABC$ be a triangle, and points $ P$ and $ Q$ are outside of it such that $ AP \equal{} AB$, $ AQ \equal{} AC$ and $ \angle PAB \equal{} \angle QAC$. $ R$ is the intersection point of $ CP$ and $ BQ$ and $ O$ is the circumcentar of triangle $ BCR$. Show that $ AO \bot PQ$.

Jesi li to ti  ili je ovo slucajno Mladenov zadatak? :o
Complex numbers, very easy !

Sorry?
Complex numbers, hm, i dont't like that... Is there any synthetical solution?

I used a little bit of trigonometry, but here it is:
let $ R=PC\com{QB}$ triangles $ PAC$ and $ BAQ$ are equal, and one is the rotated of the other by an angle of $ CAQ=\alpha$ $ \Rightarrow$ $ \angle{CRQ}=\angle{BRP}=\alpha$ this means both $ APBR$ and $ AQCR$ are cyclic. Let $ O_1$ the circumcenter of $ APBR$ and $ O_2$ the circumcenter of $ AQCR$. What we want to prove is that $ OP^2-OQ^2=AP^2-AQ^2=AB^2-AC^2$. The power from $ Q$ to $ BRC$ is $ OQ^2-OC^2=QR\cdot{QB}$, analogously: $ PO^2-OC^2=PR\cdot{PC}$. $ \Rightarrow$ $ OP^2-OQ^2=PR\cdot{PC}-QR\cdot{QB}$ but $ PR\cdot{PC}$ is the power of $ P$ respect to $ AQCR$ so equals $ PO_2^2-R_2^2$ analogously, $ QR\cdot{QB}=QO_1^2-R_1^2$ then $ OP^2-OQ^2=PO_2^2-R_2^2-(QO_1^2-R_1^2)$ but $ PO_2^2=AB^2+R_2^2-2AB\cdot{R_2)\cos{PAO_2}}$ and analogously: $ PO_1^2=AC^2+R_1^2-2AC\cdot{R_1}\cos{QAO_1}$ so pluging in this equalities and noticing $ \angle{QAO_1}=\angle{PAO_2}$, yields: $ OP^2-OQ^2=AB^2-AC^2-2\cos{QAO_1}\cdot(AB\cdot{R_2}-AC\cdot{R_1})$ but because $ AQB$ is similar to $ ACP$ then $ PO^2-OQ^2=AB^2-AC^2$ and we are done.

[quote="mstoenescu"][quote="Nemion"] What we want to prove is that $ OP^2 \minus{} OQ^2 \equal{} AP^2 \minus{} AQ^2 \equal{} AB^2 \minus{} AC^2$. [/quote]

I don't understand why this think implies that $ AO\perp{PQ}$ .
Can you explain, please ? :([/quote]

that's a well-known and very useful theorem,we have:

$ XY\perp UV\iff XU^2 \minus{} XV^2 \equal{} YU^2 \minus{} YV^2$

the proof of this theorem is pretty easy:

let $ X'$ and $ Y'$ be the feet of the perpendiculars from $ X$ and $ Y$ to $ UV$,so $ XY\perp UV\iff X'\equiv Y'$.

now note that:

$ X'\equiv Y'\iff UX' \minus{} X'V \equal{} UY' \minus{} Y'V$ (*)

where all distances are directed distances.

now note that:

$ UX' \plus{} X'V \equal{} UV \equal{} UY' \plus{} Y'V$

thus (*) would be equivalent to:

$ X'\equiv Y'\iff UX'^2 \minus{} X'V^2 \equal{} UY'^2 \minus{} Y'V^2$

which is equivalent to:

$ XU^2 \minus{} XV^2 \equal{} YU^2 \minus{} YV^2$

thus:

$ XY\perp UV\iff XU^2 \minus{} XV^2 \equal{} YU^2 \minus{} YV^2$

Thank you [color=red]BaBaK Ghalebi[/color]! It's really a nice theorem !

Theorem: $ AC\perp BD\iff AB^2\plus{}CD^2\equal{}BC^2\plus{}DA^2$.

Proof: Proceed by vectors. Take an arbitrary origin and let $ A$ be a vector denoting point $ A$ a.s.o. Observe \[ AB^2\equal{}(A\minus{}B)\cdot (A\minus{}B)\equal{}A\cdot A\minus{}2A\cdot B\plus{}B \cdot B\]
\[ AB^2\plus{}CD^2\minus{}BC^2\minus{}DA^2\equal{}\minus{}2( A\cdot B\plus{}C\cdot D\minus{}B\cdot C\minus{}D\cdot A)\equal{}\minus{}2(A\minus{}C)\cdot (B\minus{}D)\] Then the last line is equivalent to the vector connecting $ A$ and $ C$ being perpendicular to the vector connecting $ B$, and $ D$, so we are done.

[quote="SpongeBob"][color=darkred]Let $ ABC$ be a triangle. The points $ P$ and $ Q$ are outside of it such that $ AP = AB$ , $ AQ = AC$ and $ \widehat {PAB} = \widehat {QAC}$ .

Denote the intersection $ R\in CP\cap BQ$ and the circumcenter $ S$ of the triangle $ BCR$ . Prove that $ AS \bot PQ$ .[/color][/quote]

[color=darkblue][b][u]Preliminary.[/u][/b] Denote $ m(\widehat {PAB})=\phi$ . Prove easily that $ \triangle APC\equiv\triangle ABQ$ , the quadrilaterals  $ APBR$ , $ AQCR$

are cyclically and $ m(\widehat {BRC})=180^{\circ}-\phi$ , $ m(\widehat {BSC})=2\phi$ . Denote $ C(O,R)$ - the circumcirle of $ \triangle ABC$ .

[b][u]Proof I (with complex numbers).[/u][/b] Denote $ X(x)$ - the point $ X$ with affix $ x\in\mathbb C$ . I"ll choose the origin in $ A$ , i.e. $ A(0)$ .

Define $ \omega =\cos\phi +i\cdot\sin\phi$ , where $ \phi =m(\widehat {PAB})$ . Thus, $ \omega\overline {\omega}=1$ , $ p=\overline {\omega}b$ , $ q=\omega c$ and $ s=\frac {b-\omega^2c}{1-\omega^2}$ .

Denote $ z=\frac {q-p}{s}$ . Hence $ z=\frac {\omega^2-1}{\omega}=\omega -\overline {\omega}$ . Observe that $ z+\overline z=0$ , i.e. $ AS\perp PQ$ .

[b][u]Proof II (metric).[/u][/b] Observe that $ \{\begin{array}{c}
BP=2c\cdot\sin\frac {\phi}{2}\\\\
CQ=2b\cdot\sin\frac {\phi}{2}\end{array}$ . Apply the [b]generalized Pythagoras' theorem[/b] in $ \triangle SPB$ , $ \triangle SQC$ :

$ \{\begin{array}{c}
SP^2=BS^2+BP^2-2\cdot BS\cdot BP\cdot \cos (B-\frac {3\phi}{2})\\\\
SQ^2=CS^2+CQ^2-2\cdot CS\cdot CQ\cdot\cos(C-\frac {3\phi}{2})\end{array}$ . Thus $ \boxed {BP^2-CQ^2=2(1-\cos\phi)(c^2-b^2)}$ ,

$ BS=CS$ and define $ \Omega\equiv 2\cdot CS\cdot CQ\cdot\cos(C-\frac {3\phi}{2})-2\cdot BS\cdot BP\cdot\cos(B-\frac {3\phi}{2})$ . Therefore,

 $ \Omega =2\cdot\frac {a}{2\cdot\sin\phi}\cdot 2\sin\frac {\phi}{2}\cdot[c\cdot\cos(B-\frac {3\phi}{2})-b\cdot\cos(C-\frac {3\phi}{2})]=$

$ \frac {aR}{\cos\frac {\phi}{2}}\cdot[2\sin C\cos(B-\frac {3\phi}{2})-2\sin B\cos(C-\frac {3\phi}{2})]=$

$ \frac {2R^2\sin (B+C)}{\cos\frac {\phi}{2}}\cdot[\sin(C-B+\frac {3\phi}{2})-\sin(B-C+\frac {3\phi}{2})]=$

${ \frac {2R^2\sin (B+C)}{\cos\frac {\phi}{2}}\cdot 2\sin (B-C)\cos\frac {3\phi}{2}}=$ $ 4R^2(\sin ^2C-\sin ^2B)(4\cos^2\frac {\phi}{2}-3)$ $ \implies$ $ \boxed {\Omega =(c^2-b^2)(2\cos \phi -1)}$ .

$ SP^2-SQ^2=(BP^2-CQ^2)+\Omega =$ $ 2(1-\cos\phi )(c^2-b^2)+(c^2-b^2)(2\cos\phi -1)=c^2-b^2$ $ \implies$ $ AS\perp PQ$ .[/color]


modular arithmetic
number theory
relatively prime
algebra unsolved
algebra

Does anyone how to prove the following:

[color=green]a and b are relatively prime if and only if There exist integers s and t satisfying sa + tb = 1[/color]

Thanks very much!!!  :lol:

The hard part is the "only if".  Hint:  this is equivalent to proving that if $a$ and $b$ are relatively prime then there exists a multiplicative inverse to $a$ mod $b$.

First, let's assume that $a$ and $b$ aren't coprime. Then $a=da_1$ and $b=db_1$ where $d>1$. But then $1=sa+tb=d(sa_1+tb_1)$, which means that $d|1$, and that's impossible.

Now, let's assume that $a$ and $b$ are coprime. We'll prove that the numbers $0, b, 2b,\dots,(a-1)b$ give pairwise distinct remainders modulo $a$. Assume the opposite, that there are distinct $k,l\in\{0,1,\dots,a-1\}$ such that $kb\equiv lb\pmod{a}$. Then $a|(k-l)b$, but as no prime factor of $a$ is a prime factor of $b$, it means that $a|k-l$. Since $|k-l|<a$, that implies $k=l$.
Hence there is $k_0<a$ such that $k_0b\equiv 1\pmod{a}$, which means that there exists $l_0\in\mathbb{Z}$ such that $k_0b-1=l_0a$, so we can take $s=-l_0$ and $t=k_0$. QED.


Putnam
Columbia
college
college contests

Hi, this year I am working at an internship at NYC, but I still want to take the Putnam exam, so I emailed a professor at Columbia to ask where to take it.  Now, I didn't tell her that I am not a student at Columbia because I thought it would be ok.  I am a little skeptical now.  Can I take Putnam at a college where I am not a undergrad?  I am too shy to ask her in person.

You're too shy?  That's not a good thing.

I believe that you register through a school so if Columbia is willing to register you as part of their team, I guess they could.  I would ask, though.  Work up the courage.

Except that the registration form was due two weeks ago.

Nah, that's the yellow sheet that means nothing (sometimes, when I am not sure how many people will participate, I put a few "John Smiths" and "Elizabeth Browns" in it) :P. The pink one is the one where the team gets finally fixed and it is due later. Plus you can always participate without being a team member :).

[quote="fedja"]Plus you can always participate without being a team member[/quote]
I know of a Putnam fellow who wasn't a team member because he wasn't a full-time student at the university in question. That's very likely to be the policy, although it's entirely up to whoever runs the exam locally.

Wasn't Gabriel Carrol a Putnam fellow in high school?  He had to have registered with someone.

The official results of the 2000 Putnam list as a Putnam Fellow, "Gabriel Carroll, UC Berkeley." He was at that time a student at Oakland Technical HS and he took all of his math classes at UC Berkeley. He was not a member of the UC Berkeley team; presumably Prof. Kahan might have felt that it would be improper to so include him. But he took the exam at Berkeley. (So did jmerry, who was a college freshman at the time and was on the team.)


It is trivial to prove that sin1*sin2*...*sinn tends to zero, as well as cos1*cos2*...*cosn. What about tg1*tg2*...*tgn? I've tried to answer, but I couldn't. Any ideas?

Maybe it a useless post, and I think everybody has already thought of this, but I think that if the limit exists, then it should be 0, because it's not hard to prove that there are infinitely many n s.t. tgn<0, so the sequence changes sign infinitely many times, so there are infinitely many terms >0 and infinitely many <0.

So all that's left now is to prove that a_n= \pi {k=1->n}tgk doesn't tend to 0 as n->00.

If somebody followed the discussion in harazi's [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=1695]100th message[/url] closely, he should be able to answer this question now too  :P


hey does anyone have the answers for - Workouts in Intermediate Economics; Varian 7th ed.  I have ch. 2,3,4,5,6, 14,15,16.  I really need ch's 27,28,29 and the rest.  Thanks

hey my friend can you send me varian solutions for ch. 2,3,4,5,6, 14,15,16?

Here is the link to the Ch's I was able to find

http://www.mathlinks.ro/Forum/viewtopic.php?t=80878&start=20


Let $ a,b,c$ be positive real numbers, Prove that :
$ \sum \frac{a^2}{(b\plus{}c)^2}\plus{}\frac{10abc}{(a\plus{}b)(b\plus{}c)(c\plus{}a)} \ge 2$

It's well known that:

$ \sum\frac{a^2}{b^2\plus{}c^2} \ge \sum\frac{a}{b\plus{}c}$.

So we have to prove that:

$ \sum\frac{a}{b\plus{}c}\plus{}\frac{10abc}{(a\plus{}b)(b\plus{}c)(c\plus{}a)} \ge 2 \Longleftrightarrow a^3\plus{}b^3\plus{}c^3\plus{}\sum_{sym}a^2b\plus{}13abc \ge 2\sum_{sym}a^2b\plus{}4abc \Longleftrightarrow a^3\plus{}b^3\plus{}c^3\plus{}9abc \ge \sum a^2b$

which is straight from schur....

Dimitris

[quote="Dimitris X"]It's well known that:

$ \sum\frac {a^2}{b^2 \plus{} c^2} \ge \sum\frac {a}{b \plus{} c}$.

So we have to prove that:

$ \sum\frac {a}{b \plus{} c} \plus{} \frac {10abc}{(a \plus{} b)(b \plus{} c)(c \plus{} a)} \ge 2 \Longleftrightarrow a^3 \plus{} b^3 \plus{} c^3 \plus{} \sum_{sym}a^2b \plus{} 13abc \ge 2\sum_{sym}a^2b \plus{} 4abc \Longleftrightarrow a^3 \plus{} b^3 \plus{} c^3 \plus{} 9abc \ge \sum a^2b$

which is straight from schur....

Dimitris[/quote]

You misread the inequality.


integration
trigonometry
calculus
function
geometry
calculus computations

$\displaystyle \int_{-\pi} ^{2\pi} \tan ^2 x\, dx$
$\displaystyle \int_{-\pi} ^{2\pi} \sec ^2 x-1\, dx$
$\displaystyle \tan (2\pi) - 2\pi - \tan (-\pi) -\pi$
$= -3\pi$

But since $\tan^2 x$ is never negative, how did I come up with a negative answer?

This integral is improper at $\frac{3\pi}2$, and diverges to $\infty$, since it is comparable to $\frac1{\left(x-\frac{3\pi}2\right)^2}$ near $\frac{3\pi}2$.

Integrating across a singularity is always trouble.

That's what I thought. So my teacher is wrong.

[quote="Kent Merryfield"]There is no important difference between your problem and this claim:

$\int_{-1}^1\frac1{x^2}\,dx= -\frac1x|_{-1}^1=-1-1=-2$

It's just that without the trig functions fogging your vision, it's more obvious that the latter example is wrong, and more obvious why it's wrong.[/quote]

If we want to interpret it as " area under curve " , how would the negative thing explain ?

In Kents' example, there is an obvious discontinuity at $x=0$.

In Dereks' problem, there is a discontinuity at $x= \pm \pi/2, 3 \pi/2$.

In both cases the pseudo-result is negative, and this is strange, because both integrands were positive for every between the limits, in fact for all real values both are positive.

Even if you didn't notice that you integrated through a singularity, you would notice that a sum of positive numbers somehow is negative.

For that matter, what is $\int_0^{\pi} \tan x\, dx$?
Since $\tan (\pi/2 - x) = - \tan (\pi/2 + x)$ one might consider the integral to be $0$, but in reality it DNE, right?


let $ a_1,a_2,...,a_{2008}$ be real numbers. prove that there exists 2008 matrices $ A_1,...,A_{2008}$ ($ n\times n$ matrices) such that $ detA_k\equal{}a_k$ for all k=1,..., 2008 and |$ \sum_{k\equal{}1}^{2008} A_k$|=2009


[quote="rnwang2"]Is it true that the first problem of the five on the USAMTS is the easiest?[/quote]
For this round for me, 1 wasn't the easiest.

[quote="Iversonfan2007"]um it depends for the person. For round 1, I thought 5 was the easiest, and then 1...so it really depends on what your strengths and weaknesses are[/quote]

Yeah...apparently he's good at 3-d geometry.

I'm good at combinatorics, so I didn't find 2b as hard as 5, since I suck at geometry.

#1 is always the easiest for me. #5 is always the hardest. This could be because #5 is always geometry... :ninja:


calculus
integration
trigonometry
induction
calculus computations

[quote="The Wicker Man"]Show
$ \int_{ \minus{} \pi}^{\pi}\frac {2^{2n }\prod_{k \equal{} 1}^{2n }(\cos{x} \minus{} \cos{\frac {k\pi}{2n \plus{} 1}})}{(1 \plus{} e^x)^{\prod_{k \equal{} 1}^{n \minus{} 1}\cot{\frac {k\pi}{2n}}}}dx \equal{} \pi$, $ n \ge 2$ ($ n \in \mathbb{N}$).[/quote]
Induction on $ n$... You tried that?