function
Functional inequality
IMO Shortlist
algebra

[hide]a) Because $ f,g$ are strictly increasing, we have $ f(x), g(x) \ge x$. Then $ g(g(x)) \le f(g(g(x))) < g(f(x))$, so $ f(x) > g(x)$ for all $ x$. Suppose $ f(x) > g^n(x) \equal{} \underbrace{(g \circ g \cdots g)}_{n\ \text{times}}\,(x)$; then
\[ g^{n \plus{} 2}(x) < f(g^{2}(x)) < g(f(x))\ \Longrightarrow\ g^{n \plus{} 1}(x) < f(x).\]Induction gives $ f(x) > g^n(x)$ for all $ x,n$. If $ g(k) > k$ for some $ k$ then $ f(k) > g^n(k) \ge n \plus{} k$, but then taking any $ n \ge f(k) \minus{} k$ gives a contradiction. Otherwise $ g(x) \equal{} x$ for all $ x$ which evidently fails.

b) Consider $ f\left(a \minus{} \frac 1b \right) \equal{} (a \plus{} 1)^3 \minus{} \frac 1b, \quad g\left(a \minus{} \frac 1b \right) \equal{} a \minus{} \frac {1}{ab}$. Then
\[ f\left(g\left(g\left(x\right)\right)\right) \equal{} (a \plus{} 1)^3 \minus{} \frac {1}{a^2b} < g\left(f\left(x\right)\right) \equal{} (a \plus{} 1)^3 \minus{} \frac {1}{(a \plus{} 1)^3b}.\]
[/hide]

For the second part, we can inductively construct $ g$ if we take $ f(x) \equal{} x \plus{} 1$. We well take any increasing function $ g$ in $ [0,1)$ for which $ g(x)$ stays in the same interval $ [0,1)$. Assume we constructed till $ [n,n \plus{} 1)$. Construction of $ g(x)$ for $ x$ being in $ [n \plus{} 1,n \plus{} 2)$ will be the following: Take $ g(n \plus{} 1)$ so that: 1) $ g(n \plus{} 1)$ is in $ S$; 2) $ g(n \plus{} 1) < n \plus{} 2$; 3) $ g(n \plus{} 1) > g(g(n)) \plus{} 1$;  For any positive integer $ k$,  take $ g(n \plus{} 2 \minus{} \frac {1}{k \plus{} 1})$ such that: 1) $ g(n \plus{} 2 \minus{} \frac {1}{k \plus{} 1})$ is in $ S$; 2) $ g(n \plus{} 2 \minus{} \frac {1}{k \plus{} 1}) < n \plus{} 2$; 3) $ g(n \plus{} 2 \minus{} \frac {1}{k \plus{} 1}) > g(n \plus{} 2 \minus{} \frac {1}{k}$; 4) $ g(n \plus{} 2 \minus{} \frac {1}{k \plus{} 1}) > g(g(n \plus{} 1 \minus{} \frac {1}{k \plus{} 1})) \plus{} 1$;
   Easy to verify that for this cinstruction  of $ g$, it's from $ S$ to $ S$, it's scritly increasing and for any $ x$ from $ [n,n \plus{} 1)$, where $ n$ is nonnegative integer, $ g(n)$ is in $ [n,n \plus{} 1)$. Moreover, we have $ g(x \plus{} 1) > g(x) \plus{} 1$, for all $ x$ in $ S$. $ f$ is also from $ S$ to $ S$ and is strictly increasing as well.
    For any $ x$ in $ S$,  we have   $ f(g(g(x))) \equal{} g(g(x)) \plus{} 1 < g(x \plus{} 1) \equal{} g(f(x))$, as in condition. Hence, such a couple exists for $ S \equal{} \{a \minus{} \frac {1}{b}: a, b\in\mathbb{N}\}$.

Another solution to part ii)
Let $(a,b)$ represent $a-\frac{1}{b}$. The construction $f(a,b)=(2a,b), g(a,b)=(a,b+(a-1))$ works too. This is inspired by the fact that you require $f(x) > g^n(x)$ for all $n$, so $g$ should not make any "hops" in the $a$-value, and also by the intuitive fact that applying $f$ then $g$ should make the number bigger than applying $g$ then $f$.

(i) Because it is increasing, $f(x),g(x) \ge x$ and so $g(f(x))>f(g^2(x)) \ge g^2(x) \Rightarrow f(x)>g(x)$. Repeating this argument, $g(f(x))>f(g^2(x)) > g(g^2(x))=g^3(x) \Rightarrow f(x) > g^2(x)$, and, inductively, $f(x) > g^n(x)$ for any natural $n$. If $g(x) \neq x$ then $g(x) > x$, and $g(g(x))>g(x)$ because it is increasing and so inductively $g^n(x) > g^{n-1}(x)$ and so $f(x) > g^{f(x)}(x) \ge g^{f(x)-1}(x) +1 \ge ... \ge g(x)+(f(x)-1) \ge f(x)$, a contradiction. Then $g(x)=x$ for all $x$ and plugging in, $f(x)>f(x)$, a contradiction. They don't exist.

(ii) Notice that our set is basically equivalent to $\{wn+m : n\ge 0, m \ge 1 \}$, where $w$ is the first infinite ordinal number. Let $f(wn+m)=w(n+1)+m$, and $g(wn+m)=wn+(m+3^n)$, so that $g$ grows faster the bigger $n$ is. Then $f(g(g(wn+m))) = f(g(wn+m+3^n))=f(wn+m+2*3^n) = w(n+1)+m+2*3^n$ and $g(f(wn+m))=g(w(n+1)+m)=w(n+1)+m+3^{n+1}$ and so $ g(f(x))=w(n+1)+m+3^{n+1} > w(n+1)+m+2*3^n = f(g(g(wn+m)))$, and they satisfy.

[quote=LMat]Has anyone seen a smilier problem before at an earlier competition?[/quote]

No, I haven't.
That's an excellent problem, fresh and original. It's a pity that it did not get selected.

[hide="solution"]
Notation: $f^n(x)$ indicates applying function $f$ to $x$ a total of $n$ times.

$S=\mathbb{N}$: the answer is no.
Note that since $f,g$ are strictly increasing, $f(x)\ge x$.
Thus, $g(f(x)) > f(g(g(x))) > g(g(x))\implies f(x) > g(x)$.
Now I prove by induction that $f(x) > g^n(x)$. The base case is already done. Then, assume $f(x) > g^n(x)$; then $$g(f(x)) > f(g(g(x))) > g^{n+2}(x)\implies f(x) > g^{n+1}(x)$$ done.
If $g(x_0) \ge x_0+1$ for some $x_0$, then $f(x)\ge x+1$ for all $x\ge x_0$. But $f(x_0) > g^n(x_0)$ and the left side tends to infinity as $n\to \infty$, contradiction. Thus, $g(x)=x$ for all $x$.
But this means $f(x) < f(x)$ contradiction. Thus, there are no solutions.
-------------
$S = \{a-\dfrac{1}{b} : a,b\in\mathbb{N}\}$: the answer is yes.
Let $f(x)=x+1$. Now define a function $h(x)$ from $S\mapsto S$ satisfying that the output is the smallest value in $S$ strictly greater than $x$.
We let $g(x)=h^{2^{\lfloor x\rfloor}-1}(x)$.
To show that this works:
First note the property $h(x)+1=h(x+1)$ since the set $S$ is obviously periodic with period 1.
$f(g(g(x))=f(h^{2^{\lfloor x\rfloor +1}-2}(x)) = h^{2^{\lfloor x\rfloor +1}-2}(x)+1$
$g(f(x))=g(x+1)=h^{2^{\lfloor x+1\rfloor}-1}(x+1)=h^{2^{\lfloor x\rfloor+1}-1}(x)+1$
And clearly $h^{2^{\lfloor x\rfloor+1}-1}(x)+1 > h^{2^{\lfloor x\rfloor +1}-2}(x)+1$ so the construction works. $\Box$
[/hide]

Nice problem! Here's my solution:

[b](i)[/b] We claim that Spanish Couples cease to exist [i]naturally[/i] (pun intended!). FTSOC assume there is such a Spanish Couple $(f,g)$. The crucial observation is that any strictly increasing function $h: \mathbb{N} \mapsto \mathbb{N}$ satisfies $h(x) \geq x$ (since otherwise the smaller values have to map into an even smaller set, and so two of them must coincide, which is not possible). Using this [i]deep fact[/i], we propose the following Lemma-

[b]LEMMA[/b] Given a positive integer $k$, we have $f(x)>g^k(x)$ for all $x \in \mathbb{N}$.

[u][i]Proof of Lemma[/i][/u] We proceed by induction on $k \geq 1$. Using the [i]deep fact[/i], we get $$g(g(x)) \leq f(g(g(x)))<g(f(x)) \Rightarrow g(x)<f(x)$$
proving the base case. Now, suppose the result is true for some $k$. Then, since $f(x)>g^k(x)$ for all $x \in \mathbb{N}$, so we have $$g(f(x))>f(g(g(x)))>g^{k+2}(x) \Rightarrow f(x)>g^{k+1}(x)$$
competing the induction step. $\Box$
-----

Return to the problem at hand. If $g=\text{id}$, then the given condition translates to $f(x)<f(x)$, which is not possible. So there exists some $x_0 \in \mathbb{N}$ satisfying $g(x_0)>x_0$. Let $f(x_0)-x_0=m$, where $m \geq 0$. Applying the Lemma for $k=m+1$, we get $$f(x_0)>g^{m+1}(x_0) \geq g^m(x_0)+1 \geq g^{m-1}(x_0)+2 \geq \dots \geq g(x_0)+m$$
But, since $f(x_0)=x_0+m$, so the above inequality gives $x_0>g(x_0)$, a contradiction. Thus, all Spanish Couples are [i]unnatural[/i].

[b](ii)[/b] For any $a,b \in \mathbb{N}$, and some fixed positive integer $n>1$, let $$f \left(a-\frac{1}{b} \right)=na-\frac{1}{b} \text{ and } g \left(a-\frac{1}{b} \right)=a-\frac{1}{b+\rho(a)}$$
where $\rho:\mathbb{N} \mapsto \mathbb{N}$ is some function. It's easy to see that both $f,g$ are strictly increasing. Then $$f \left(g \left(g \left(a-\frac{1}{b} \right) \right) \right)=na-\frac{1}{b+2\rho(a)}$$
$$\text{and}$$
$$g \left(f \left(a-\frac{1}{b} \right) \right)=na-\frac{1}{b+\rho(na)}$$
So we want $$na-\frac{1}{b+2\rho(a)}<na-\frac{1}{b+\rho(na)} \iff \rho(na)>2 \rho(a)$$
So our aim is to show the existence of such a function $\rho$ for some $n$. But taking any $n>2$ and $\rho(a)=a$ does the deed. $\blacksquare$

[quote=April]Let $ S\subseteq\mathbb{R}$ be a set of real numbers. We say that a pair $ (f, g)$ of functions from $ S$ into $ S$ is a [i]Spanish Couple[/i] on $ S$, if they satisfy the following conditions:
(i) Both functions are strictly increasing, i.e. $ f(x) < f(y)$ and $ g(x) < g(y)$ for all $ x$, $ y\in S$ with $ x < y$;

(ii) The inequality $ f\left(g\left(g\left(x\right)\right)\right) < g\left(f\left(x\right)\right)$ holds for all $ x\in S$.

Decide whether there exists a Spanish Couple [list][*] on the set $ S \equal{} \mathbb{N}$ of positive integers; [*] on the set $ S \equal{} \{a \minus{} \frac {1}{b}: a, b\in\mathbb{N}\}$[/list]

[i]Proposed by Hans Zantema, Netherlands[/i][/quote]
Solved with [b]Rg230403[/b] and [b]MathPassionForever[/b]  :love:
(a)    We claim that no [i]spanish couples[/i] exist if $S=\mathbb{N}$ .Assume to the contrary that there are functions $(f,g)$ satisfying the assertion. Then note that since $f,g$ are increasing functions on $\mathbb{N}$ so $f(x)\geq x$ and $g(x)\geq x$

[b]Claim[/b]  : $f(x) >  g^k(x)$ for all $k\geq 1$
[i]Proof[/i] Since $g(f(x))>f(g(g(x)))\geq g(g(x))\Longleftrightarrow f(x) > g(x)$ .  Plugging back we have $$g(f(x))>f(g(g(x)))>g(g(g(x)))\implies f(x)>g^2(x)$$
and now a simple induction proves the claim.$\square$

Now if there exists a $x\in\mathbb{N}$ such that $g(x)>x$ and let  $\chi=f(x)-x$.Thus $$f(x)>g^{x}(x)\geq 1+g^{\chi-1}(x)\geq 2+g^{\chi-2}(x)\cdots > \chi+x =f(x)$$ a contradiction.$\square$

(b)The answer is Yes for this case.The following construction works:- $f\left(a-\dfrac{1}{b}\right)=a+1-\dfrac{1}{b} $ ;  $ g\left(a-\dfrac{1}{b}\right)=a-\dfrac{1}{b+3^a}$.Indeed $$f(g(g(x)))=f\left(g\left(g\left(a-\dfrac{1}{b}\right)\right)\right)=a+1-\dfrac{1}{b+2\cdot 3^a}<a+1-\dfrac{1}{b+3^{a+1}}=g\left(f\left(a-\dfrac{1}{b}\right)\right)=g(f(x))$$
so we are done.$\blacksquare$

i:
The answer is [b]no[/b].
Obviously if $g,f\ge \text{id}$. If $g(g(x))\le g(f(x))$ we immediately die, and therefore $f(x)>g(x)$. Now, we claim that $f(x)>g^n(x)$ for all natural $n$ by induction.
The base case, $n=1$, is proven. For the inductive step assume the hypothesis true for $n=N$; notice that $g(f(x))>g^{N+2}(x)$ because $f(g^2(x))>g^{N+2}(x)$.
If $g$ is not the identity, we die here. Otherwise, we just get $f(x)<f(x)$ which is false.
ii.
The answer is [b]yes[/b].
Consider $f(a-\frac{1}{b})=a-\frac{1}{3b},g(a-\frac{1}{b})=a+187b-\frac{1}{b}$. The LHS becomes $a+374b-\frac{1}{3b}$, while the RHS becomes $a+561b-\frac{1}{3b}$.

[hide = Part A]
The answer is [i]no[/i]. Firstly, observe that $f(x) \geq x$ and $g(x) \geq x$ for every $x$. Equality holds for all $x$ iff $f(x) = x \forall x$ or $g(x) = x \forall x$, and we easily see that both of them are impossible.  Hence $f(x) > x$ and $g(x) > x$ for all $x$. Henceforth, denote substituting $x$ in the  second condition of the problem by $P(x)$.

[hide = Claim]
$f(x) > g(x) ~~ \forall x \in \mathbb{N}$.
[/hide]
[hide = Proof]
Suppose we had $f(x) \leq g(x)$ for some $x$. Then $P(x)$ gives $f(g(g(x)) < g(f(x))$, but by the first condition and our assumption, $g(f(x)) < g(g(x))$, so $f(g(g(x))) < g(g(x))$, a contradiction. Thus, $f(x) > g(x) ~~ \forall x \in \mathbb{N}$.
[/hide]

[hide = Main problem]
Denote by $g^k(x)$ the function $g$ iterated $k$ times. We shall now show that $g^n(x) < f(x) ~~ \forall x$ for any natural $n$, and since $g(y) > y ~~ \forall y$, this will be a contradiction, since $g^n(x)$ will be unbounded while $f(x)$ will be a constant. We proceed by induction. We know that $g(x) < f(x)$ by our claim, so our base case is true. Suppose $g^n(x) < f(x)$ for some $n$ and all $x$ (assume further its true for all $k \leq n$ as well). We will show that $g^{n+1}(x) < f(x)$. Suppose the contrary, that $f(x) \leq g^{n+1}(x)$. Then $P(x)$ tells us that $g^{n+2}(x) < f(g(g(x))) < g(f(x)) < g^{n+1}(x)$, a contradiction (the first inequality comes from $g^n(x) < f(x)$ and the last inequality comes from the same). Hence $g^n(x) < f(x)$ for any natural $n$, which is impossible (unless $g(x) = x$ always, which doesn't give us any valid solution).

Therefore, there is no Spanish Couple defined on the set of natural numbers.
[/hide]
[/hide]

[hide = Part B]
The answer is [i]yes[/i]. We shall list out the set $S$ in a matrix form and find a construction.
$S = \begin{Bmatrix}
0 & \tfrac{1}{2} & \tfrac{2}{3}  \cdots \\
1 & 1+\tfrac{1}{2} & 1+\tfrac{2}{3}  \cdots \\
2 & 2+\tfrac{1}{2} & 2+\tfrac{2}{3}  \cdots
\end{Bmatrix}$
In every row, the elements between two successive natural numbers are arranged in increasing order from left to right. denote the number in the $i$th column and $j$th row by $S(i, j)$. Observe that the Spanish Couple defined by $g((S(i, j)) = S(i + 2^{2(j-1)}, j)$ and $f(S(i, j)) = S(i, j+1)$ works.
[/hide]

[hide=Solution]
(a):

Note that $f(n) \geq n$ and $g(n) \geq n$ for all $n \in \mathbb{N}$ since both are increasing.

If there exists a $t \in \mathbb{N}$ such that $f(t) \leq g(t)$, then we have $g(g(t)) \leq f(g(g(t)) < g(f(t)) \leq g(g(t))$, contradiction.

So $f(x) > g(x)$ for all $x \in \mathbb{N}$. We will prove by induction that $f(x) > g^n(x)$ holds for all $x,n \in \mathbb{N}$.

Our claim is true for $n = 1$. Suppose it is true for $n$. Then by induction hypothesis, $$g^{n+2}(x) < f(g(g(x))) < g(f(x)) \implies f(x) > g^{n+1}(x)$$ because $g$ is increasing, so our claim is true for all $n \in \mathbb{N}$.

If there exists a $t \in \mathbb{N}$ for which $g(t) > t$, then $g(m) \geq m+1$ for all $m \geq t$. So taking $n$ large enough in $f(t) = g^n(t)$ gives a contradiction.
So, combining this with $g(t) \geq t$, this means $g(x) = x \ \forall x \in \mathbb{N}$, but this clearly doesn't satisfy the given condition.

(b):

We will show the answer is yes. Let $f(a - 1/b) = a + 1 - 1/b$ and $g(a - 1/b) = a - \frac{1}{b + 3^a}$.

Then clearly $f$ and $g$ are increasing and also, $$a + 1 - \frac{1}{b + 2\cdot 3^a} = f(g(g(a-1/b))) < g(f(x)) = a + 1 - \frac{1}{b + 3^{a+1}} \iff 3^{a+1} > 2\cdot 3^a$$, so our second condition is also satisfied, thus we are done. $\square$
[/hide]

Very original problem as pointed out by #6 and #7. Here is a solution with some motivation.

As always, let $g^n(x) = g^{n-1}(g(x))$ for all $n \in \mathbb{N}$. \\
[hide=Part 1)]
$\textbf{Claim:}$ There is no Spanish Couple for $S= \mathbb{N}$, i.e, the answer is no. \\

$\textbf{Proof)}$ \\
Assume without loss of generality that there are two increasing functions $f,g$ from the positive integers to the positive integers such that for all $x \in \mathbb{N}$, $f(g(g(x)) < g(f(x))$. \\

$\textbf{Lemma 1:}$ $f(x), g(x) \geq x$ for all $x \in \mathbb{N}$ \\
$\textbf{Proof)}$ \\
This holds for all increasing functions from the positive integers to the positive integers, in fact, this proof will also carry over to when $S = \{a - \frac{1}{b} | a,b \in \mathbb{N} \}$ but is not necessary and thus will not be included. \\

We will induct on $x$ after noticing that $f(1) \geq 1$, if $f(x-1) \geq x-1$, then $f(x) > f(x-1) \geq x-1$ means that $f(x) \geq x$, completing the inductive step. $\blacksquare$ \\

$\textbf{Lemma 2: }$ $f(x)>g(x)$ for all $x \in \mathbb{N} $\\
$\textbf{Proof)}$ \\
The following inequality which can be derived by $\textbf{Lemma 1}$ immediately implies the desired result as $f,g$ are strictly increasing functions.\\
$$g(f(x)) > f(g(g(x))) \geq g(g(x))$$

$\textbf{Lemma 3}$ $f(x) > g^n(x)$ for all $x \in \mathbb{N}$ \\
$\textbf{Proof)}$ \\
We will induct on $n$ with the base case being $\textbf{Lemma 1}$. Assume that for some $k \in \mathbb{N}$ and all $x \in \mathbb{N}$, $f(x) > g^k(x)$, then we have the following inequality that immediately concludes the inductive step as $g$ is increasing. \\
$$g(f(x)) > f(g(g(x)) > g^k(g(g(x)) = g(g^{k+1}(x))$$ meaning that $f(x) > g^{k+1}(x)$. $\blacksquare$ \\

$\textbf{Lemma 4:}$ $g(x) = x$ for all $x \in \mathbb{N}$ \\
$\textbf{Proof)}$ \\
Firstly, notice that $g$ is injective as it is increasing and thus if $g^n(x) = g^{n-1}(x)$ for some $n \in \mathbb{N}$, then $g(x) = x$, assuming that $g(x) \neq x$, we have that $g^n(x) \geq g^{n-1}(x)+1$ meaning that $f(x) > g^{m}(x) \geq m+g(x)$ for all $m \in \mathbb{N}$ which is a contradiction. $\blacksquare$ \\

We are able to conclude immediately as $f(x) = g(f(x)) > f(g(g(x))) = f(x)$ which does not hold. $\blacksquare$ \\

[/hide]

$\textbf{Part 2)}$ \\
[hide=Motivation: Infinite Chains]
We are in fact able to conclude all the previous facts about $g^n(x) < f(x)$ for all $n \in \mathbb{N}$ when $S = \{a- \frac{1}{b} | a,b \in \mathbb{N}\}$ as well but we will not be needing this as we will in fact construct a solution. \\
Firstly, it makes sense to take $f$ to be a linear, so let us set $f(x) = x+1$ for all $x \in S$. \\
We will look fix some $a \in \mathbb{N}$ and then look at the sequence $a-\frac{1}{b}$ and build $g$ so that each number is mapped forward by some specific amount in the chain formed by $a-\frac{1}{b}, a-\frac{1}{b+1}, \cdots$, the reason that this will work is that each of the sequences created by some $a$ is independent of all other sequences which was, of course, not the case when $S = \mathbb{N}$, we can then set $g(a-\frac{1}{b}) = a- \frac{1}{u(x)}$ for some $u: \mathbb{N} \to \mathbb{N}$, we can indeed take it to be any exponential other than the powers of two, but there are clearly other functions that also work (such functions can simply be defined recursively to work, for example).

Note: I thought this problem was quite similar to ELMO Shortlist 2018/A1 for the infinite chain idea, which I actually completed between this solution and the write-up (this solution is from a month ago).  I won't comment more on the problem for the sake of not spoiling anything but I definitely recommend people to try it.
[/hide]

Let $f(x) = x+1$ and $g(a-\frac{1}{b}) = a-\frac{1}{b+3^a}$, we can indeed verify that for all $a,b \in \mathbb{N}$ $$g(f(a-\frac{1}{b})) > a+1- \frac{1}{b+3^{a+1}}> a+1-\frac{1}{b+2 \cdot 3^a} = f(g(g(a-\frac{1}{b})))$$ meaning that $(f,g)$ are a Spanish pair for $S = \{a- \frac{1}{b}|a,b \in \mathbb{N} \}$. $\blacksquare$ \\

When only positive integers are in question, we have $f(x)\ge x.$ Thus, $g(g(x))\le f(g(g(x)))<g(f(x))$ which implies $g(x)<f(x).$ Now, $f(g(g(x)))<g(f(x))<f(f(x))$ so $g(g(x))<f(x).$
\\$~$\\
If $g^n(x)<f(x)$, then $g^n(g^2(x))<f(g(g(x)))<g(f(x))$ implies $g^{n+1}(x)<f(x),$ absurd. Thus, $f(x)>g^n(x)$ for all $x.$ If $g(k)>k$, then $g^n(k)>n+k$ but increasing $n$ will eventually make $f(x)\le g^n(x).$ Thus, $g(x)=x$ which implies $f(x)<f(x)$, impossible.
\\$~$\\
Let $f(x)=x+2\lceil x\rceil = 3a-\frac{1}{b}$ and $g(x)=a-\frac{1}{a+b}$ works.

For the first part, repeatedly substituting $x=g(g(x))$ and noting that $f(x)\ge x$ we obtain
\[g^{2k}(x)\le f(g^{2k}(x))<g^k(f(x))\implies g^k(x)<f(x)\] for all $k\ge 1$. Therefore we can choose arbitrarily large $x$ where $g(x)=x$ which implies $g(x)=x$ for all $x$, a contradiction.

For the second part, take $f\left(a-\frac{1}{b}\right)=(a+1)-\frac{1}{b}$ and $g\left(a-\frac{1}{b}\right)=a-\frac{1}{b+(2^a-1)}$.

[hide=Solution for a)] We are given that $f(x)>f(y) \iff x>y$ and $f(x) \geq x$ for all $x$ and the same things hold for $g$. We have that $g(f(x))>f(g(g(x)) \geq g(g(x))$, so $f(x)>g(x)$ for all $x$. Thus, $f(f(x))>g(f(x))>f(g(g(x)))$, so $f(x)>g(g(x))$ for all $x$. If we have $f(x)>g^m(x)$, then $g(f(x)) >f(g(g(x)))>g^{m+2}(x)$, so $f(x)>g^{m+1}(x)$, so by induction $f(x)>g^n(x)$ for all $n \in \mathbb{N}$. However, obviously $g$ can't have fixed points, so $g(x)\geq x+1$ for all $x$ and thus by induction $f(x)>g^n(x)>x+n$. Fixing $x$ and taking large $n$ now gives contradiction, so such a pair of functions doesn't exist.


Every positive integer $k$ has a unique factorial base expansion $(f_1,f_2,f_3,\ldots,f_m),$ meaning that \[ k=1!\cdot f_1+2!\cdot f_2+3!\cdot f_3+\cdots+m!\cdot f_m,  \] where each $f_i$ is an integer, $0\le f_i\le i,$ and $0<f_m.$  Given that $(f_1,f_2,f_3,\ldots,f_j)$ is the factorial base expansion of $16!-32!+48!-64!+\cdots+1968!-1984!+2000!,$ find the value of $f_1-f_2+f_3-f_4+\cdots+(-1)^{j+1}f_j.$

[quote=maxo]Sorry for the revive, but can anyone explain how K81o7 went from the first equation to the 2nd equation?[/quote]

bumpp


algebra
polynomial
induction
system of equations

The sum of the first $ n$ squares is equal to $ \frac {n(n \plus{} 1)(2n \plus{} 1)}{6}$

Plug in $ 2009$ to get $ 2009(335)(4019) \equal{} 2704847285$

If you didn't know that formula before, you can get it like this:

Let $ f(x) \equal{} \sum_{i \equal{} 1}^xi^2$
[See picture now]

Seeing as you need 3 to take finite differences three times before you get a constant, this will be a third degree polynomial. (And yes, you should technically use more initial points, but I skimped a bit for size, and because it's clear that it works)

So now it's just a point of finding a third degree polynomial that contains $ (0,0),(1,1),(2,5),(3,14)$
Let the polynomial be of the form $ ax^3\plus{}bx^2\plus{}cx\plus{}d$
Clearly $ d\equal{}0$ (since $ f(0)\equal{}0$)

So now you just solve the system of equations:
$ a\plus{}b\plus{}c\equal{}1$ (1)
$ 8a\plus{}4b\plus{}2c\equal{}5$ (2)
$ 27a\plus{}9b\plus{}3c\equal{}14$ (3)

$ c\equal{}1\minus{}a\minus{}b$ (1)
$ 8a\plus{}4b\plus{}2\minus{}2a\minus{}2b\equal{}5$ (2)
$ 2b\equal{}3\minus{}6a$
$ b\equal{}\frac{3}{2}\minus{}3a$
Putting this into (3):
$ 27a\plus{}9\left (\frac{3}{2}\minus{}3a\right )\plus{}3\left [1\minus{}a\minus{}\left (\frac{3}{2}\minus{}3a\right )\right ]\equal{}14$
$ 27a\minus{}27a\minus{}3a\plus{}9a\plus{}\frac{27}{2}\plus{}3\minus{}\frac{9}{2}\equal{}14$
$ 6a\plus{}12\equal{}14$
$ a\equal{}\frac{1}{3}$
$ b\equal{}\frac{1}{2}$
$ c\equal{}\frac{1}{6}$

$ \frac{1}{3}x^3\plus{}\frac{1}{2}x^2\plus{}\frac{1}{6}x\equal{}\frac{x}{6}(2x^2\plus{}3x\plus{}1)\equal{}\frac{x(x\plus{}1)(2x\plus{}1)}{6}$

Please, teach me more detalhed, I don't understand your logic.

To prove the formula $ \frac{n(n\plus{}1)(2n\plus{}1)}{6}\equal{}1^2\plus{}2^2\plus{}...\plus{}n^2$ can use induction.

Ok, but If I'd like to calculate this example:

S = 1+3+5+7+9 ... +2009 ?

and

S1 = 1+2+3+4+5+6+7+8+9 ... +2009 ?

How to use this formula  ?

If this is what you mean: The sum of odd no.s $ 1\plus{}3\plus{}...\plus{}(2k\plus{}1)\equal{}(k\plus{}1)^2$ because the sums of consecutive odds with first term 1 will be $ (k\plus{}1)^2$ (prove by induction if you are unsure). $ S_1\equal{}2009(2010)/2$ (again prove $ 1\plus{}2\plus{}...\plus{}k\equal{}k(k\plus{}1)/2$ if you are uncertain).

Thanks Bengal, but S = (k+1)², then, S = 4040100 or 1010025 , and how to find this ?

Prove by induction: http://en.wikipedia.org/wiki/Mathematical_induction.

Thanks Bengal. I understand now. I'm if I bored you. Thanks. I know now ;)

[quote="luiseduardo"]Numerical value of the sum:

S = 1² + 2² + 3² + 4² + 5² ... +2008² + 2009²

How to do ? (Please, teach me more detalhed possible)

Thanks (my answer was 2704847285)[/quote]

luiseduardo,

what you should have SHOWN/TYPED was what you did to get 2704847285,
FIRST, before asking for others to post and explain how they did it, especially
because your answer agrees with the sum of n squares formula's answer.


algebra
polynomial
probability and stats

In a certain type of auction, the winning bidder is the person with the lowest unique bid. Suppose that $ n$ is a positive integer and there are $ 2n\minus{}1$ people bidding in this sort of auction. Bids must be positive integers, and bids are closed (i.e. no one knows what anyone else has done). Also assume that there's no collusion.

1. Suppose that everyone believes the item is worth $ n$, so their return from winning the auction with bid $ b$ is $ n\minus{}b$. In this case, everyone would have the same strategy. The strategy is to pick a bid $ b$ at random from $ [1, n]$. What distribution maximizes expected return?

2. Now suppose that each person has a value $ v_i$ which is uniform on $ [1, n]$. Can we find an equilibrium strategy now?

3. In each case, what is the expected sale price? Compare this to the expected sale price in other standard auction forms (Dutch auction / first price sealed bid = $ 1\plus{}\frac{4(n\minus{}1)^3}{(2n\minus{}1)^2}$ and button auction / second price sealed bid = $ 1\plus{}\frac{(n\minus{}1)(2n\minus{}3)}{2n\minus{}1}$ [hopefully I'm right about those; they're reasonable things to compare to at least]).

I apologize to anyone who spent much time on this. I was hoping there'd be some nice way to explicitly find the distribution; as far as I can tell, though, all you can do is write out a huge polynomial and try to maximize it. It's straightforward in the sense of procedure but for $ n > 2$ I don't think the solutions are easily expressible.

It's an interesting auction form because the expected sale price ought to be pretty low -- I'd still be interested if anyone has an idea of how to estimate the sale price in terms of $ n$. In most auctions the expected sale price is pretty close to the maximum of the values of placed on it by the buyers, but this is one of the forms that's not like that. This might actually be more profitable for sellers, though, because buyers will be willing to pay a significant price to place bids when their return for bidding is that high. (It's a slightly diluted and slightly less random version of a lottery, essentially.)


geometry
circumcircle
trapezoid
power of a point
radical axis

[size=117][color=darkblue][b]I present here a nice problem for which maybe you'll find an its extension.[/b][/color][/size]

[quote="Crux mathematicorum with Mathematical Mayhem,1991,Nr.8/vol 17,1671"][color=darkred]A right triangle $ ABC$ with right angle at $ A$ is inscribed in a circle $ \Gamma$ . Let $ M$ , $ N$ be midpoints of $ AB$ , $ AC$ and let $ P$ , $ Q$ be the points of intersection of the line $ MN$ with $ \Gamma$ . Let $ D$ , $ E$ be the points where $ AB$ , $ AC$ are tangent to the incircle. Prove that $ D$ , $ E$ , $ P$ , $ Q$ are concyclic.[/color][/quote]
[size=150][color=darkred][b]Happy new year ![/b][/color][/size]

[color=darkblue]I have a [b]short metrical proof[/b] and I wish, if is possibly, a [b]synthetical proof[/b] ![/color]

[color=darkred]Denote: the circumcircle $ \Gamma = \mathcal C(O,R)$ ; the incircle $ w = \mathcal C(I,r)$ of an $A$-right $\triangle  ABC\ ;$ the midpoints $ M$ , $ N$ of $ [AB]$ , $ [AC]$ respectively $;$

$ \{P,Q\} = MN\cap \Gamma$ so that $ M\in (PN)$ , $ N\in (MQ)$ ; $ D\in (AB)\cap w$ , $ E\in (AC)\cap w$ . Prove that $\{D,E,P,Q\}$ are concyclically.[/color]

[color=darkblue][b]Proof (metric).[/b] Observe that the bisectors $ [DE]$ , $ [PQ]$ meet $ \Gamma$ in the same $ A'$ . Then $\{D,E,P,Q\}$ are concyclically $\iff \boxed {A'P = A'D}$ and

in this case these points belong to the circle with the center $ A'$ . I'll ascertain $ A'P$ and $ A'D$ ! Denote the length $ h$ of the $ A$-altitude of $ \triangle ABC$ .[/color]

[color=darkred][b][u] The first method[/u][/b] (use only the [b]theorem of cathetus[/b] and the [b]Pythagoras' theorem[/b]).[/color]

$ 1\blacktriangleright$[color=darkblue]Denote the diameter $ [A'A_1]$ in the circle $ \Gamma$ and $ R\in A'A_1$ , $ PR\perp A'A_1$ . Observe that

$ A'P^2 = A'A_1\cdot A'R =$ $ a(\frac a2 + \frac h2) =$ $ a(\frac a2 + \frac {bc}{2a})$ , i.e. $ \boxed {A'P = \sqrt {\frac {a^2 + bc}{2}}}\ .$[/color]
[color=darkblue]

$ 2\blacktriangleright$ Denote the point $ B_1$ for which the line $ BC$ doesn't separate the points $ B_1$, $ A$ and

$ B_1B\perp BC$ , $ B_1B = r$ . Observe that $ \triangle B_1BA'\equiv\triangle DIA'$ $ \implies$ $ \boxed {A'B_1 = A'D}$ .

Prove easily that $ A'B_1^2 = (\frac a2)^2 + (\frac a2 + r)^^2$ . Thus, $ r = p - a$ $ \implies$

$ A'B_1^2 = \frac 14\cdot[a^2 + (b + c)^2]$ $ \implies$ $ A'B_1 = \sqrt {\frac {a^2 + bc}{2}}$ $ \implies$ $ \boxed {A'D = \sqrt {\frac {a^2 + bc}{2}}}\ .$  [/color]

[color=darkblue]$ \blacksquare$ [b]In conclusion, $ A'P = A'D$ , i.e. $ \{\ D\ ,\ E\ ,\ P\ ,\ Q\ ,\ B_1\ \}\subset \mathcal C(A')\ .$[/b][/color]

[color=darkred][b][u]The second method[/u][/b] (use the [b] Ptolemaeus'[/b] and the [b]generalized Pythagoras' theorems[/b]).[/color]

$ 1\blacktriangleright$[color=darkblue] Observe that $ \|\begin{array}{c} PB^2 + PC^2 = a^2 \\
 \\
PB\cdot PC = \frac {ah}{2}=\frac {bc}{2}\end{array}\|$ $ \implies$ $ PB + PC = \sqrt {a^2 + bc}$ .

Apply the [b]Ptolemaeus' theorem[/b] to the quadrilateral $ BPCA'$ :

$ A'P\cdot BC = BA'\cdot (PB + PC)$ $ \implies$ $ \boxed {A'P = \sqrt {\frac {a^2 + bc}{2}}}$ .[/color]

[color=darkblue]$ 2\blacktriangleright$ Apply the [b]Ptolemaeus' theorem[/b] to the quadrilateral $ BACA'$ and obtain

$ AA' = \frac {\sqrt 2}{2}\cdot (b + c)$ . Apply the [b]generalized Pythagoras' theorem[/b] :

$ A'D^2 = AD^2 + A'A^2 - \sqrt 2\cdot AD\cdot AA' =$ $ (p - a)^2 + \frac 12\cdot (b + c)^2 - (p - a)(b + c)\ .$

Thus, $ A'D^2 = \frac 12\cdot (b + c)^2 - p(p - a) =$ $ \frac 12\cdot (b + c)^2 - \frac {bc}{2}\implies$ $ \boxed {A'D = \sqrt {\frac {a^2 + bc}{2}}}$ .[/color]

[color=darkblue]$ \blacksquare$ [b]In conclusion, $ A'P = A'D$ , i.e. $ \{\ D\ ,\ E\ ,\ P\ ,\ Q\ \}\subset \mathcal C(A')\ .$[/b][/color]

Here are some observations that may lead to a synthetic solution.

Notation: Let $ ABC$ be a right triangle with circumcircle $ O$. Let $ N$ and $ P$ be the intersections of the $ A$-midline of $ \triangle ABC$ with $ O$ so $ N$ is opposite $ B$ and $ P$ is opposite $ C$. Let the incircle touch at $ D$, $ E$, and $ F$. So $ AD$, $ BE$, $ CF$ are concurrent. Let $ NP$ intersect $ DE$ and $ DF$ at $ F'$ and $ E'$, respectively.

We can show that $ AEF'IE'F$ is cyclic and if we show that $ \angle PFD\equal{}\angle NED$, then we are done. Note that $ F'$ and $ E'$ lie on the angle bisectors of angle $ B$ and $ C$, respectively. The points $ E'$, $ F'$ are well known...

Dear Mathlinkers,
you can see my synthetic proof on
http://perso.orange.fr/jl.ayme

contenu...volume 1... Quelques théorèmes oubliés.

Sincerely
Jean-Louis

Yet another proof given by my son.
See the attached, for the notation (quite different than the ones in the given problem)

Let $D$ be the midpoint of the arc $\stackrel{\frown}{BC}$ opposite to $A$, $R',P'$ on $AB, AC$ so that triangles $RDR', PDP'$ be $D-$isosceles, $G,H$ be midpoints of $RR', PP'$ respectively, $E,F$ midpoints of $AB, AC$ respectively and $M,N$ the intersections with the circle $\odot(ABC)$ of $EF$.
$AGDH$ is a square, with $AG=\frac{b+c}{2}$ (from $\triangle BGD\cong\triangle CHD$) and $AR=s-a$, with $2s=a+b+c$, where $a,b,c$ are the sides of $\triangle ABC$. Consequently $ER=EA-AR=\frac{c}{2}-(s-a)=\frac{a-b}{2}, ER'=AR'-AE=$  $AR+2RG-AE=\frac{a+b}{2}$, hence $ER\cdot ER'=AE\cdot BE$, so $E$ lies onto the radical axis of the circles $\odot(ABC),\odot(RR'P'P)$ - $PRR'P'$ is an isosceles trapezoid, hence cyclic. In a similar way $F$ lies onto the same axis, i.e. $MN$ is this radical axis, so $MNPR$ is, indeed cyclic.

Best regards,
sunken rock


geometry
rectangle
trapezoid
analytic geometry
graphing lines
slope
3D geometry

I have a 8*8 grid.

I cut it into a 3*8 rectangle and a 5*8 rectangle

The 3*8 rectangle I cut diagonally from the corners into 2 equivalent triangles

The 5*8 rectangle cut into 2 trapezoids by cuting a diagonal line beetween the points 3 units from the left side on top and 3 units from the right side on the bottom

you should now have 2 trapezoids and 2 triangles.

arrange them so you have a 5*13 rectangle.

whats wrong with the area????!!!! :o

[hide]the answer lies in the fibbonaci #s. if you square the middle # of a chain of 3 consecutive fibbonaci (8) it will be either one more or one less than the 2 side #s 13&5. The fibbonaci #s are a chain where one # added to the next number equals the following #.Ex 0,1,1,2,5,8,13,21,34,55.....[/hide]

[hide="another explanation?"]
the two diagonals have different slope, so they don't come together perfectly.  It's very close, but not quite.
[/hide]

Notice that 8 is a perfect cube and a Fibonacci number.  8^2+1=65 is also factorable into 5*13.  the two Fibonacci numbers next to 8 are 5 and 13, so their product is 65 and the square of 8 is 64.


in bag C there are exactly 4 red, 4 blue, and 4 white marbles. in bag D there are exactly 4 red, 4 blue, and 4 white marbles. bob blindly draws the largest possible number of marbles from bag C so that he is positive there is at least one marble of each color left in bag C. he then places the drawn marbles in bag D. then bob blindly draws the smallest possible number of marbles from bag D so that when he places those drawn marbles in bag C he is positive there are at least 2 marbles of each color in bag C. after bob's blind draw from bag D, how many marbles are left in bag D?

i got an answer of
[hide]12[/hide]

I think the answer should be:
[hide]6.  He can only take 3 from bag C and still be certain that there are at least one of each color in it.  Suppose he takes 3 whites.  Then bag D has 4 red 4 blue and 7 white.  To be absolutely certain that there will be 2 colors of each after putting marbles back in C, assume the worst case.  Bag C needs only one more white to satisfy this condition.  Suppose he draws the 4 red and 4 blue from D. Then all thats left in D is 7 whites, he needs to draw one more from D to be certain there are two of each color in C. [/hide]

A twist to the problem:
Suppose it is given that Bob draws three of the same color from bag C and places them in bag D.  Upon drawing 9 marbles from bag D what is the probability that the remaining marbles in bag D are all the same color?

I agree with illcrowflu's answer.

As for the twist:
[hide]
If he adds 3 of one color to bag D, it now has 7 of one color, 4 of a 2nd color, and 4 of a 3rd color. In order to draw 9 marbles and have a single color remaining, he must draw 8 marbles from the 2nd and 3rd color and 1 marble from the 1st color.
There are 7 ways to draw the 1 and 1 way to draw the 8. This makes 7*1=7 ways to have a single color remaining.
There are 15 nCr 9 = 5005 ways to choose any 9 marbles.
Thus, the probability is 7/5005 or 1/715.[/hide]


trigonometry
inequalities solved
inequalities

Determine the maximum value of

  a(1-b^2)(1-c^2) + b(1-c^2)(1-a^2) + c(1-a^2)(1-b^2)

subject to the conditions ab+bc+ca=1 and a,b,c \geq 0

Crux * year * month * problem *

I really think that I have already solved this one.

other solution : Denote $a=\tan{\frac{X}{2}},b=\tan{\frac{Y}{2}},c=\tan{\frac{Z}{2}}$, where $X,Y,Z$ are three angles of a triangle.


real analysis
function
analytic geometry
inequalities
LaTeX
topology
real analysis unsolved

Let $ m^{*}$ denote Lebesgue outer measure on $ \mathbb{R}$. Suppose $ f: \mathbb{R} \rightarrow \mathbb{R}$ satisfies $ \left| f(x) \minus{} f(y) \right| \leq C\left| x \minus{} y \right|$ for all $ x,y \in \mathbb{R}$ and $ 0 < C < \infty$. Prove that

(a) $ m^{*}f(A) \leq C\cdot m^{*}A$ for every $ A \subset \mathbb{R}$.
(b) If $ A \subset \mathbb{R}$ is a Lebesgue measurable set, then so is $ f(A)$.

Do you mean uniform  Lipschitz?
What is the precise definition for  the  Lebesgue outer measure  ?I couldn’t find a clear definition in books I have ever studied .
I think this theorem may be useful .” Every none empty set in R such as S can be exposed as a countable  union of disjoint component intervals of S”

[quote="christ"]What is the precise definition for  the  Lebesgue outer measure  ?I couldn’t find a clear definition in books I have ever studied .”[/quote]

Define the volume ($ \text{vol}$) of a box in $ \mathbb{R}^d$ with sides parallel to the (usual) coordinate axes to be the product of its sides, and then the definition of the outer measure $ m^*$ for a set $ \Omega\subset\mathbb{R}^d$ is just

\[ m^*(\Omega) \triangleq \inf \left\{\sum_i \text{vol}(A_i) \ : A_i\subset\mathbb{R}^d\text{ are boxes , }\bigcup_i A_i \supset \Omega\right\}
\]

[quote="christ"]Do you mean uniform  Lipschitz?[/quote]
I mean Lipschitz continuous.

Regarding the uniform Lipschitz condition f is continuous on R .
Ii ’s  are component  intervals of A .
A= U Ii            f (A) = f(U Ii  ) =  U f(Ii  )    (i=1 to infinity )
     Let’s  suppose that    Ii  = (ai ,bi)   such that  “(“ or “)”   or both can be replaced by  ” [“   or   “] “  .
f(ai,bi) = f(U[    ai +( bi - ai)/3 n,    bi  -  ( bi - ai)/3 n  )  ] )  (n=1 to infinity ) =
U f( [    ai +( bi - ai)/3 n,    bi  -  ( bi - ai)/3 n  )  ] ) (n=1 to infinity )
f is continuous  so f( [    ai +( bi - ai)/3 n,    bi  -  ( bi - ai)/3 n   ] ) = [Cn ,Dn]
f(ai,bi) = U[Cn ,Dn] (n=1 to infinity )
[C1 ,D1] subset  of [C2 ,D2] subset  of [C3 ,D3] subset  of …….      subset  of [Cn ,Dn] …. subset  of(ai,bi)
If   f(dn) =Dn  and  x1  belongs to   (ai +( bi - ai)/3 n,    bi  -  ( bi - ai)/3 n  ) :
| Dn- f(x1) | <= C| dn - x1 |<= C|b-a| < infinity  then dn is bounded as well as  cn which f(cn) =Cn   .Regarding this fact we result :
U[Cn ,Dn] (n=1 to infinity )= (inf Cn ,supDn) both on n .What is resulted is that f(A) is a union of intervals. f(A) =  U Ji (i=1 to infinity ) while m(Ji) <= Cm(Ii) . Tis result is true even when “(“ or “)”   or both can be replaced by  ” [“   or   “] “  .
m* (f(A) ) = inf (sigma(m(Bi)) (n=1 to infinity) \f(A) is a subset of U Bi and Bi  is an interval )<=
sigma(m(Ji)) (i=1 to infinity) < =C sigma(m(Ii)) (i=1 to infinity)
     But Ii ’s  are component  intervals of A then  sigma(m(Ii)) (i=1 to infinity) is the minimum of (sigma(m(Ai)) (n=1 to infinity) \ A is a subset of U Ai and Ai  is an interval )  so:
m* (f(A) ) <= Cm* (A)

Excuse me ,this proof is true only for none empty open sets(empty set  clearly satisfies the intended inequality ).The used theorem is correctly as following  :
” Every none empty Open set in R such as S can be exposed as a countable union of disjoint component intervals of S.”

(a)
Let me know this solution is true or not. The former one apparently works only for open sets .
Ii ’s are  intervals (boxes) .
A is a subset of   U Ii ,  (i=1 to infinity )
    In former solution it is proved that  m(f(Ii )) <= C m(Ii) While we Know f(Ii ) is an interval as well as  Ii ,so it is lebesgue measurable .
sigma(m f(Ii )) (i=1 to infinity) <= C sigma(m(Ii )) (i=1 to infinity)
( sigma(m f(Ii )) (i=1 to infinity) ) / C <= sigma(m(Ii )) (i=1 to infinity)
0 <  C  <  infinity
f(A)  is a subset of   f(U Ii)= U f( Ii) ,  (i=1 to infinity ) and f(Ii ) is an interval so :
m* (f(A) ) / C <= (sigma(m f(Ii )) (i=1 to infinity)  )/C <= sigma(m(Ii )) (i=1 to infinity)
  { Ii} are an arbitrary set with desired condition so  m* (f(A) ) / C is a lower bound for the set { sigma(m(Ii )) (i=1 to infinity) / Ii is an interval (box) and A is a subset of   U Ii } then that is smaller the greatest lower bound of this set which is in fact m* (A) )  so :
m* (f(A) ) <= Cm* (A)

It seems to me correct even if the proof that $ f(A)$ is a countable union of open intervals is quite unreadable. Please, try to write in $ \text{\LaTeX}$.

(b)
About (b) I couldn’t get to a reasonable result but in the special case where A is open ,f(A) is countable union of intervals (as mentioned earlier).So if A be a  Lebesgue measurable set (while it is open and it is so ) then f(A) is a Lebesgue measurable set .
  I guess This theorem may be useful in general case.
“If  A be a Lebesgue measurable set ,there are sets such as C which belongs  to F_sigma  and D which belongs  to G_delta  such that:
  C subset of A  subset of D “ and  m(D-C)=0
F_sigma  is the set of all countable unions of closed sets and G_delta  is the set of all countable intersections of open  sets.

Let's prove (a) in a more readable way. First, notation: $ B(a,r): \equal{}\{x\in\mathbb R\colon |x\minus{}a|<r\}$, where $ a\in\mathbb R$ and $ r>0$. We know that $ A\subset \bigcup_{i\equal{}1}^{\infty} B(a_i,r_i)$ where $ \sum_{i\equal{}1}^{\infty} r_i<m^*(A)\plus{}\epsilon$, and $ \epsilon>0$ is as small as we wish. The Lipschitz condition implies $ f(B(a,r))\subset B(f(a),Cr)$. Hence $ f(A)\subset \bigcup_{i\equal{}1}^{\infty} B(f(a_i),Cr_i)$, which implies $ m^*(f(A))\le C(m^*(A)\plus{}\epsilon)$.

(b) For any $ \epsilon>0$ there is a compact set $ K\subset A$ such that $ m(A\setminus K)<\epsilon$. Since $ f$ is continuous, $ f(K)$ is compact too. Also, $ f(A)\setminus f(K)\subset f(A\setminus K)$ and $ m^*(f(A\setminus K))<C\epsilon$. By subadditivity of $ m^*$ we have $ m^*(f(A))\le m(f(K))\plus{}C\epsilon$, which implies that $ f(A)$ is measurable.


[hide="Answer"]Multiples of 9 greater than 65: $72$, $81$, $90$, $99$. Not a multiple of 5, removing 90. Tens digit is odd, units digit is even, leaving $n=72$.[/hide]

[hide]2 seconds of thought tells you it has to be 72.  the only numbers in consideration anyway are 72, and 90, and the latter is a multiple of 5.[/hide]

[quote="XxHarryxX"][hide]The answer is 72.  81 has two odd integers and 90 is a multiple of five.[/hide][/quote]

i think 8 is even   :roll: But I see what you mean.
You only have to think about three numbers, a moment of mindwork tells us the answer is 72.

:lol: Devendra Patel, you missed the hiding...  :rotfl:

[quote="Devendra Patel"]72
[hide][/hide][/quote]
:rotfl: haha do you mean
[hide]72[/hide]

[quote="math92"]I am a two-digit integer. My tens digit is odd, but my units digit is even. I am greater than 65. I am a multiple of 9, but I am not a multiple of 5. What integer am I?[/quote]

Using elimination

Multiples of 9 greater than 65, two digit
72, 81, 90, 99

Not a multiple of 5
72, 81, 99

Tens digit is odd
72, 99

Units digit is even
72


Reserves were announced today, here are the full rosters:

[hide="For the West..."]
[u]Starters[/u]
Tim Duncan- San Antonio
Kevin Garnett- Minnesota
Yao Ming- Houston (out with injury)
Tracy McGrady- Houston
Kobe Bryant- LA Lakers
[u]Reserves[/u]
Steve Nash- Phoenix
Dirk Nowitzki- Dallas
Allen Iverson- Denver
Carlos Boozer- Utah (out with injury)
Amare Stoudemire- Phoenix
Shawn Marion- Phoenix
Tony Parker- San Antonio[/hide]

[hide="For the East..."]
[u]Starters[/u]
LeBron James- Cleveland
Chris Bosh- Toronto
Shaquille O'Neal- Miami
Dwayne Wade- Miami
Gilbert Arenas- Washington
[u]Reserves[/u]
Vince Carter- New Jersey
Jason Kidd- New Jersey
Jermaine O'Neal- Indiana
Chauncey Billups- Detroit
Richard Hamilton- Detroit
Dwight Howard- Orlando
Caron Butler- Washington[/hide]

So what do you guys think? What are your opinions? Any noticeable players missing or what?

And how on earth is steve nash not a starter? is 2 time MVP not enough to start?

because of the suspension

it's clear that the west has a [b]much, much[/b] better bench. The East has a slightly better starting lineup. The west starters have no real point guard, but they have two good ones on the bench.

prediction:I'm gonna go with the west, 126, 121

[quote="kheg_k"]
it's clear that the west has a [b]much, much[/b] better bench. The East has a slightly better starting lineup. The west starters have no real point guard, but they have two good ones on the bench.

prediction:I'm gonna go with the west, 126, 121[/quote]

Keep in mind that Yao Ming is injured meaning that Mike D'Antoni will have to choose someone on the bench to replace him; the chances are great that he will pick Steve Nash, giving the West a true point guard and possibly a better starting lineup. By putting Nash into the lineup, he gets something like this:
Center- Tim Duncan
Forward- Kevin Garnett
Forward- Tracy McGrady
Guard- Kobe Bryant
Guard- Steve Nash

I'm gonna say that Carmelo Anthony and Josh Howard are picked by David Stern.

If Nash does get picked to replace yao in the starting lineup, then the west will clearly be the better team. The starters will be fairly even.

[quote="not_trig"]Well, the teams in the West are better, because the good people in the East are all randomly scattered...

The East will probably have a problem with Shaq in there, he's getting old... but Bosh, Arenas, Wade, James will be REALLY good -- if they can play the whole game :D

The West will probably win, due to their bench pwning the East's. but the West kinda lacks swingmen (just McGrady and Bryant, really, plus maybe Iverson, to the East's James, Bosh, Wade, Arenas (kinda), Carter, Hamilton). The West obviously has better big men, plus Nash who pwns at point, but they have no depth at 2 and 3.[/quote]

BOSH???????? A SWING MAN?????????? hes like a power forward

Ummm... No.

The West changed their roster b/c of injuries.
Yao Ming: OUT
Carmelo Anthony: IN
Carlos Boozer: OUT
Josh Howard: IN

Good job, life=tennis+math; you just got both right! =)

[quote="stupidkid"]Man Yao Ming is going be a starter for probably most of the All Stat games he plays in. All those people in China definitely voted for him.[/quote]
That's true. As long as Yao Ming is in the list, he shall be a starter.

Why do Michael Redd and Mo Williams BOTH get snubbed? They are good enough so that at least one of them should make it.

[quote="ra5249"]BTW...
Jason Kidd was out, and Joe Johnson got stuck in.
Is anyone else thinking, like, wtf?!?[/quote]

what are you talking about, Joe Johnson is a an excellent player.

Anyways, I got the East winning and Vince Carter as mvp.

Also, Dwight Howard got robbed yesterday, did you see how high above the box he touched?

Finally West win!! :D
And Kobe get the MVP.


function
logarithms
inequalities
inequalities proposed

Sorry if this one already appered 10 times here...I give the complete exercise so that there is a first question which is an help...

1) Let $f$ be the function defined by $f(x)=x^x$ for each $x>0$.
Determine the minimum of $f(x)$ as $x$ varies over the set of the positive real numbers.

2) Let $x,y$ be two positive real numbers.
Prove that $x^y+y^x > 1$.

Pierre.

Let $f'(x) = x^x(1+\ln x) =0$, we get $x=1/e$.
It is easy to verify that $\min f = f(1/e) = e^{-1/e}$.

if x or y  >= 1 then x^y+y^x >1. So we may assume 0<x;y<1.
Applies Bernoully inequality :
x^(-y) = (1+1/x - 1)^y  <= 1 + (y-xy)/x. Hence x^y >= x/(x+y-xy)
Like that y^x >= y/(x+y-xy)
x^y+y^x >= (x+y)/(x+y-xy)
We have strict inequality


function
analytic geometry
graphing lines
slope
Asymptote

Could someone point out what I'm doing wrong in this? I think what I'm seeing is that curve() and slopefield() don't understand the function sqrt(1+x^2) properly..

I'm following instructions [url=http://asymptote.sourceforge.net/doc/slopefield.html]here.[/url]

[asy]import graph;
import slopefield;
size(300);

Label f;
f.p=fontsize(10);
xaxis(-10,10,LeftTicks(f,10));
yaxis(-10,10,RightTicks(f,10));

real a(real x) {return sqrt(1+x^2);}
D(graph(a,-10,10));
real b(real x) {return -sqrt(1+x^2);}
D(graph(b,-10,10));
real c(real x) {return sqrt(1+x^2);}
D(curve((0,1),c,(-10,-10),(10,10)),red);

add(slopefield(a,(-10,-10),(10,10),20));[/asy]

I do not see anything wrong thith the picture; the curve is tangent to the slope field and passes through the specified point exactly as it should be. You didn't expect $ y\equal{}f(x)$ to be a solution of the differential equation $ y'\equal{}f(x)$, did you?

It passes through the specified point, but when I give "real func(real x) {return sqrt(1+x^2);}", using graph() and curve() lead to two different lines on the picture. graph() leads to the correct line.

ehh maybe I'm missing something here..

graph() gives you $ y\equal{}f(x)$ and curve() gives you the solution of $ y'\equal{}f(x)$, i.e., the antiderivative of $ f(x)$ in this case, the exact formula for which I'm too lazy to compute now. See the difference?


superior algebra
superior algebra unsolved

what are the Double cosets of $ S_{n\minus{}1}\setminus S_{n\minus{}1}/S_{n\minus{}1}$?

Obviously, there is only one¿
Sorry, but you either check your posts or don't expect answers  :wink:


AMC
AIME
email
USA(J)MO
USAMO
AMC 10
AMC 12

Hi you guys.
I was wondering when the MAA said:
"After that process we carefuly considered the contestants not already selected. Out of nearly 6000 eligible contestants, there were 15 students in 10th grade or below with qualifying AMC 12 scores who scored 8 or more on the AIME I or AIME II. We will make a special invitation to these students to the USAMO. This makes a grand total of 514 students invited to take the 2009 USAMO."

I have a 105 AMC 12 and an 8 AIME, and am a 9th grader. However, I didn't make it..
Should I email the MAA? If so, what email should I use (there are many on the website)?

Thanks!

You should, but wait until next Monday:

[quote="AMCDirector"]Please see the reminder in Section V, page 5 of the AIME Teachers' Manual, no AIME results will be given out by phone (or otherwise) until after April 13. Please do not call or contact us now, we have much to do yet. [/quote]

but isn't the policy about no emails until monday just about inquiring about aime scores? what email would i email it to?

Refer to [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1094145#1094145]this[/url] from 2008. Inquiring about USAMO qualification is equivalent to inquiring about your AIME score.

It could be because you also took amc 10 and they used ur amc10 index. I think the 8 aime or above thing is for people who couldn't take the 10.

they're penalizing me for [i]taking[/i] a test??

[quote="simo14"]Hi you guys.
I have a 105 AMC 12 and an 8 AIME, and am a 9th grader. However, I didn't make it..
[/quote]

There are two things that may have happened.

1. They didn't look at your AMC12 score, since they usually just consider the higher one.
2. They only want the 8+ to apply to people who took only the 12, since the whole idea is that people who went for the extra challenge should not be penalized for it.

I wish you luck, but I think the fact that you did take the 10 and didn't reach the qualification barrier with it is enough reason to not allow you to fit under that group of qualifiers.

[quote="simo14"]the fact that i took the amc 12a in the 1st place shows that i went for the extra challenge..
had i known about this, i wouldn't have taken the 10b, this is completely unfair![/quote]

Like I said, since I'm assuming you bubbled your AMC10 score on the AIME, it might just be that they haven't looked at your AMC12 score.  I doubt it, though.

I think a post from AMC Finance said they only looked at the higher AMC score. So you would benefit from this special invitation only if you took AMC 12 only or scored higher on AMC 12 than AMC 10 (which, if ever happened, would probably imply your AMC 10 score was not AIME-qualifying).

@simo14: if AMC was not gracious enough to grant this special invitation, you will still not qualify. Take it as a gift rather than a right.

I'm not taking it as a right.. I'm just saying, if they took some of them in the category, wouldn't it be unfair to the others?
so you guys think the reason is that i took the 10b and scored higher than it on the 12 or that i bubbled my 10b score on the aimr sheet? So do you guys think there's a chance i might still qualify? should i still send them email?
thanks!

Well, the addition of these people does not displace any regular qualifier, so I don't see how it's unfair...

There is still chance, imo, if your non-qualification was not an intentional selection by the AMC but by a procedural omission. If so, you should wait until Apr. 13 to e-mail them your case. I doubt this is the case, though (I know of another person who was in pretty similar situation as you and did not qualify, 2 points from secondary index with an 8 aime and a qualifying amc 12 score).

This is the same with me, I would have taken the 12 instead of 10, I think I missed it with a 9 on AIME and 121.5 score on AMC10 (too many mistakes). Although I thought I got an 11, but I don't have my score yet, so that's the only way I can see it possible.

I'm pretty sure the point of taking the extra 15 was to help out the underclassmen who [b]only[/b] took the 12's.  Taking one 12 and one 10 still gives the advantage of taking the 10, which one would think is easier to score high on.  So, in that sense, you wouldn't be in the category, simo.

but on the website it just says 8 aime with an amc 12 qualifying score..
and, should they not warn people that they were going to extend invites to those who only took the amc 12?
in that case, i would have taken the amc 12b or no b test..
so i think the most fair thing to do is to extend those extra invites to all those underclassmen who took the amc 12 and got >=8 on the aime. it wouldn't be more than like 5 people extra and the maa should be fair about extra invitations (though i am really grateful of their generosity in actually giving away these extra invites).

I agree, if they are going to invite special people, they should say beforehand. That way, you only needed a 180 index with 8 on the AIME, and I needed 10(!) on the AIME because I took the AMC10. They say the purpose of including AMC scores is so people will attempt the back page of the AMC, but I got just as many of the earlier problems long as the later, so that's how I got 121.5.

Well the point of the extension (which was very good) is to make it fair for those who did not get a chance to take the 10. You took the 10, and thus had an advantage in the first place.

That being said, you could still try to contact them and ask. Frankly, if I were you, I would, just to be sure.

I'm starting to see how this situation is really unfair.  The AMC office really should have told people beforehand about this new selection process.  Still, @simo14, since you already took the AMC 10 (yes, you shouldn't be punished for taking a test) you already had a shot at the advantage of taking the easier test.

I don't feel that this was unfair. Given the large discrepancy in difficulty between the AMC 10 and the AMC 12, the AMC decided to be generous to some that were unable to take the 10.

Furthermore, these students did not displace anyone so you had a fair enough shot.

so should i just kill all my hopes of qualifying for usamo?  :(
i still think it's unfair to disadvantage those who took a test. i agree wholeheartedly with giving a boost to those who took the amc 12, but not to extend the gracious invitation to those who took both and met the criteria but didn't have the foresight not to take the amc 10 (which is absurd as im sure they would want people to take their tests..).

If they applied it to those who took both 10 and 12, then it would simply give that pool of people an advantage over others. Also, according to the index, an aime score of 8 would need a 135 on the amc 10 to qualify. Also, most likely, less contestants 10th grade or under got an 8+ than 135+ on the amc 10 which would not make it unfair statistically speaking.

[quote]Also, most likely, less contestants 10th grade or under got an 8+ than 135+ on the amc 10 which would not make it unfair statistically speaking.[/quote]
exactly, so the extremely small number of people is so insignificant that they might as well do it to save fairness.

I meant that they probably selected an aime score as to not give those who took the 12 an advantage over those who took the 10.

they were still given an advantage though... (as in my case)
personally, i think all or none should have the special invitation.

I have to agree that excluding underclassmen from the special selection just because they also took the AMC-10 is pretty unfair. It does not affect me personally--except that I told extremely strong underclassmen at my school to take 12A/10B on the assumption that taking the AMC-10 would certainly make it easier for them to qualify for the USAMO. That was the clear message we've gotten for the past couple of years and it really disappoints me that this got sprung on them without any warning.

While I understand the motivation behind only giving this opportunity to people who did not have a chance to take the AMC-10, I really dislike the idea of what continuing to do this every year would introduce into the system. This basically asks underclassmen to make a bet on whether they'll score at the floor, in which case taking the AMC-10 gives them a huge advantage, or above the floor, in which case it gives them a huge disadvantage. It frustrates me that USAMO selection seems to turn more and more into a matter of strategically choosing which tests to take every year--and we never even know for sure what rules to base our strategy on.

simo14, I agree with you -- that if your scores are correct, you should also be invited. But arguing about it here isn't going to help anything. You should just e-mail them and ask.

[quote="bookaholic"]It frustrates me that USAMO selection seems to turn more and more into a matter of strategically choosing which tests to take every year--and we never even know for sure what rules to base our strategy on.[/quote]

Yes, but the important thing is that although the AMC and to a slight extent the AIME are meant to cultivate interest in math, the USAMO has the sole purpose of narrowing down the talent.  Therefore, all that is needed is a system that can find the best possible people, and the best possible people will make it no matter what the system.  If the AMC office thinks it's fair, then it's up to them.

thank you gauss and bookaholic. btw bookaholic, i think i know who u are..
@gauss: i know, i'm just waiting till monday to email them though.
thanks!

[quote="simo14"]btw bookaholic, i think i know who u are..[/quote]
Oh wait...oh! Hi. Darn, I feel pretty bad about this :( There is still the possibility that it was just a mistake...let's hope so...

simo, I can see both sides to this one.  I can see how some would think that you have had plenty of chances to qualify (i.e could have qualified with AMC-12+AIME >= 201, or a AMC-10+AIME >= 215 -- that's already one more bite at the apple than most people had).  To these people, it would likely feel like a greater injustice to omit those underclassmen that did not have a chance to take the AMC-10 that showed high potential on the AIME than it would be to omit folks in your situation.

However, I also see the point that you feel penalized for taking both tests (or perhaps more correctly, for taking the AMC-10 and not scoring better than you did).  I doubt the USAMO selection folks proactively envisioned the case where a person would have qualified for a USAMO position had they elected not to take a test.

simo, you should follow up on Monday.  The website is quite unclear, and it may be that few enough people in your situation that they would consider interpreting their policy to let you (and the small number of folks in your boat) into the USAMO pool.

I also see this situation as a bit unfair. Underclassmen were told that taking the AMC10 will be advantageous for qualifying for the USAMO, but this year, that wasn't true.
Frankly, I don't see why a 129 AMC10/ 8 AIME is any worse then a 99 AMC12/ 8 AIME. Oh well. I guess in any sort of system, there will always be people who just barely miss the cutoff.

Actually I really now think they missed me by mistake. It says:

"After that process we carefuly considered the contestants not already selected. Out of nearly 6000 eligible contestants, there were 15 students in 10th grade or below with [b]qualifying AMC 12 scores[/b] who scored 8 or more on the AIME I or AIME II. We will make a special invitation to these students to the USAMO. This makes a grand total of 514 students invited to take the 2009 USAMO."

If the student had taken the AIME (thereby getting >=8), then they would have had a qualifying score from either the AMC 12 or AMC 10. Why say "qualifying AMC 12 scores"? It's because people may have qualified for the AIME through the AMC 10, and they wanted people who also qualified through the AMC 12.

Just a thought.

Right, you
(1) are "in 10th grade or below"
(2) are "with [a] qualifying AMC 12 score"
(3) "scored 8 or more on the AIME I or AIME II"
so the AMC will "make a special invitation [...] to the USAMO".
There is no reason to believe otherwise at the moment unless the AMC changes the wording of the said sentence.

If you didn't get in because you took the 10, that would be really unfair. That means it would have been better for someone to get a lower score on the 10 than a higher score.

they wanted to make sure that anybody who got in on that rule had to at least be proficient with the amc 12 material, i guess, some people, saying this without evidence, probably drop off in the transition from amc 10 to amc 12, so the committee wanted to make sure that they would reward students good at both

[quote="asdf4"]I also see this situation as a bit unfair. Underclassmen were told that taking the AMC10 will be advantageous for qualifying for the USAMO, but this year, that wasn't true.
[/quote]

Actually, it is true.  Those underclassmen had their advantage but failed to capitalize on it; therefore, the AMC office decided not to reward them.
@simo: Dude, everyone feels for you, but that's not going to change the results.

Simo14,

If I may offer some advice,

CALL THE AMC OFFICE.

I was in a similar situation 3 years ago, and I imagine that sooner or later you'll pick up what I learned: obsessive-compulsive tracking of AoPS threads does not help.  Gather the intelligence first, and decide where to go from there.

Everything else is purely speculative.

I wish you the best of luck.

In the meantime, please remember how hard it is to run an organization.  Professor Dunbar and his colleagues are doing the best they can.

Maybe people should stop complaining. So what if the cutoff is 14 points higher? Especially for people who took amc10a and b, it is still advantageous. For a huge number of people, AMC10 can guarantee a perfect or near perfect score, while many of those same people would not fair well at all on the AMC12. Kent Merryfield posted some statistics showing that the average difference between AMC10 and AMC12 scores in California for people who took both is around 23 points, much greater than the 14 point difference in the indices.

Remember, there are less spots that are specially allocated to underclassmen to start with. With so many people getting over 140 on AMC10, there is no reason to expect the index to be lower every single time. Maybe you complainers should just improve and get a better score.

[quote="simo14"]I ended up not making it. Oh well..  :|[/quote]
what reason did they give?

If they had a reason, I think the only reason they could legitimately give is that simo14 did take the AMC10, thus he shouldn't be considered for the special case given to those who took the AMC12 only.

I'm really sorry to hear that simo, especially since I think you have a really good point.  I guess all you can do is pretend those extra people were never allowed to take the USAMO, and just do your best to qualify next year.  I think the fact that these additional people are taking the USAMO indicates that the AMC knows their selection process isn't up to par, and hopefully this will all be sorted out for next year.

Well, now I feel particularly retarded for making a stupid mistake and only getting a 7 on the AIME (I'm in 10th grade and qualified through the AMC 12).

Ah well, there's always the next two years and as some people said, this isn't the normal thing that the CAMC does anyway.

It was because I took the amc 10. I'm just gonna try harder for next year.


AMC
AIME
trigonometry
trig identities
Law of Cosines
number theory
group theory

hi there,

how much time should you spend on a problem before giving up and looking at the answers? :-P

That depends a lot on what type of problem it was.  What type of problem is it?

(By the way, if the answer you're looking at is, say, some one else's solution to a homework problem, then you shouldn't.  Just sayin'.)

Well, AIME level varies a lot -- personally, I would keep working on a later AIME question for at least an hour before I looked up a solution, if I couldn't get it.   If I was stuck on an earlier AIME question, I would keep working on it until I got it, however long that might take.  Actually, that's probably true of a later problem as well, but if I got fed up I would look at a solution only after a good long time working on it.

Now, that's not necessarily what's best for you -- that's just what I would do.  I usually give up on olympiad problems much too quickly, though.

In general I would say keep working until you run out of ideas. But practically speaking, an hour of intense thinking or investigation sounds sufficient for an AIME problem. Problems that I have a [i]feeling[/i] I should be able to do, I will usually keep working on for a day or two before checking the solution to see what I am missing.

ya, work until you like dont know what to do anymore (or if you start hallucinating, thats a sign to stop as well). If you still have some different possible of ways to solve it, keep trying. otherwise, think about it and if you still dont know, just look at the answer.

I personally recommend not looking at an answer if you can possibly avoid it.  Even after you've tried every crazy blind alley for the problem, your brain will continue to think it over, and if you come back to the problem every few days or weeks, you'll try even more blind alleys, but eventually will get the problem.  Plus, all those blind alleys probably turned up some interesting things you'd never have though about if you'd looked at the answer.  That said, reading a well-written solution can be super-informative.  I'd argue that if you think that you _ought_ to be able to do the problem, then don't look at the solution.  If you have a hunch it might require something significantly beyond your current level of understanding, then go ahead and look.  Another option is to have someone else (your teacher?) look at the solution and tell you if they think you'll get there, or give you a hint ("it uses the law of cosines", etc.).  Of course, if you see a bright light and hear dead relatives beckoning, it's time to take a break.

[quote="tom_clymer"]Of course, if you see a bright light and hear dead relatives beckoning, it's time to take a break.[/quote]

hahaha. Unless, of course, your name is Nash or Cantor!!

I think it depends what your goal is. If your goal is to learn math, you will learn more in a shorter amount of time by looking up solutions after a while. If you want to solve it for the sake of solving it, keep working on it until you get it.

I think it depends on what your goal is.  If your goal is just to solve the problem on your own, then I'd agree with tom_clymer.  However, if your goal is to learn lots of math/prepare for a particular event, you have to put time limits on yourself.  You only get so much time in life to learn/prepare.  You have to use it wisely.  Spending 5 hours on a single AIME problem is simply inefficient if your goal is to learn as much problem solving as possible.

(As an extension - this is one of my greatest gripes about undergraduate & graduate-level texts.  No solution manuals.  I don't have time to work all the problems, and would like to see solutions to some of the really, really hard problems that sometimes creep into these books.  Also, it's tough for me to direct a student to a book for self-study that has no, or few, solutions.  (I make an exception for the Zeitz book.)  If anyone can suggest good texts in number theory, group theory or graph theory that have solutions to the problems (or a solution manual) & would be appropriate for avid high schoolers or even undergraduates interested in self-study, I'd appreciate it.)

For graph theory, check out the book "Combinatorial Problems and Exercises", by Laszlo Lovasz.  It covers both graph theory and combinatorics.  It is mostly a problems book, with hints and solutions.  It would not be easy for a high-school student, but anyone who went through the book would be a strong combinatorialist and graph theorist.


modular arithmetic
algebra
polynomial
number theory

What is the remainder when $ x^{18} \plus{} 1$ is divided by $ x \minus{} 1$?

Do synthetic division.  This is made easier by the fact that most of the entries are 0.

$ x^{18} \plus{} 1 \equal{} (x^6 \plus{} 1)(x^{12} \minus{} x^6 \plus{} 1) \equal{} ((x^6 \minus{} 1) \plus{} 2)((x^{12} \minus{} 1) \minus{} (x^6 \minus{} 1) \plus{} 1)$

Noting that $ x \minus{} 1$ is a factor of both $ x^6 \minus{} 1$ and $ x^{12} \minus{} 1$, the above is equivalent to $ (0 \plus{} 2)(0 \minus{} 0 \plus{} 1) \equiv 2 \pmod{x \minus{} 1}$, and thus the remainder is $ \boxed{2}$.

There's a better way then to divide it out or factor it anyway.

By whatever its called theorem, we have $ x^{18}\plus{}1\equal{}Q(x) (x\minus{}1) \plus{}R(x)$ and we know that $ R(x)$ has a lower degree then what you divided by, so it is a constant. Then plug in 1 to both sides to find that constant.

You're looking at the [url=http://en.wikipedia.org/wiki/Factor_theorem]factor theorem[/url].  This is the easiest application of [url=http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=125861]polynomial modular arithmetic[/url].

[hide="Alternately..."] Note that $ x \minus{} 1 | x^{18} \minus{} 1$. [/hide]

Hmm... I thought it was the [url=http://en.wikipedia.org/wiki/Remainder_theorem]Remainder Theorem[/url].


Randomly select a whole number $ x$ such that $ 0 < x < 100$. What is the probability that $ x$ equals the sum of two perfect squares? Express your answer as a fraction.

There are $ 99$ numbers between $ 0$ and $ 100$.
$ 1^2$ plus any square below $ 10^2$ would be a number less than $ 100$, and there are $ 9$ of these. Then, there is $ 2^2$ plus any square from $ 2^2$ to $ 9^2$ (notice that $ 2^2\plus{}1^2$ has already been counted, and we don't want to count it twice). Now, we see a pattern. Repeating the process, there are $ 9$ numbers from $ 1^2$, $ 8$ from $ 2^2$, $ 7$ from $ 3^2$, $ 6$ from $ 4^2$, $ 4$ from $ 5^2$ (remember that $ 5^2\plus{}9^2$ is greater than 100, so that doesn't meet the criteria), $ 2$ from $ 6^2$ and $ 1$ from $ 7^2$. Adding up, we get $ 37$. But notice, $ 1^2\plus{}8^2\equal{}4^2\plus{}7^2$, $ 1^2\plus{}7^2\equal{}5^2\plus{}5^2$, and $ 2^2\plus{}9^2\equal{}6^2\plus{}7^2$. These have to be subtracted from the $ 37$, since they were counted twice. Thus, we have $ 34$ such whole numbers under $ 100$, and the probability is $ \fbox{34/99}$.

The answer key says 42/99 (I have 1997 states on my comp)

If it were 42/99 it could be simplified into 14/33.

Perhaps 0^2 is considered a perfect square, so there are 8 extra numbers (5^2=3^2+4^2). That's the only reason.

Review confirms $ \frac{42}{99}$. However, why isn't it simplified then?

It doesn't seem logical that O is considered a perfect square-it usually isn't. And if so, what are the 4 duplicates? (One is 0+25=9+16)


function
induction
algebra unsolved
algebra

FIND ALL FONCTION          N---->N
f(x²+y²+z²+t²) =(f(x)) ²+(f(y))²+(f(z))²+(f(t))²
 :D

A short question: is $0$ considered as element of $\mathbb{N}$¿

setting $x=y=z=t=0$ gives $f(0)=0$
setting $x=y=z=0,t=1$ gives $f(1)=f(1)^2$, so $f(1) \in \{ 0;1 \}$

statement: $f(n)=nf(1)$
Proof by induction:
It's clear for $n=0;1$
Let it be proofed for all $k<n>1$. Write $n$ as sum of four squares, which then all are lower then $n$.
Then you have
$f(n)=f(a^2+b^2+c^2+d^2)=f(a)^2+f(b)^2+f(c)^2+f(d)^2=(a^2+b^2+c^2+d^2)f(1)=nf(1)$
, so it's done.

Now both possibilities for $f(1)$ give correct solutions.


[quote="santosguzella"]Prove that:
$\dbinom{n+1}{2m+1}=\sum_{k=0}^{n}\dbinom{n-k}{m}\dbinom{k}{m}$[/quote]

$\sum_{k=0}^{n}{C_{m}^{n-k}C_{m}^{k}}$ is the coefficient of $x^{n}$ in the product $(x+1)^{m}(1+x)^{m}$. But $(x+1)^{m}(1+x)^{m}=(1+x)^{2m}$ so the coefficient of $x^{n}$ is $C_{2m}^{n}$.


invariant
combinatorics proposed
combinatorics

we have 2n+1 balls in the cell number 0 of a infinitive*infinitive row.
in each level we can chooose two balls from a cell x and put one of them into cell x-1 and we put the other ball into cell x+1
is it true that we never have a ball into the cell n+1?

Hahah this is the flea problem. I know it but instead of balls there were fleas :)
Whatever :).

Im gonna post the solution soon:D

so would you mind please tell where was this problem?
and also the solution of it

Hi!
Sorry that I am late with posting the solution but I was a little bussy and I didn't have time.

Well, I will give you my problem and solve it and see how it result in yours.

[b]The Flea Problem.[/b]
We have $2n+1$ fleas on the point $0$ of the number axis. We play a game. On a turn we may pick two fleas which are on number $x$ and place one of them in $x-1$ and one in $x+1$. Prove that:
1) The game has and end!
2) The game allways end in the same configuration!
3) The final configuration is: $(-n,-n+1,\ldots,-1,0,1,\ldots,n-1,n)$ !

Comment: If we prove $1)$,$2)$ and $3)$ then we can surely say that never a flea have been in $n+1$ because if once of the time there is a flea in a place $\geq k$ then after that in any moment there should be a flea with place $\geq k$.

Let's start!
Solving $1)$- invariant:
We can see that if the "value" of every flea is the place where it stays then over all fleas:
$S_1=\sum x_i = const = 0 (a)$
where $x_i$ is the value of the i-th flea. Also :
$S_2=\sum x_i^2 = 2.N (b)$
where $N$ is the number of the turnes played because at every turn $S_2$ grows with two: $2x^2 +2 = (x-1)^2 +(x+1)^2$ .

Also there cannot be a "hole" of two or more places. I mean we cannot have the situation: $flea, (empty), (empty), flea$ because at the first turn we get a hole of two this means that we have played one of this two places, so there must be a flea in the other.

Suppose the game continues endlessly. Then $S_2$ grows endlessly. In simple words this means that for every natural p we can reach a situation in which $S_2>p$. This means ( because we know how much are the fleas) that for every natural $q$ we can reach a situation in which $|x_i|>q$. but because we cannot have a hole of two then for every flea $j$,  $|x_i - x_j|> 2.2n$ which for big enough $q$ means that all fleas have same sign which is contradiction to $(a)$.
So the game has an end!!!

Solving $2)$- extreme element
Well, I don't remember fully this part but the main idea is to let there be two final positions and look at the last moment when we can reach both of them and then there must be the possible turns at places x and y and using that if we are able to play x at some time then we must play x at some(maybe later). I will think about this part and edit or post again after I remember the exact solution.

Solving $3)$- construction
Find a game which results in $(-n,-n+1,\ldots,-1,0,1,\ldots,n-1,n)$!!
We can do that very natural :) Or maybe just by induction.

So we only left to prove $2)$ but I am sure it is true and I will try to solve it soon :D
Hope that this will satisfy you for now, OK?

Well, now I found the original solution of part 2) :
____________
We will prove that the final position is only one possible. Suppose the opposite and let's have two final positions A and B. Let's consider the last possible turn in which we can reach this two positions. Let that be turn at m (leading to A) and turn at k(leading to B). $m \not\equiv k$. But we can play firstly m, and after that k, or vice versa and both of them lead to same possition which is contradiction with the extremality of the turn.
______________

Well that's it! Finally!


Gauss
number theory
number theory theorems

Can someone recommend me a comprehensible proof of the following result of Gauss?

[i]Each positive integer can be written as the sum of at most 3 triangular numbers.[/i]

most number theory books do not provide a proof of Gauss' triangle number theorem.  But they do provide proofs of the fact that a number can be written as a sum of three squares iff it is not of the form 4^n*(8k+7)

if you can get your hands on a proof of that fact, then the sum of three triangular numbers becomes trivial:

lemma 1. A number of the from 8k+3 can be written as the sum of three odd squares

proof: if you accept the fact that a number can be written as a sum of three squares iff it is not of the form 4^n*(8k+7), you will notice that 8k+3 can be written as the sum of three squares say x^2+y^2+z^2, and if we look mod 4, x^2+y^2+z^2 = 3 mod 4 => x^2 = y^2 = z^2 = 1 mod 4, so x,y,z are odd.

claim: any number N can be written as a sum of at most three triangular numbers

proof:  consider the number 8N+3, from lemma 1, there exist x,y,z s.t.
8N+3 = (2x+1)^2 + (2y+1)^2 + (2z+1)^2. => 8N = 4*(x^2+y^2+z^2+x+y+z) => N = (x^2+y^2+z^2+x+y+z)/2 =>
N = x*(x+1)/2 + y*(y+1)/2 + z*(z+1)/2, three triangular numbers.

for more info about sums of polygonal numbers and sums of squares, the book: Additive Number Theory: The Classical Bases by Melvyn B. Nathanson covers this topic in chapter 1.


This nice inequality was proposed in a National Olympiad Contest.
Prove that

   (b^3+a)(c^3+b)(a^3+c)  \geq 125abc

with a,b,c real numbers   \geq 2.

It can be solved in an ingenious mode by AM-GM inequality. Try it!

First for $a\geq 2$ we have $2a^2-5a+2\geq 0$ because 2 is the gratest root of $2a^2-5a+2$

Next $a^3+c\geq 2a^2+2\geq 5a$ and cyclic product gives $(b^3+a)(c^3+b)(a^3+c) \geq 125abc $

$ LHS $ is at least $ (4y+x)(4z+y)(4x+y) $ and by $ AM-GM $ we have $ 4y+x\geq 5y^\frac{4}{5}x^\frac{1}{5} $ this two imply desired inequality.


function
combinatorics unsolved
combinatorics

A deck of $ 32$ cards has $ 2$ different jokers each of which is numbered $ 0$. There are $ 10$ red cards numbered $ 1$ through $ 10$ and similarly for blue and green cards. One chooses a number of cards from the deck. If a card in hand is numbered $ k$, then the value of the card is $ 2^k$, and the value of the hand is sum of the values of the cards in hand. Determine the number of hands having the value $ 2004$.

The red cards are determinated by the (even) sum of their values, since an even number can be written uniquely as a sum of power of $ 2$. So the blue cards and so the green cards. The jokers have value $ 1$. So we can use none of the jokers or both ($ 2004$ is even). In the first case, we have $ S_r \plus{} S_b \plus{} S_g \equal{} 2004$, where $ S_r$, $ S_b$ and $ S_g$ are the sum of values of red cards, blue cards and green cards. Each solution gives a hand and viceversa. Then we are looking for the number of integer solutions of $ x \plus{} y \plus{} z \equal{} 1002$ (again, note that each sum is even). This is $ \binom{1004}{2}$. In the other case we get $ \binom{1003}{2}$. Our total is thus $ \binom{1004}{2} \plus{} \binom{1003}{2}$.

[hide="Solution"]Let's finish it with generating function.The generating function will be
\begin{align*} G(x) &=(1+x)^2.(1+x^2)^3.(1+x^4)^3 \cdots (1+x^{1024})^3 \\ & = \frac{(1+x)^2.(1-x^{2048})^3}{(1-x^2)^3}\\ & =(1+2x+x^2-3x^{2048}-6x^{2049}-3x^{2050}+ \cdots )(1-x^2)^{-3}\end{align*}
We have to find the coefficient of $x^{2004}$ is $G(x)$.It's easy to observe $(1-x^2)^{-3}$ does not contain any odd power of $x$.So we get, $x^{2004}$ by multiplying  $1$ with the $x^{2004}$ in the second factor and $x^2$ with the $x^{2002}$ in the second factor.Therefore the ans will be $ \binom{1004}{2} + \binom{1003}{2}$[/hide]


geometry
angle bisector
geometry proposed

Let $ABC$ be a triangle, and $C^{\prime}$ and $A^{\prime}$ the midpoints of its sides $AB$ and $BC$. Consider two lines $g$ and $g^{\prime}$ which both pass through the vertex $A$ and are symmetric to each other with respect to the angle bisector of the angle $CAB$. Further, let $Y$ and $Y^{\prime}$ be the orthogonal projections of the point $B$ on these lines $g$ and $g^{\prime}$.
Show that the points $Y$ and $Y^{\prime}$ are symmetric to each other with respect to the line $C^{\prime}A^{\prime}$.

It is sufficient to show that $YY'$ is perpendicular to $AC$ since it can be easily proved that $C'Y = C'Y$ and $A'C' // AC$.

 Let $Ay$ the ray on the line $g'$ such that $\measuredangle(Ay, AC) + \measuredangle{YAB} = 0$.
 We have $\measuredangle{BY'Y} = \measuredangle{BAY} = \measuredangle(Ay,AC)$. Since $BY'$ is perpendicular to $Ay$, we obtain $YY'$ is perpendicular to $AC$. And we are done.


modular arithmetic
number theory
prime factorization

What is the best way to compute $ a^b mod n$? I can think of 5 methods, and i wonder which one can be used most frequently with the least effort :p

[b]1.[/b] When $ n/2 < a < n$ make use of $ a^b \equiv (a - n)^b\pmod{n}$, because $ |a - n| < n\2$, which is smaller than $ a$.
[b]2.[/b] Find a positive integer $ c$ such that $ a^c\equiv 1\pmod{n}$. If $ b = q\cdot + r$ then $ a^b\equiv (a^c)^q\cdot a ^r\equiv 1^q\cdot a^r\equiv a^r\pmod{n}$
[b]3.[/b] Find a positive integer $ c$ such that $ a^c\equiv - 1\pmod{n}$. Then $ a^{2x}\equiv 1 \pmod{n}$, and then apply [b]2[/b].
[b]4.[/b] Assume that $ a^c\equiv 1 \mod{n}$ and $ b$ is just below $ c$and that $ a$ amd $ n$ are reletively prime. Calculate $ a^{c - b}\pmod{n}$ and Bezout $ a^{c - b}$ and $ n$. Then we have $ x\cdot a^{c - b} + y\cdot n = 1$. Take modulous of both sides the the unknown quantity $ a$. Then we have that $ x\equiv x\cdot a^c \equiv a^b\pmod{n}$.
[b]5.[/b] Use Chinese remainder theorem. Factor $ n$ into pairwise relative prime factors. Compute $ a^b$ modulus each factor, and then use the Chinese Remainder Theorem to combine and obtain the result modulo $ n$

As for being the most error-prone and also time consuming, I think [b]4.[/b] and [b]5.[/b] are good candidates...

I assume you mean "by hand."  You'll find that [b]5.[/b] is necessary when $ \gcd(a, n) > 1$.  You also haven't specified whether $ b$ is large or $ n$ is; in particular, if you don't know the prime factorization of $ n$ then the best method by far is exponentiation-by-squaring.  If you do know the prime factorization of $ b$ then you can split the problem up; instead of computing $ a^{pq} \bmod n$ you can reduce $ a^p \bmod n$ and then take it to the power of $ q$.

In general, the answer is "it depends on what makes the computation hard."

It really depends on the particular problem. I tend to go with either 1 or 5 (or with Euler's Totient formula), depending on the situation.

In general, I find method 1 to be more "fun," especially with problems like $ 2^{2008} \pmod {14}$, where you see that $ 2^4 \equal{} 16 \equiv 2$ and the exponent collapses.


calculus
integration
function
Support
algebra
polynomial
complex analysis

Hello,

I've got another infinite system of integral equations to solve. But first I have a general question. Does
\[ \int_{\minus{}1}^0e^{\lambda s}f(s)\mathrm{d}s\] for every $ \lambda\in (a,b)$ ($ a<b$) imply $ f\equiv 0$?
Now the actual problem:
\[ \int_{\minus{}1}^0 e^{\lambda s} [f(t)(\lambda\plus{}1\minus{}e^{\minus{}\lambda})\plus{}g(t)(\lambda\minus{}1\plus{}e^{\minus{}\lambda})]\mathrm{d}s\equal{}0\]
for every $ \lambda>C$ for a fixed $ C>0$. Does this imply $ f\equiv g\equiv 0$?

laxton

The Laplace or Fourier transform of a function with compact support is entire, and an entire function which is identically zero on a segment is zero everywhere. The transform is invertible, so a function with zero transform is zero a.e. So yes, if $ I$ and $ J$ are bounded intervals and $ \int_I e^{\lambda s} f(s)\,ds=0$ for all $ \lambda\in J$, $ f=0$ almost everywhere on $ I$.

Now, let $ \hat{f}(\lambda)=\int_I e^{\lambda s}f(s)\,ds$. Your equation (assuming you meant $ f(s),g(s)$ rather than $ t$) is $ \left(\lambda+1-e^{-\lambda}\right)\hat{f}(\lambda)+\left(\lambda+1-e^{-\lambda}\right)\hat{g}(\lambda)=0$, which has entire solutions $ \hat{f}(\lambda)=p(\lambda)\left(\frac{\lambda-1+e^{-\lambda}}{\lambda}\right), \hat{g}(\lambda)=p(\lambda)\left(\frac{\lambda+1-e^{-\lambda}}{\lambda}\right)$ for entire functions $ p$. Why divide by $ \lambda$? That accounts for the only common zero of the two functions, a single factor at the origin.

Which ones can be transforms of integrable functions on $ [-1,0]$? That imposes the additional restriction that $ \hat{f}$ and $ \hat{g}$ can't grow any faster than $ e^{|\lambda|}$, and can only grow in restricted directions. If $ \int_{-1}^0 |f(s)|\,ds=M$, ${ |\hat{f}(\lambda}|\le \begin{cases}M&\text{Re}(\lambda)\ge 0\\M|e^{-\lambda}|&\text{Re}(\lambda)\le 0\end{cases}$. We already have $ e^{\lambda}$ and constant factors in the picture. On the positive side, this forces $ |p(\lambda)|\le M$ as $ \lambda\to\infty$; on the negative side, $ |p(\lambda)|\le M|\lambda|$ as $ \lambda\to-\infty$.

The only entire functions that fit under polynomial bounds are polynomials, and these bounds are tight enough to force $ p$ to be constant. What $ f$ and $ g$ do we get out of this? The inverse transform of $ 1$ is the Dirac delta $ \delta(s)$, and the inverse transform of $ \frac{1-e^{-\lambda}}{\lambda}$ is $ -\int \delta(s)-\delta(s+1)\,ds=\mathbf{1}_{[-1,0]}$, the function which is $ 1$ on that interval and zero elsewhere.

So $ f(s)=C\left(\delta(s)-\mathbf{1}_{[-1,0]}(s)\right)$ and $ g(s)=C\left(\delta(s)+\mathbf{1}_{[-1,0]}(s)\right)$ for some constant $ C$. For these to be conventional functions, $ C$ must be zero, and we are done.

Transform methods. Understand them.

Can you suggest any good reference for these transform methods (including entire functions)?

laxton

It's a very big subject, and I don't really have a reference; I learned most of what I know in conversations with my father. One point to clear up: entire functions are complex analysis, a different field. "Entire" just means that a function is analytic on the whole complex plane.


I wasn't able to find any other post that would disscus this... so I ask :

While reading some posts I noticed that when people are chosen for both IMO and IPhO teams they have to chose where will they go.

Is there any rule that forbides being at IMO and IPhO at the same time, or people chose one of them so they can really prepare well?

You're not allowed to do both.  One could argue that having the olympiads at (or around) the same time and telling students they can't go to both is a bad idea, because there would be a lot of good people in common.  However, they do want people to focus on one and do really well in that one...also, they probably want to give more people the opportunity.  I would say it's a better decision.

They don't want someone going to one olympiad thinking about the other, having one olympiad as a "primary" one and one as a "secondary" one.  The people going to each should be completely committed there.  Plus, the teams may do their own training (as the US IMO team did in China last year), so they want full commitment.

Thank you! :lol:

But what about other combinatinons like IMO and IOI , or IPhO and IChO?

Technically speaking, you CAN do both in some countries (for instance, in Bosnia and Herzegovina a student participated in both IMO 2003 and IPhO 2003).

It is not recommended, though.

It's a silly decision to say that you can only participate in one olympiad. Unnecessarily confining yourself to one subject, especially at such a young age, is stupid. You can wait until graduate school to do that (and even then, I still plan to be reasonably conversant about a wide range of subjects both related and not related to mathematics).


A conference begins between 6:00 and 7:00 p.m., and ends between 9:00 and 10:00 p.m. The minute and hour hands have exchanged places.
When does the conference start and end ?

[size=75]
from book "The Moscow puzzles" by Boris A. Kordemsky

Please hide Your solution . Write inside Hide ... /Hide
[/size]

[quote="isabella2296"]Do you mean that when it started somewhere between 6 and 7, the hour hand was on A and the minute hand was on B, and then when it ended, the hour hand was on B and minute hand on A?[/quote]

Yes. How it say short in English ?

[b]O M G wrote:[/b]
[quote]you know since its between 6 and 7, it should be 9:30 ending, and 6:45 since 9 corresponds to 45. so it should last 2 hours and 45 seconds.[/quote]

Actually, at 6:45 the hour hand would have moved 22 and 1/2 degrees clockwise, because it is a 3/4 of an hour past 6:00. At 9:30, the hour hand would have moved 15 degrees clockwise, because it's half an hour past 9:00.

Here's the solution. It's not exact, but it's really close. I estimated one of the values.

[hide="Solution"]

Say that the conference starts at 6: x and ends at 9:y. An hour is from one number to the next, so it travels as far as the minute hand does in 5 minutes. There are 5 minutes from the number 6 to 7. On the whole clock there are 60 minutes. Therefore the hour hand is on 6*5+ 5/60*x for the little marks on the clock that mark the minutes. The minutes is on x. Similarly, at 9:y, the hour hand is on 9*5+5/60*y and the minute hand is on y. Because you're supposed to switch the hands, 6*5+5/60*x=y, and x=9*5+5/60*y. Substituting can give (6*5+5/60)(9*5+5/60*y)=y. Solving this will give y is about 34, and x would then be 48. Therefore the conference would start at [b]6:48[/b] and end at [b]9:34[/b]. You can check this by finding where the hands are. The only flaw is that at 6:48 the minute hand would be 18 degrees past 9, and the hour hand at 9:34 would be 17 degrees past 9. This is because we estimated for y.

Hope this helps.[/hide]


Hello Marylanders! Welcome to the new forum. The purpose of this is to allow us to share problem techniques and help prepare fo the ARML and MATHCOUNTS teams especially. I hope we will all have a chance to get to know each other, since I think this is supposed to be a virtual math club. I'm Edward and I go to Blair High School in Montgomery County. I'll be participating in ARML this year, I hope to see all of you. Please introduce yourselves also.

i''m smurfboy(my mom says i'm not allowed to share personal information) and i go to McDonogh...it's in owings mills.

I'm <personal information not allowed :P > and I'm going to Dulaney High as a freshman this fall. Anyone else from Baltimore County?

hello everyone

chuckzeduck... thanks to Eddy for allowing me to enter this community.

Hello Marylanders!  I just discovered this forum.  I am a Howard Area Homeschooler.  For MathCounts people, I was #5 at state in 2005 (#2 in Chesapeake Chapter).