function
irrational number
real analysis
real analysis unsolved

Does there exist a sequence of continuous positive functions $f_n$ on $R$ such that the sequence $[f_n(x)]$ is unbounded if and only if

 a) $x$ is irrational
 b) $x$ is rational

Where is Grobber's reply on this problem?  :?
Did you delete it, Grobber?  ;)

What I had written there was rather stupid :).

b) Take arbitrary $a_1=\frac{p_1}{q_1}\in \mathbb{Q}$. We can find $n_1$ and $\delta_1$ s.t. $|f_{n_1}(t)|\geq 1$ for all $t\in(a_1-\delta_1,a_1+\delta_1)=I_1$, $\overline{I_1}$ doesn't contain rational numbers with denominators $<q_1$. Choose arbitrary point $a_2=\frac{p_2}{q_2}\in I_1$ s.t. $q_2>2q_1$. We can find $n_2>n_1$ and $\delta_2$ s.t. $|f_{n_2}(t)|\geq 2$ for all $t\in(a_2-\delta_2,a_2+\delta_2)=I_2\subset I_1$ and $\overline{I_2}$ doesn't contain rational numbers with denominators $<q_2$. And so on.
Due to embedded segments theorem, $\cap \overline{I_k}\neq%Error. "varempty" is a bad command.
$, i.e. there is $s\in \cap \overline{I_k}$. It is clear $s$ can't be rational [b](!)[/b] and $f_n(s)$ is unbounded sequence.

Thank you!
I just wonder how to solve a)...

I guess the answer for a) is positive ( exist ), as in Riemann's function case :D

The question is not so easy...
I suspect that there is no such example... :?

Ops... It is an obvious thing...

Let $q_1$, $q_2$, ... be an enumeration of all rational numbers.
Define $f_1(x)\equiv 1$ and all remaining functions we will define recursively.
[b]Case 1.[/b] Suppose $q_i<q_n<q_j$, $i,j<n$ and $q_i$ and $q_j$ are the nearest such numbers to $q_n$. Then $f_n(x)=f_{n-1}(x)$ for all $x\not\in[q_i,q_j]$, $f_n(q_n)=n$ and define $f_n(x)$ on $[q_i,q_j]$ as it is described on Figure 1.
[b]Case 2.[/b] Suppose $q_n>q_i$ for $i<n$ (or $q_n<q_i$). Then again $f_n(x)\equiv f_{n-1}(x)$ on $(-\infty,q_i]$, $f_n(q_n)=n$ and define $f_n(x)$ on $(q_i,+\infty)$ as it is described on Figure 2.

Note that $f_m(q_n)= n$ for all $m\geq n$, so $f_n$ is bounded for all rational points. Moreover, it is clear that $f_n$ is unbounded for all irrational points!

Yahoooooo!!! :D

[quote="Myth"] Moreover, it is clear that $f_n$ is unbounded for all irrational points!

[/quote]

 I need you to explan a little more!! Many of my examples were trapped at that point :blush:
 By the way, what software did you use to draw that figure? :P

[quote="dickchimney"][quote="Myth"] Moreover, it is clear that $f_n$ is unbounded for all irrational points.[/quote]
I need you to explan a little more!! Many of my examples were trapped at that point :blush:[/quote]
For given irrational number $a$ we can find infinitely many rational approximations in following way: $q_{i_1}<q_{i_2}<q_{i_3}<...<a<...<q_{j_3}<q_{j_2}<q_{j_1}$, $i_1<i_2<...$, $j_1<j_2<...$. And with each new $q_{i_k}$ or $q_{j_k}$ value $f_n(a)$ will increase. Sorry, I don't know how to exlain it.
[quote]By the way, what software did you use to draw that figure? :P[/quote]
I use Geometr Sketchpad v.3.1. If you have v4.1 then you may send it to me :) I will be happy.

[quote="Myth"]
For given irrational number $a$ we can find infinitely many rational approximations in following way: $q_{i_1}<q_{i_2}<q_{i_3}<...<a<...<q_{j_3}<q_{j_2}<q_{j_1}$, $i_1<i_2<...$, $j_1<j_2<...$. And with each new $q_{i_k}$ or $q_{j_k}$ value $f_n(a)$ will increase. Sorry, I don't know how to exlain it.
[/quote]

 I think it is OK now!! Solved!! So you move it, and many other solved ones in this forum, please!! For this forum to be always fresh and new!!

[quote]I use Geometr Sketchpad v.3.1. If you have v4.1 then you may send it to me :) I will be happy.[/quote]

 I would be very happy if you send me your v.3.1 :D

The sets of points $A\subseteq \mathbb R$ for which there is a sequence of continuous functions $(f_n)_n$ (defined on the reals, with real values) s.t. $(f_n(x))_n$ is unbounded iff $x\in A$ are precisely the $G_\delta$ sets, I think.

To prove that if $(f_n)_n$ is a sequence of continuous functions as above, then the mentioned set is $G_\delta$. Let $A_{m,n}=\{x\in\mathbb R||f_n(x)|>m\},\ m,n\in\mathbb N$. Given $x\in\mathbb R$,  and $m\in\mathbb N$, there is an $n$ s.t. $|f_n(x)|>m$ iff $x\in\bigcup_n A_{m,n}$. $x$ belongs to our set iff the abopve is true for every $m$, and this is true iff $x\in\bigcap_m\left(\bigcup_n A_{m,n}\right)$. Since $A_{m,n}$ are open, $\bigcup_n A_{m,n}$ is open for all $m$, so $\bigcap_m\left(\bigcup_n A_{m,n}\right)$ is a $G_\delta$ set. In particular, since $\mathbb Q$ is not a $G_\delta$ set, this proves part (b).

I believe the converse to be true as well (and this would have (a) as a consequence, since $\mathbb R\setminus\mathbb Q$ is $G_\delta$), but my "solution" (I don't know if it's correct :)) is rather hard to explain. There's nothing fancy about it, but I have all sorts of sequences of intervals and I could easily get lost in all the indices used for the notations :).


analytic geometry
combinatorial geometry
geometry solved
geometry

Hi,

I can't remember the solution of the fifth exercise of the CG of 1998.

Let n be an integer greater than 2. Let A  a set of n points on R^2 such that any three points of A are not colinear.
Proove that it exists a set B of 2n-5 points of R^2 such that for any triangle formed with points of A contained a point of B.

Good luck

Fabrice

I love this one...  :)

Since $A$ is finite, there are only a finite number of directions determined by pair of points in $A$. Thus, we may choose an orthogonal system of coordinates such that the respective $x$-coordinate of the points are pairwise distincts.
Let $A_i (x_i,y_i)$, where $i=1, \cdots , n$ be the points with $x1 < x_j2 < \cdots < x_n$.

Let $d>0$ be the minimal distance between one of the points, say $A_i$ and a line $A_jA_k$ which does not contain $A_i$.
For each $i$, let $M_i, P_i$ be the two points with the same $y$-coordinate as $A_i$ and such that $A_iM_i = A_iP_i = \frac d 2.$

Now let $T = A_iA_jA_k$ be a triangle. Wlog, we may assume that $i < j < k$, so that one of the points $M_j,P_j$ is an interior point of $T$.

It follows that the set $B$ formed with the points $M_i,P_i$ has the desired property, but has cardinality $2n$.
Let $C$ be the convex hull of $A$. Note that $A_1,A_n$ are two vertices of $C$. Let $c$ be the number of vertices of $C$.
Thus, for each vertex of $C$ except $A_1$ and $A_n$, say $A_i$, only one of the points $M_i,P_i$ is interior to $A$ so that one of these points is never an interior point of the considered triangles. The same is true for both $M_1,P_1$ and both $M_n,P_n$.
Therefore, we may delete at least $c+2$ points from $B$ without loosing the desired property. Thus, we have found a set $B'$ with the desired property, and with $|B' | = 2n - c-2$.
Since $C$ is at least a triangle, we deduce that $c \geq 3$, so that $|B'| \leq 2n-5$, and we are done.

Pierre.

Some details :

1) CG means 'Concours Général'. It is perhaps the oldest (national) math competition in the world.
For years, it has been used as a IMO-TST in France.

2) If I'm not confusing, this problem comes from some ISL. It has been used in our CG just to test one candidate, namely Joseph Najnudel, who was at IMO and won a gold medal the preceding year. It turned that Najnudel did not solve this problem, but another candidate did and won the competition (I do not remember who, maybe Moubi does). So Najnudel qualified to IMO for his second year without winning the CG....and won another gold medal  :)

Pierre.


Find all positive integers $n$ with the following property: For every positive divisor $d$ of $n$, $d+1$ divides $n+1$.

Hopefully a correct [hide="solution"]Assume $n$ is composite: $n=kl$ where $k,l\geq 2$. Then $k+1|kl+1\land l+1|kl+1.$

We have ${{kl+1}\over{k+1}}=l-{{l-1}\over{k+1}}$ and ${{kl+1}\over{l+1}}=k-{{k-1}\over{l+1}}$. Hence, both ${{l-1}\over{k+1}}$ and ${{k-1}\over{l+1}}$ must be integer. But that's impossible since at least one of them is less than one: $k\leq l\implies {{k-1}\over{l+1}}\leq{{l-1}\over{l+1}}<1$ and $l\leq k\implies {{l-1}\over{k+1}}\leq{{k-1}\over{k+1}}<1$.

Hence, $n$ must be prime, which means that $2$ and $n+1$ must divide $n+1$. We conclude that this is satisfied for all odd primes and no other numbers.[/hide]

I think it`s right and very nice.
Thanks a lot


For all such things : http://www.mathlinks.ro/Forum/viewtopic.php?t=76610


geometry
3D geometry
ratio
similar triangles

A cone-shaped mountain has its base on the ocean floor and has a height of 8000 feet. The top $ \frac {1}{8}$ of the volume of the mountain is above water. What is the depth of the ocean at the base of the mountain in feet?

i did this using a lot of unnecessary algebra and want to know how to easily do it with setting up a proportion. I understand that from similar triangles, the ratio between the radii of two cones and their heights is constant, but how do I link this to get a proportion for the volume?

Because $ 8 \equal{} 2^3$, the top half of the cone would equal one eighth of the total volume. Thus the answer is $ \frac {8000}{2} \equal{} \boxed{4000}$.

I guess the question I have is how to relate the height based off the volume. How do you know that the height is the inverse cube of the volume?

This is a corollary off of similarity.

Think of the volume of a cube. If you double the side length of the cube, since the volume is $ s^3$, the volume increases by a factor of eight.

Basic rule: Side scaled by $ k \Leftrightarrow$ Area scaled by $ k^2\Leftrightarrow$ Volume scaled by $ k^3$.

ahh so in this problem, if we scale the radius and height by k, then the volume would be scaled by k^3. So the height (or radius for that matter) would be be the cube root of the volume's scalar.

Exactly.

A note: Do make sure that everything is scaled. If you double the radius, but do nothing to the height, the volume of the cone will increase by a factor of four. Similarly, doubling the height without doubling the radius increases the volume of the cone by a factor of two.

Yes. I agree with darkdieuguerre. Also, this goes the same with area. For example, doubling the side length of a square results in the area being multiplied by $ 2^2\equal{}4$.


Here are two questions I've found that was on the past amc 12 tests.
I do not understand how to get the answer to both, can someone explain it?
1). Points A and B are on the parabola y=4x^2+27x-1 and the origin is the midpoint of AB, what is the length of AB.
2). How many pairs of (x,y) can you make with the equation 2x+y=100

I am very confused on how to do those, the first answer turned out to be "five times the squareroot of two" and the second answer turned out to be 49.

Any ideas?

Thanks

for #2, you left out the "positive integers" restriction part of that question (sample q #1 at AMC site).
basically; pos integers=1, 2, 3, etc.
thus, x=1, y=98
x=2, y=96
etc till
x=49, y=2.  at this point, y goes to 0 for the next ordered pair (50,0), and since 0 is not a positive integer, it isnt counted as a valid ordered pair for this problem.  thus, there are 49 ordered pairs to it.

Are you sure about the coefficients in the parabola? I got $\sqrt{730}$.

Here's how:

If A is the point $(x,y)$, then since $0$ is the midpoint of A and B, B is the point $(-x,-y)$.

They must both satisfy the equation of the parabola.

$y = 4x^2 + 27x - 1$
$-y = 4(-x)^2 + 27(-x) -1$

Adding these two equations together gives

$0 = 8x^2 - 2$
$x^2 = 1/4$

We let $x$ be the positive value without loss of generality.

$x = 1/2$

Plugging this back in:

$y = 4(\frac 12 )^2 + 27 (\frac 12) - 1 = 1 + \frac{27}{2} -1 = \frac{27}{2}$

So the distance is $\sqrt{1^2 +27^2} = \sqrt{1+729} = \sqrt{730}$

I have understood the second question.
Thank you,
and You're right about the first question, I had typed it up wrong, it was 4x^2+7x-1  not 27 sorry about that.
I understood everything but the last part of the explanation.
Why do you have "squareroot of 1^2+27^2"? Where did you get the one from?

That would be the distance formula, which can also be thought of as the Pythagorean Theorem.

Just ignore my last comment, it was very silly of me to forget the distance formula!

Sry, heh

Thank you for helping! the explaination now makes a lot of sense!

[quote="Jo Moose"]2). How many pairs of (x,y) can you make with the equation 2x+y=100[/quote]

Assuming positive integers...

$y=100-2x$, and $x$ ranges from $1$ to $49$ (because $x=50$ makes $y=0$), so $\boxed {49}$ such ordered pairs.

[quote="Philip_Leszczynski"]Are you sure about the coefficients in the parabola? I got $\sqrt{730}$.

Here's how:

If A is the point $(x,y)$, then since $0$ is the midpoint of A and B, B is the point $(-x,-y)$.
[/quote]

well ..I suppose there are other values of A and B may satisfy the condition..
How about if A and B are in 4th and 2nd quadrant...say A is (x,-y) and B is (-x,y) ?

$x$ and $y$ aren't necessarily positive numbers.


function
logarithms
algebra
functional equation
algebra unsolved

1. Find all functions $f: \mathbb R \to \mathbb R$ such that for all reals $x$ and $y$,
\[ f(xy) \equal{} yf(x) \plus{} xf(y).\]
2. Find all functions $f: \mathbb R \to \mathbb R$ satisfying the following functional equation for every real number $x$:
\[ f(x) \plus{} \left(x \plus{} \frac {1}{2}\right)f(1 \minus{} x) \equal{} 1.\]
3. Find all functions$f: \mathbb R \to \mathbb R$ such that for all real numbers $x$ we have
\[ f(2x)\plus{}f(1\minus{}x) \equal{} 5x\plus{}9.\]

[quote="amparvardi"]$ 1$.Find all functions $ f: R\rightarrow R$ such that for every $ x,y$ from real numbers we have:
$ f(xy) \equal{} yf(x) \plus{} xf(y)$[/quote]

Let $ P(x,y)$ be the assertion $ f(xy)\equal{}yf(x)\plus{}xf(y)$

$ P(2,0)$ $ \implies$ $ f(0)\equal{}0$
$ P(x,x)$ $ \implies$ $ f(x^2)\equal{}2xf(x)$
$ P(\minus{}x,\minus{}x)$ $ \implies$ $ f(x^2)\equal{}\minus{}2xf(\minus{}x)$
So $ f(\minus{}x)\equal{}\minus{}f(x)$ $ \forall x\ne 0$ and so $ f(\minus{}x)\equal{}\minus{}f(x)$ $ \forall x$

Let then $ h(x)\equal{}e^{\minus{}x}f(e^x)$

So, $ \forall x>0$ : $ h(\ln(x))\equal{}\frac{f(x)}{x}$

So, $ \forall x\ne 0$ : $ h(\ln(|x|))\equal{}\frac{f(x)}{x}$ and $ f(x)\equal{}xh(\ln(|x|)$

Then the equation becomes $ xyh(\ln(|xy|)\equal{}xyh(\ln(|x|)\plus{}xyh(\ln(|y|)$ and so $ h(u\plus{}v)\equal{}h(u)\plus{}h(v)$ $ \forall u,v$ and so $ h(x)$ is any solution of Cauchy's equation.

And it is easy to check back that this indeed is a solution.

Hence the result :
Let $ h(x)$ be any solution of Cauchy's equation. Then :
$ f(0)\equal{}0$
$ f(x)\equal{}xh(\ln(|x|)$ $ \forall x\ne 0$

If you require continuity, then $ h(x)\equal{}ax$ and the only continuous solutions are $ ax\ln(|x|)$ (with continuous extension value $ 0$ at $ x\equal{}0$)

[quote="amparvardi"]problem $ 2$.find all functions $ f: R\rightarrow R$ satisfying the following functional equation:
$ f(x) + (x + \frac {1}{2})f(1 - x) = 1$   (for every real number $ x$)[/quote]

Let $ P(x)$ be the assertion $ f(x)+(x+\frac 12)f(1-x)=1$

$ P(1-x)$ $ \implies$ $ f(1-x)+(\frac 32-x)f(x)=1$

Multiplying this equality by $ (x+\frac 12)$, we get $ (x+\frac 12)f(1-x)+(x+\frac 12)(\frac 32-x)f(x)=x+\frac 12$

Subtracting $ P(x)$ from this equality implies $ (x+\frac 12)(\frac 32-x)f(x)-f(x)=x-\frac 12$

And so ${ \boxed{f(x)=\frac 2{1-2x}\forall x\ne\frac 12}}$ and $ P(\frac 12)$ $ \implies$ $ \boxed{f(\frac 12)=\frac 12}$

and this indeed is a solution (quick easy check)

[u][b]About problem 1[/b][/u], just point the parts you dont understand.

[quote="amparvardi"]problem $ 3$.find all functions $ f: R\rightarrow R$ such that for every real number $ x$ we have:
$ f(2x) \plus{} f(1 \minus{} x) \equal{} 5x \plus{} 9$[/quote]

First let us find a solution in the form $ ax\plus{}b$. A quick identification gives $ f(x)\equal{}5x\plus{}2$

Let then $ g(x)\equal{}f(x)\minus{}5x\minus{}2$ and we get $ g(2x)\plus{}g(1\minus{}x)\equal{}0$

Let then $ h(x)\equal{}g(x\plus{}\frac 23)$ and we get $ h(2(x\minus{}\frac 13))\plus{}h(\frac 13\minus{}x)\equal{}0$ and so $ h(2x)\equal{}\minus{}h(\minus{}x)$

As a consequence : $ h(4x)\equal{}h(x)$ and we get a general solution for $ h(x)$ :

Let $ u(x)$ any function defined over $ [0,1)$ :
$ \forall x>0$ : $ h(x)\equal{}u(\{\log_4(x)\})$
$ h(0)\equal{}0$
$ \forall x<0$ : $ h(x)\equal{}\minus{}h(\minus{}2x)\equal{}\minus{}u(\{\log_4(\minus{}2x)\})$

And the general solution of the requested equation is $ f(x)\equal{}5x\plus{}2\plus{}h(x\minus{}\frac 23)$ for any $ h(x)$ defined as above.

Once again, if you add continuity constraint, $ h(4x)\equal{}h(x)$ implies $ h(x)\equal{}c$ and then $ h(x)\equal{}0$ and the only continuous solution is $ 5x\plus{}2$


if a,b,c are non-negative no.s such that ab+bc+ca=3 ptove that
$ \frac{1}{a^2\plus{}2}\plus{}\frac{1}{b^2\plus{}2}\plus{}\frac{1}{c^2\plus{}2}$ $ \le$ $ 1$

[quote="sophie germain"]if a,b,c are non-negative no.s such that ab+bc+ca=3 ptove that
$ \frac {1}{a^2 \plus{} 2} \plus{} \frac {1}{b^2 \plus{} 2} \plus{} \frac {1}{c^2 \plus{} 2}$ $ \le$ $ 1$[/quote]
$ \sum_{cyc}\frac {1}{a^2 \plus{} 2}\leq1\Leftrightarrow\sum_{cyc}\left(1\minus{}\frac{2}{a^2\plus{}2}\right)\geq1\Leftrightarrow\sum_{cyc}\frac{a^2}{a^2\plus{}2}\geq1.$
But $ \sum_{cyc}\frac{a^2}{a^2\plus{}2}\geq\frac{(a\plus{}b\plus{}c)^2}{a^2\plus{}b^2\plus{}c^2\plus{}6}\equal{}1.$

[quote="sophie germain"]if a,b,c are non-negative no.s such that ab+bc+ca=3 ptove that
$ \frac {1}{a^2 \plus{} 2} \plus{} \frac {1}{b^2 \plus{} 2} \plus{} \frac {1}{c^2 \plus{} 2}$ $ \le$ $ 1$[/quote]

$ \Leftrightarrow a^2b^2\plus{}b^2c^2\plus{}c^2a^2 \plus{} a^2b^2c^2 \ge 4$

$ ab\equal{} x$ , $ bc \equal{} y$ , $ ca\equal{} z$;

$ x\plus{}y\plus{}z \equal{} 3$ ,$ q\equal{}xy\plus{}yz\plus{}zx  \le 3$ , $ r\equal{}xyz$ , (by Shur $ : r \ge \frac{4}{3}q\minus{}3$)

$ \Leftrightarrow r\plus{}9\minus{}2q \ge 6\minus{}\frac{2}{3}q \ge 4$;


limit
integration
function
Support
calculus
real analysis
absolute value

Let $f\in L^{1}(\mathbb{R})$ and $g$ be a bounded measurable function. Show that \[\lim_{n\to \infty}\int_{-\infty}^\infty g(x)\{f(x+1/n)-f(x)\}\,dx=0\] (The teacher give a hint to approximate $f$ by a continuous function)

Doesn't
$\int_{\mathbb{R}}f(x)=\int_{\mathbb{R}}f(x+1/n)$? So then the problem is obvious? Correctly if I am wrong

[quote="barra"]Doesn't
$\int_{\mathbb{R}}f(x)=\int_{\mathbb{R}}f(x+1/n)$? So then the problem is obvious? Correctly if I am wrong[/quote]

That's true. However, that doesn't tell you anything about
$\int_{\mathbb{R}}g(x)f(x) dx$ and $\int_{\mathbb{R}}g(x)f(x+1/n)dx$.
You do want to use your teacher's hint. You can just say that continuous functions are dense in $L^{1}(\mathbb{R})$ and prove it for continuous ones, if you're comfortable with that kind of argument. Alternatively, you can actually prove it directly for all $f \in L^{1}$ using Lusin's theorem, which says that an integrable function on a bounded set $E$ is continuous when restricted to $E \ G$, where $G$ is of arbitrarily small measure.

The latter method is my preferred method -- for some reason it helps my intuition for why things are true. ("Continuous functions are a dense subset" is too abstract for my small mind.)

The particular density you would want to use is that you could approximate $f$ by a continuous function [i]with compact support[/i].

Let $M=\|g\|_{\infty}=\text{ess }\sup |g(x)|.$

Suppose $\epsilon>0$ is given. Find a continuous, compactly supported function $h$ such that if we let $b(x)=f(x)-h(x),$ then $\|b\|_{1}\le\frac{\epsilon}{4M}.$

Suppose $\text{supp}(h)\subset [-a,a]$ Then $h$ is uniformly continuous on the interval $[-a-1,a+1]$ and zero outside that interval. Hence we can find $N$ such that if $n>N,$ then $|h(x+1/n)-h(x)|<\frac{\epsilon}{4(a+1)M}$ on the interval $[-a-1,a+1]$ and zero outside that interval.

Now suppose $n>N.$

$\left|\int_{-\infty}^{\infty}g(x)[f(x+1/n)-f(x)]\,dx\right|$

$\le \int_{\infty}^{\infty}|g(x)| |b(x+1/n)|\,dx+\int_{\infty}^{\infty}|g(x)| |b(x)|\,dx+$
$+\int_{-a-1}^{a+1}|g(x)| |h(x+1/n)-h(x)|\,dx$

$\le M\|b\|_{1}+M\|b\|_{1}+2(a+1)M\cdot\frac{\epsilon}{4(a+1)M}$

$<\frac{\epsilon}4+\frac{\epsilon}4+\frac{\epsilon}2= \epsilon.$

We have proved that given $\epsilon>0,$ there exists $N$ such that if $n>N,$ then the absolute value of the integral is less than $\epsilon.$ Hence, the limit is zero.

[quote="Kent Merryfield"]
Suppose $\text{supp}(h)\subset [-a,a]$ Then $h$ is uniformly continuous on the interval $[-a-1,a+1]$ and zero outside that interval. Hence we can find $N$ such that if $n>N,$ then $|h(x+1/n)-h(x)|<\frac{\epsilon}{4(a+1)M}$ on the interval $[-a-1,a+1]$ and zero outside that interval.

.[/quote]

Why $h$ uniformly continuous?? :blush:  :blush:

Can we deal with the continuous part as the following?
Suppose $f$ is continuous and $support\, f \subset [-a,a]$, then $f(x),f(x+1/n)$ are zero outside $[-a,a+1]$ and on this interval $\max |f(x)|=\max f(x+1/n): =K$ for every $n$.
Now $g\{f(x+1/n)-f(x)\}\leq 2K\|g\|_\infty\in L^{1}([-a,a+1])$ so by LDCT
$\lim_{n\to\infty}\int_{-\infty}^\infty g\{f(x+1/n)-f(x)\}=\lim\int_{[-a,a+]}g\{f(x+1/n)-f(x)\}=\int_{[-a,a+1]}\lim g\{f(x+1/n)-f(x)\}=0$

A continuous function on a compact set is uniformly continuous. That's why $h$ is uniformly continuous on $[-a-1,a+1].$ (Yes, I know we only need $[-a,a+1],$ but does it really matter? No.) Outside that interval, $h(x+1/n)-h(x)=0.$

Yes, you can use the Dominated Convergence Theorem as you've indicated. Note that you're using one of the other properties of a continuous function on a compact set: that it is bounded.


topology
real analysis
real analysis unsolved

Prove that $ [a,b)$ and $ (a,b)$ are not homeomorphic metric spaces?

The point $ a$ is special- it can be removed without disconnecting the space.


function
quadratics
pigeonhole principle

George encodes messages using functions that map certain letters onto other letters.  For example, the function $f(x) = x^{2}(\text{mod }27)$ would convert $T$ to $20$, square it to get $400$, and mod it by $27$ to get $22$ or $V$.

First George tries $f(x) = x^{2}(\text{mod }24)$ but this is not very good; $9$ distinct letters map onto $A$.
Of the 26 letters that can make up the encoded message, how many have more than one possible letter that they came from?

Next he tries $f(x) = x^{2}(\text{mod }27)$
Of the 26 letters that can make up the encoded message, how many have more than one possible letter that they came from?

Finally, he tries the function $f(x) = x^{3}(\text{mod }27)$
Of the 26 letters that can make up the encoded message, how many have more than one possible letter that they came from?

Is there supposed to be an elegant way of doing this, or are we supposed to slog out the quadratic (and cubic) residues of mod 27? :(

I know all of those aren't perfect since multiples of 3 squared and cubed give multiples of 9 and 27, so no letter will be turned into 3, 6, 12, 15, etc. and pigeonhole shows that there must be duplicate letters.


probability
geometry
vector
3D geometry
tetrahedron
dodecahedron

1. All of the faces of a polyhedron are congruent polygons.  This polyhedron has 2.5 times as many edges as faces and 3 faces meet at each vertex.  Determine the number of vertices of this polyhedron.

2. Let P be a point randomly chosen inside triangle ABC.  Find the probability that one of the three triangles ABP, APC, or PBC will have more area than half of ABC.

3. If x^2-5x+2 is divisible by 19 and 0<=x<=2013, find the number of possible values for x.

4. Hexagon HEXAGN is inscribed in a circle.  If angle H = 108, angle E=144, and angle X = 120 (all in degrees), find the measure of angle G.

2. It's 3/4. Let D, E, F are midpoints of BC, CA, AB respectively. the probability such that P inside one of AEF, BDF, CDE is 3/4.

[hide="Solution to first"]Consider the faces meeting at a vertex as vectors, and view the vertex from the direction of the sum of these vectors. Since there are three faces meeting here, each angle will appear to be 120 degrees (projected onto the plane of view). Hence, each angle appears to be 120 degrees, and is less than 120 degrees. Looking for solutions to 360 - 360/n < 120, we get that we must either have a perfect tetrahedron (n=3), cube (n=4), or dodecahedron (n=5).

Since there are 2.5 times as many edges as faces, the number of edges must be a multiple of 2.5, and thus of 5. This fails for n=3,4, so n=5 (dodecahedron).

There are 12 pentagons, 5 vertexes per pentagon, and 3 pentagon vertexes shared at each dodecahedron vertex (since there are 3 faces meeting at each vertex); thus the number of vertexes is $ \frac {12 \cdot 5}{3} \equal{} \boxed{20}$[/hide]

3:
[hide]

mod 19 x^2-5x+2 = x^2+14x+40 = (x+10)(x+4), so now we just need to find how many numbers congruent to 9 or 15 mod 19 less than 2013

106*19-1 =  2013, so thats 106*2 = 212 solutions.[/hide]

One could also do the first without actually figuring out what the polyhedron is:

[hide]Use Euler's Polyhedral Formula $ V \plus{} F \minus{} E \equal{} 2$.  3 faces meet at each vertex, so 3 edges meet at each vertex and $ E \equal{} \frac {3V}{2}$, while we're given that $ F \equal{} \frac {2E}{5}$.  Plugging these in gives $ V(1 \plus{} \frac {3}{2} \cdot \frac {2}{5} \minus{} \frac {3}{2}) \equal{} 2$, so $ V \equal{} 20$.[/hide]


Solve for $ a$ in the equation $ a^{ \minus{} 1} \plus{} b^{ \minus{} 1} \equal{} 5$

I think you meant $ a^{\minus{}1}\plus{}b^{\minus{}1}\equal{}5$. This is impossible to solve, unless it is in terms of b. That is becuase there are two variables with one equation.

We can multiply the equation by $ ab$ on both sides to reveal
$ 1 \plus{} 1 \equal{} 5ab$
$ 2 \equal{} 5ab$
$ \boxed{a \equal{} \frac {2}{5}b}$

Hope this answer helps and is what you were looking for.

This solution involves laws of exponents.  In case you did not know this, $ a^{ \minus{} 1} \equal{} \frac {1}{a}$

We can plug in this value for $ a$ in the equation to get
$ (\frac {2}{5}b)^{ \minus{} 1} \plus{} b^{ \minus{} 1} \equal{} 5$
$ \frac {5}{2b} \plus{} \frac {1}{b} \equal{} 5$
$ \frac {5}{2b} \plus{} \frac {2}{2b} \equal{} 5$
$ \frac {7}{2b} \equal{} \frac {5}{1}$
$ 10b \equal{} 7$
$ \boxed{b \equal{} \frac {7}{10}}$

Which should be the answer you are looking for.

EDIT:  This doesn't seem right, where did I go wrong?

I think there was a mistake in your first step.

$ \frac {1}{a} \plus{} \frac {1}{b} \equal{} 5$

Multiplying by $ ab$ you get:

$ b \plus{} a \equal{} 5ab$

This problem is similar to [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=278806]this[/url]. Read post number 7 (my post), which proves what I am doing. According to what I said there, here is the number of possible a's and b's:

$ 2(\text{number of factors of }5^2) \minus{} 1 \equal{} 2(\text{number of factors of }25) \minus{} 1 \equal{} 2(3) \minus{} 1 \equal{} 6 \minus{} 1 \equal{} \boxed{5}$

Note that this is assuming that a and b are integers.

Use distributive property:

$ ab\times(\frac {1}{a} \plus{} \frac {1}{b}) \equal{} ab\times\frac {1}{a} \plus{} ab\times\frac {1}{b} \equal{} \frac {ab}{a} \plus{} \frac {ab}{b} \equal{} b \plus{} a \equal{} a \plus{} b$

I am starting to suspect myself, because it is 1 to 2. Please show why it is not if it isn't.

oops, yeah i meant to have solve for a in terms of b
I'm pretty sure powerofpi is correct though, as the distributive property says $ ab(1/a \plus{} 1/b) \equal{} ab/a \plus{} ab/b \equal{} b \plus{} a$

EDIT:Got it now,  :wallbash_red: stupid mistake
anyways, shouldn't the answer be $ a\equal{}5ab\minus{}b$?
because $ 1/a\plus{}1/b\equal{}5$
$ ab/a\plus{}ab/b\equal{}5ab$
$ b\plus{}a\equal{}5ab$
$ a\equal{}5ab\minus{}b$

So we get $ a\plus{}b\equal{}5ab$. We assume that b is a constant.

$ b\plus{}a\equal{}5ba$
$ b\equal{}(5b\minus{}1)a$
$ \boxed{a\equal{}\frac{b}{5b\minus{}1}}$

I believe that is the answer.

ARGH! Another stupid mistake! :wallbash_red:  :wallbash_red:  :wallbash_red:
hmm...i think you are correct powerofpi, it appears i have overlooked one a
just to clarify, powerofpi "fused" two steps into one,
$ a \plus{} b \equal{} 5ab$
$ b \equal{} 5ab \minus{} a$
$ b \equal{} (5b \minus{} 1)a$
$ \boxed{a\equal{}\frac{b}{5b\minus{}1}}$

no, i just thought i would add it
the question is from an online test that gives an answer but no solution.
I originally made a stupid mistake and did not recognize the step to multiply "ab" to everything.


algebra
function
domain
linear algebra
matrix
parameterization

I have been asked to find the dim of the image and null space of the subspace of F^4 in mod 5 defined by the following equations:

4w+3x+3y+2z=0
2w+x+4y+2z=0
w+3x+3z=0

but I'm not really sure what I'm doing. I know Its got something to do with matrices, and i can prove something( not sure whether its the domain, im or null space) is linearly independent. I'm a bit lost past that though.

Oh dear.

Can anyone help?

We're trying to find the rank and the nullity of the following matrix:

$ \begin{bmatrix}4&3&3&2\\2&1&4&2\\1&3&0&3\end{bmatrix}.$

The basic tool for this is Gaussian elimination. We just have to remember that we're doing all of our arithmetic $ \mod{5}.$ Before I start, let me write that upper left corner element as $ \minus{}1$ instead of $ 4$ - notationally, that makes things easier.

Add $ 2$ times the first row to the second row, and add $ 1$ times the first row to the third row:

$ \begin{bmatrix}\minus{}1&3&3&2\\0&2&0&1\\0&1&3&0\end{bmatrix}.$

Now add $ 2$ times the second row to the third row.

$ \begin{bmatrix}\minus{}1&3&3&2\\0&2&0&1\\0&0&3&2\end{bmatrix}.$

This is now in row echelon form. There are three pivots - a pivot in every row. The column space, or image, of this matrix is three dimensional, which means all of $ \mathbb{F}_5^3.$ There is one column without a pivot (the fourth column, as I've written it). That means that we could find a one-parameter family of members of the null space (the solution space for the homogeneous equation), meaning that the null space is one-dimensional. The null space is a one dimensional subspace of the domain, and the domain is $ \mathbb{F}_5^4.$

The rank-nullity theorem in this case:

$ (\text{rank})\plus{}(\text{nullity})\equal{}(\text{number of columns})$

$ 3\plus{}1\equal{}4.$

Thats fantastic, thankyou. It's really cleared it up for me  :D


Evo stogod (nadam se korisnog) za one koji se ove godine pripremaju za drzavna takmicenja kao i olimpijade. Zadaci i rjesenja drzavnog takmicenja BiH 2004. Ako jos neko ima slicnih biltena dobro bi bilo da ih objavi.

Samo BiH ili ne?
Ako ne, srpska takmicenja su na
http://www.dms.org.yu
http://www.srb.imomath.com

Ponesto od hrvatskih natjecanja:

http://e.math.hr/natjecanja/index.html

P. S. Ako sta nadjem od bh biltena kod kuce, okacit cu... Mada sto sam imao od zadataka vec je na srb.imomath.com

Hvala za linkove

Mislio sam na bilo koje od takmicenja sa Former Yogoslavia teritorije Sva nasa drzavna (osim 2007.) mogu se naci na internetu ali samo zadaci na engleskom dok je npr. dosta tesko naci Federalna takmicenja a pogotovo Republicka iz RSa (bar ja ne uspijevam da nadjem).

Evo i bilten naseg proslogodisnjeg Federalnog takmicenja.

Evo iz Hrvatske nešto, ne znam ni sam što sve tamo ima:

http://www.mioc.hr/other/matematika/ (Ovako odoka, mislim da su tu općinska 1996.-2004., državna 1995.-2005. i županijska 1994.-2006. bez 1995. sa rješenjima)

http://playmath.petagimnazija.hr/pripreme05/ (Pripreme ekipe za IMO 2005.: Tulumi, TMOK-ovi (Testovi matematičke opće kulture  :D) i HMO, oba dana)

Da nema neko možda tu 2007. (BiHMO)? Vjerujem da imaju Salem i Harun, pa ako nije problem...  :lol:

Ja vjerujem da imam negdje kuci (u Zenici) to, pa ako mozes sacekati vikend...  :lol:


quadratics
modular arithmetic
algebra
number theory unsolved
number theory

Find all positive integers such that:
\[ 8{a^2} \plus{} 10a \plus{} 3\equal{}b^2\]

[quote="Theorem1"]Find all positive integers such that:
\[ 8{a^2} \plus{} 10a \plus{} 3 \equal{} b^2
\]
[/quote]
This equation may be written $ u(2u\plus{}1)\equal{}b^2$ with $ u\equal{}2n\plus{}1$

Since $ u$ and $ 2u\plus{}1$ are coprime, this implies $ u\equal{}x^2$ and $ 2u\plus{}1\equal{}y^2$ and so $ 2x^2\plus{}1\equal{}y^2$ but this implies $ x$ even (looking at the equation mod $ 4$), so no solution.

[quote="pco"][quote="Theorem1"]Find all positive integers such that:
\[ 8{a^2} \plus{} 10a \plus{} 3 \equal{} b^2
\]
[/quote]
This equation may be written $ u(2u \plus{} 1) \equal{} b^2$ with $ u \equal{} 2n \plus{} 1$

Since $ u$ and $ 2u \plus{} 1$ are coprime, this implies $ u \equal{} x^2$ and $ 2u \plus{} 1 \equal{} y^2$ and so $ 2x^2 \plus{} 1 \equal{} y^2$ but this implies $ x$ even (looking at the equation mod $ 4$), so no solution.[/quote]
Also we can conclude that there is no solution because:
$ (2a \plus{} 1)(4a \plus{} 3) \equal{} 8b^2$
but $ LHS \equal{} odd,RHS \equal{} even$, contradiction....

Also we can solve it like a quadratic equation in a. As you are solving it in integers - the discriminant will be a square of some integer and you will get:
$ 32b^{2} \equal{} (k \minus{} 2)(k \plus{} 2)$ and that easily yields no positive solutions as we will get $ b \equal{} 1$ and $ a \equal{} \minus{} 1$

[quote="pco"][quote="Dimitris X"] Also we can conclude that there is no solution because:
$ (2a \plus{} 1)(4a \plus{} 3) \equal{} 8b^2$
but $ LHS \equal{} odd,RHS \equal{} even$, contradiction....[/quote]

I dont understand. We have $ (2a \plus{} 1)(4a \plus{} 3) \equal{} b^2$, not $ (2a \plus{} 1)(4a \plus{} 3) \equal{} 8b^2$[/quote]
Yes, i made a mistake :oops: :
My solution(same as pco i think):
$ (2a \plus{} 1)(4a \plus{} 3) \equal{} b^2$
But $ (2a \plus{} 1,4a \plus{} 3) \equal{} 1$,so there exist $ x,y$ such that:
$ 2a \plus{} 1 \equal{} x^2$ and $ 4a \plus{} 3 \equal{} y^2$
By $ 2a \plus{} 1 \equal{} x^2$,$ x$ is odd,so $ x^2 \equal{} 8k \plus{} 1$.
So $ a \equal{} 4k$.But we can easily see that in order to be right the first it must be $ a \equiv 1 (mod 4)$,which is a contradiction....
Thank you for pointing out my careless mistake pco.

[quote="Theorem1"]Find all positive integers such that:
\[ 8{a^2} \plus{} 10a \plus{} 3 \equal{} b^2
\]
[/quote]

$ 8(8a^2\plus{}10a\plus{}3)\equal{}8b^2$ that is $ (8a\plus{}5)^2\equal{}2(2b)^2\plus{}1$ but $ (\frac{\minus{}2}{p})\equal{}1$ iff $ p\equal{}1 \text{ or }3 \pmod 8$ that is absurd.


For $a,b,c$ positive reals prove that

$\frac{a^2+b^2}{a+b}+\frac{b^2+c^2}{b+c}+\frac{c^2+a^2}{c+a} \leq \frac{3(a^2+b^2+c^2)}{a+b+c}$

Proof without words, following Harazi's footsteps:

$3\frac{a^{2}+b^{2}+c^{2}}{a+b+c}-\left( \frac{b^{2}+c^{2}}{b+c}+\frac{c^{2}+a^{2}}{c+a}+\frac{a^{2}+b^{2}}{a+b}\right) $
$=\left( \frac{a^{2}+b^{2}+c^{2}}{a+b+c}-\frac{b^{2}+c^{2}}{b+c}\right) +\left( \frac{a^{2}+b^{2}+c^{2}}{a+b+c}-\frac{c^{2}+a^{2}}{c+a}\right) +\left( \frac{a^{2}+b^{2}+c^{2}}{a+b+c}-\frac{a^{2}+b^{2}}{a+b}\right) $
$=\frac{ab\left( a-b\right) +ac\left( a-c\right) }{\left( b+c\right) \left( a+b+c\right) }+\frac{bc\left( b-c\right) +ba\left( b-a\right) }{\left( c+a\right) \left( a+b+c\right) }+\frac{ca\left( c-a\right) +cb\left( c-b\right) }{\left( a+b\right) \left( a+b+c\right) }$
$=\frac{ab\left( a-b\right) }{\left( b+c\right) \left( a+b+c\right) }+\frac{ac\left( a-c\right) }{\left( b+c\right) \left( a+b+c\right) }+\frac{bc\left( b-c\right) }{\left( c+a\right) \left( a+b+c\right) }+\frac{ba\left( b-a\right) }{\left( c+a\right) \left( a+b+c\right) }$
$+\frac{ca\left( c-a\right) }{\left( a+b\right) \left( a+b+c\right) }+\frac{cb\left( c-b\right) }{\left( a+b\right) \left( a+b+c\right) }$
$=\left( \frac{bc\left( b-c\right) }{\left( c+a\right) \left( a+b+c\right) }+ \frac{cb\left( c-b\right) }{\left( a+b\right) \left( a+b+c\right) }\right) +\left( \frac{ca\left( c-a\right) }{\left( a+b\right) \left( a+b+c\right) }+ \frac{ac\left( a-c\right) }{\left( b+c\right) \left( a+b+c\right) }\right) $
$+\left( \frac{ab\left( a-b\right) }{\left( b+c\right) \left( a+b+c\right) }+ \frac{ba\left( b-a\right) }{\left( c+a\right) \left( a+b+c\right) }\right) $
$=\frac{\left( b-c\right) ^{2}bc}{\left( a+b+c\right) \left( c+a\right) \left( a+b\right) }+\frac{\left( c-a\right) ^{2}ca}{\left( a+b+c\right) \left( a+b\right) \left( b+c\right) }+\frac{\left( a-b\right) ^{2}ab}{\left( a+b+c\right) \left( b+c\right) \left( c+a\right) }$
$\geq 0$.

  Darij


inequalities
absolute value
inequalities open

$prove\ that\ for\ positive\ reals\ x,y,z\ \ we\ have\ the\ following\ inequality\ true\ :-$
\[x^{2}+y^{2}+z^{2}\ge \sum_{\substack{cyc}}\frac{x^{4}+y^{4}+64(\sqrt{x^{5}y^{3}}+\sqrt{x^{3}y^{5}})-70x^{2}y^{2}}{20(x^{2}+y^{2}+xy)}\ge xy+yz+zx\]
$please\ also\ tell\ whether\ the\ above\ inequality\ is\ also\ true\ for\ real\ x,y,z$

Prove that for positive reals $x,y,z$:
\[x^{2}+y^{2}+z^{2}\ge \sum_{\substack{cyc}}\frac{x^{4}+y^{4}+64(\sqrt{x^{5}y^{3}}+\sqrt{x^{3}y^{5}})-70x^{2}y^{2}}{20(x^{2}+y^{2}+xy)}\ge xy+yz+zx \]
Does it holds for all reals?

edit: how could it holds for all reals, since $\sqrt{x^{5}y^{3}}$ is undefined when $0$ lies between $x,y$ and likewise for the rest, thus either all above 0 or all below. But these two cases are the exact same...

Would you substitute absolute value signs?

you are right . if we remove the  underroots by substitution
\[\sqrt{x}=a \ etc\]
then it holds for real a,b,c with condition of no two being 0.


Let  {x[n]} be a sequence of positive integers satisfying

x[1] = 1, and x[n] < x[n + 1] < 2n + 1 for n = 1, 2, ...

Prove that for all integers k, one can find indices r and s such that x[r] - x[s] = k.

It is a classical pigeon-hole one, am I right?

Let $k>0$ be given.
We have $x_{k+1} \leq 2k$. Thus, $x_1, \cdots , x_{k+1}$ are pairwise distinct and each of them is in $\{1, \cdots , 2k \}$.
In another hand, since we have $k+1$ integers, the pigeon-hole principle ensures us that there are two integers $1 \leq s<r \leq k+1$ such that $x_r-x_s = 0 \mod[k].$
Since $0 < x_r - x_s \leq 2k - 1 < 2k$ it follows that $x_r - x_s = k$ and we are done.

Pierre.


algebra
IMO Shortlist
Divisors
number theory
primes

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]  :)

[b]Lemma 1[/b]: If $(a,b)=1$ and $a,b$ are odd, then $(2^a+1,2^b+1)=3$.

[b]Proof[/b]: Let $d=(2^a+1,2^b+1)$. $3|d$ and $d|(2^{2a}-1,2^{2b}-1)=2^{(2a,2b)}-1=2^2-1=3$, so $d=3$. $\blacksquare$

[b]Lemma 2[/b]: If $3\not |a$ ($a$ is odd), then $9\not |2^a+1$.

[b]Proof[/b]: If $a=3k+1$ we have $2^a+1=2(2^{3k}+1)-1=9t-1$, and if $a=3k+2$ we have $2^a+1=4(2^{3k}+1)-3$. $\blacksquare$

Let $N=p_1\ldots p_n,\ N'=\frac N{p_n}$.

For $n=1$, the result is easy to prove: $2^p+1$ has the divisors $1, 3, \frac{2^p+1}3, 2^p+1$. We have $3\ne \frac{2^p+1}3$ because $p>3$. We can now use induction. Assume we have shown it for $n-1$. This means that $2^{N'}+1$ has at least $4^{n-1}$ divisors. We have $2^{N'}+1|2^N+1,\ \frac{2^{p_n}+1}3|2^N+1$, and we can apply the lemmata for $a=p_n, b=N'$ to get $\frac{2^{p_n}+1}3\big|\frac{2^N+1}{2^{N'}+1}$. On the other hand, we clearly have $\left(\frac{2^{p_n}+1}3\right)^2<\frac{2^N+1}{2^{N'}+1}$, which means that $\frac{2^N+1}{2^{N'}+1}$ has at least four divisors $1=d_1,d_2,d_3,d_4$. For each $d|2^{N'}+1$, each of $d_id$ is a divisor of $2^N+1$, and all $d_id$ are different because $(d_i,d)=1$, hence the result: $2^N+1$ has at least $4\cdot 4^{n-1}=4^n$ divisors.

Remark on the solution for this problem in one book says that it can be proved with cyclotomic polynomials that number $ 2^{p_1...p_n} \plus{} 1$ has at least $ 2^{2^{n\minus{}1}}$ divisors, which is larger than $ 4^n$.
Can someone please try to solve it in that way?

Tnx

Consider $ 2^{mn} \plus{} 1 \equal{} (2^n \plus{} 1)(2^{n(m \minus{} 1)} \minus{} 2^{n(m \minus{} 2)} \plus{} ... \plus{} 1) \equal{} PQ,Q \equal{} m\mod P \equal{} 2^n \plus{} 1$.
In these way we can prove, that for any odd m>3 exist prime p, suth that $ p|2^m \plus{} 1$ and $ p|2^n \plus{} 1\to m|n.$
Therefore for your case (any primes greater 3 we had $ N\ge 2^n$ disdinct primes $ p_k|2^m \plus{} 1, m \equal{} p_1p_2...p_n$ (one for any divisor m). Therefore number of divisors $ 2^m \plus{} 1 \equal{} p_1^{k_1}....p_N^{k_N}$ equal $ (k_1 \plus{} 1)...(k_N \plus{} 1)\ge 2^{2^n}$.
If one of odd primes in $ m\equal{}p_1...p_n$ is equal 3, then number of divisors $ 2^m\plus{}1$ greater or equal $ 3*2^{2^n\minus{}2}$.

[quote="SpongeBob"]Remark on the solution for this problem in one book says that it can be proved with cyclotomic polynomials that number $ 2^{p_1...p_n} \plus{} 1$ has at least $ 2^{2^{n \minus{} 1}}$ divisors, which is larger than $ 4^n$.
Can someone please try to solve it in that way?

Tnx[/quote]

Let $ \prod_{i \equal{} 1}^{n} p_i \equal{} P$.  Then

$ 2^P \plus{} 1 \equal{} \prod_{d | P} \Phi_{2d} (2)$.

$ P$ has $ 2^n$ divisors $ d$, hence there are $ 2^n$ factors on the RHS.

Consider two divisors $ a, b$ of $ P$.  We have

$ \gcd(2^{2a} \minus{} 1, 2^{2b} \minus{} 1) \equal{} 2^{2\gcd(a, b)} \minus{} 1$.

Now, the RHS can be written as a product of cyclotomic polynomials $ \Phi_{2d} (2)$ where $ d | \gcd(a, b)$.  In particular, unless $ a | b$ we know that $ d < a, d < b$.  Therefore

$ \gcd(\Phi_{2a}(2), \Phi_{2b}(2)) \equal{} 1$.

We should be able to conclude from here that $ P$ has at least $ 2^{n \minus{} 1}$ distinct prime factors, but I'm afraid I don't see the argument :(

Edit:  But of course!  If $ a | b$ then $ \Phi_{2a}(2), \Phi_{2b}(2)$ are both factors of

$ 2^{2b} \minus{} 1 \equal{} (2^b \minus{} 1)(2^b \plus{} 1)$

where $ \gcd(2^b \minus{} 1, 2^b \plus{} 1) \equal{} 1$ and $ \Phi_{2a}(2) | 2^b \minus{} 1, \Phi_{2b}(2) | 2^b \plus{} 1$, hence it is still true that $ \gcd(\Phi_{2a}(2), \Phi_{2b}(2)) \equal{} 1$.  Hence $ P$ has at least $ 2^n$ distinct prime factors as Rust has stated.  :)

I think this works. We'll show that the desired number has at least $ 2n$ distinct prime factors, and thus at least $ 2^{2n} \equal{} 4^{n}$ factors. We induct on $ n$, the base case is easy, since $ 2^{p_{1}} \plus{} 1$ has two prime factors, 3 and something else. Assume it's proven for $ n \minus{} 1$, and let $ A \equal{} p_{1}p_{2}\cdots p_{n \minus{} 1}$, $ p \equal{} p_{n}$.

$ 2^{Ap} \plus{} 1 \equal{} (2^{A} \plus{} 1)(2^{A(p \minus{} 1)} \minus{} 2^{A(p \minus{} 2)} \plus{} \cdots \plus{} 1)$.

$ 2^{A} \plus{} 1$ contributes $ 2(n \minus{} 2)$ distinct prime factors by induction hypothesis. We need to show the second factor contributes 2 others. We can repeatedly apply the Euclidean Algorithm to get that the GCD of the two factors is $ (2^{A} \plus{} 1,p)$, which is either 1 or $ p$. First, consider what happens when it's 1. It suffices to show that the second factor is composite. Using grobber's lemma, $ (2^{A} \plus{} 1,2^{p} \plus{} 1) \equal{} 3$, so $ (2^{p} \plus{} 1)/3$ divides the second factor (as it divides the whole thing). Now, once we divide out $ (2^{p} \plus{} 1)/3$ from the second factor, we'll be left with an integer something bigger than 1* relatively prime to the first factor, which will give us another prime factor. Thus, we have two new prime factors, the new one from $ (2^{p} \plus{} 1)/3$ and the new one from the second factor divided by $ (2^{p} \plus{} 1)/3$.

*To see this, the second factor is equal to $ (2^{p} \minus{} 1)(2^{A(p \minus{} 2)} \plus{} 2^{A(p \minus{} 4)} \plus{} \cdots \plus{} 2^{A}) \plus{} 1 \equal{} 2^{A}(2^{p} \minus{} 1)(mess) \plus{} 1 > 2^{p} \plus{} 1$.

So the other case is if the gcd is $ p$. Stuff basically works the same, we now instead of to take out $ p(2^{p} \plus{} 1)/3$. Note that $ 2^{p} \plus{} 1\equiv 3\pmod{p}$ and $ p > 3$ so $ (p,2^{p} \plus{} 1) \equal{} 1$. By similar logic from before, $ (2^{p} \plus{} 1)/3$ divides the whole second factor, giving us a new prime factor, and when we divide out $ p(2^{p} \plus{} 1)/3$, we get something bigger than 1 relatively prime to the first factor, giving us another new prime factor, because

$ (2^{p} \minus{} 1)(2^{A(p \minus{} 2)} \plus{} 2^{A(p \minus{} 4)} \plus{} \cdots \plus{} 2^{A}) \plus{} 1 \equal{} 2^{A}(2^{p} \minus{} 1)(mess) \plus{} 1 > 2^{A \plus{} p} > 2^{p \plus{} 2} > p(2^{p \plus{} 1}) > p(2^{p} \plus{} 1)$.

Sorry if that was hard to follow. If someone finds a hole let me know.

[quote="CatalystOfNostalgia"]INow, once we divide out $ (2^{p} \plus{} 1)/3$ from the second factor, we'll be left with an integer something bigger than 1* relatively prime to the first factor, which will give us another prime factor. Thus, we have two new prime factors, the new one from $ (2^{p} \plus{} 1)/3$ and the new one from the second factor divided by $ (2^{p} \plus{} 1)/3$.

[/quote]

How do you know that the second prime factor isn't the same as the first? For example, we could have something like $ ((2^{p} \plus{} 1)/3)^2$, then dividing $ (2^{p} \plus{} 1)/3$ won't give you a [i]new[/i] prime factor. You can fix this by saying if $ q|(2^{p} \plus{} 1)/3$ then $ 2^{A(p\minus{}1)}\minus{}2^{A(p\minus{}2)}\plus{}\cdots\plus{}1$ is not divisible by $ q^3$, and $ 2^{A(p\minus{}1)}\minus{}2^{A(p\minus{}2)}\plus{}\cdots\plus{}1>((2^{p} \plus{} 1)/3)^2$. Then you can have a new prime factor.

Also you can eliminate the second case by assuming $ p$ is the smallest among all primes in the exponents. If $ 2^{Ap}\equiv \minus{}1(p)$, then $ 2^{(2Ap, p\minus{}1)}\equiv 1(P)$. But $ (2Ap, p\minus{}1)\equal{}2$ and $ p>3$. So $ (2^A\plus{}1, 2^{A(p\minus{}1)}\minus{}2^{A(p\minus{}2)}\plus{}\cdots\plus{}1)\equal{}1$

[quote="nealth"] if $ q|(2^{p} \plus{} 1)/3$ then $ 2^{A(p \minus{} 1)} \minus{} 2^{A(p \minus{} 2)} \plus{} \cdots \plus{} 1$ is not divisible by $ q^3$[/quote]

Thanks for pointing this out -- but how come this is true? (I know you're at MOP, but if anyone can answer this...)

[quote="t0rajir0u"][quote="SpongeBob"]Remark on the solution for this problem in one book says that it can be proved with cyclotomic polynomials that number $ 2^{p_1...p_n} \plus{} 1$ has at least $ 2^{2^{n \minus{} 1}}$ divisors, which is larger than $ 4^n$.
Can someone please try to solve it in that way?

Tnx[/quote]

Let $ \prod_{i \equal{} 1}^{n} p_i \equal{} P$.  Then

$ 2^P \plus{} 1 \equal{} \prod_{d | P} \Phi_{2d} (2)$.

$ P$ has $ 2^n$ divisors $ d$, hence there are $ 2^n$ factors on the RHS.

Consider two divisors $ a, b$ of $ P$.  We have

$ \gcd(2^{2a} \minus{} 1, 2^{2b} \minus{} 1) \equal{} 2^{2\gcd(a, b)} \minus{} 1$.

Now, the RHS can be written as a product of cyclotomic polynomials $ \Phi_{2d} (2)$ where $ d | \gcd(a, b)$.  In particular, unless $ a | b$ we know that $ d < a, d < b$.[/quote]

I think the previous two sentences should be "Now, the RHS can be written as a product of cyclotomic polynomials $ \Phi_{d} (2)$ where $ d | 2\gcd(a, b)$.  In particular, unless $ a | b$ we know that $ d < 2a, d < 2b$."

[quote="t0rajir0u"]  Therefore

$ \gcd(\Phi_{2a}(2), \Phi_{2b}(2)) \equal{} 1$.

We should be able to conclude from here that $ P$ has at least $ 2^{n \minus{} 1}$ distinct prime factors, but I'm afraid I don't see the argument :(

Edit:  But of course!  If $ a | b$[/quote]

and $a\neq b$

[quote="t0rajir0u"] then $ \Phi_{2a}(2), \Phi_{2b}(2)$ are both factors of

$ 2^{2b} \minus{} 1 \equal{} (2^b \minus{} 1)(2^b \plus{} 1)$

where $ \gcd(2^b \minus{} 1, 2^b \plus{} 1) \equal{} 1$ and $ \Phi_{2a}(2) | 2^b \minus{} 1, \Phi_{2b}(2) | 2^b \plus{} 1$,[/quote]

I don't understand why $ \Phi_{2a}(2) | 2^b \minus{} 1, \Phi_{2b}(2) | 2^b \plus{} 1$.

[quote="t0rajir0u"] hence it is still true that $ \gcd(\Phi_{2a}(2), \Phi_{2b}(2)) \equal{} 1$.  Hence $ P$ has at least $ 2^n$ distinct prime factors as Rust has stated.  :)[/quote]

Also, you must prove that $\Phi_{2d}\left(2\right)>1$ for every positive integer $d$. Fortunately this is a known fact (geometrically more or less evident by drawing the regular $2d$-gon in the unit circle).

Solution :
$N=2^{p_1p_2*...*p_k}+1=\prod_{d | p_1p_2*...*p_k}\Phi_{2d}(2)$
Use next Lemma :
If for integer number x $\gcd(\Phi_{m}(x),\Phi_{m}(x))>1$ , then $\frac{n}{m}=p^{\lambda}$ , for integer $\lambda$
So if $k$ is odd then easy to see that if $a|p_1p_2*...*p_k$ , then if $b=\frac{p_1p_2*...*p_k}{a}$ , then $a$ , or $b$ has odd prime divisors from (p_1,p_2,...,p_k) , and number of such numbers is $2^{k-1}$ , if $k$ is even , then number of numbers $a|p_2p_3*...*p_k$ , were $a*p_1$ has odd number of prime divisors from (p_1,p_2,...,p_k) is $2^{k-2}$ and number of numbers $b|p_2p_3*...*p_k$ , were $b$ has odd number of prime divisors from (p_2,...,p_k) is $2^{k-2}$ , so number of numbers $c|p_1p_2p_3*...*p_k$ , were $c$ has odd number of prime divisors from (p_1,p_2,...,p_k) is $2^{k-2}+2^{k-2}=2^{k-1}$ , so take this $2^{k-1}$ numbers $x_1,x_2,...,x_{2^{k-1}}$ , and $\frac{x_i}{x_j}\neq p^{\lambda}$ , so $\gcd(\Phi_{x_i}(2),\Phi_{x_j}(2))=1$ , so $2^{p_1p_2*...*p_k}+1$ has at least $2^{2^{k-1}}$ divisors . done

We will prove that by induction, showing that the expression has at least $2n$ distinct prime divisors, which would show the problem.

Base Case: $2^{p_1}+1$ is divisible by $3$ and an other prime.

Inductive Case: Let $a=p_1p_2\cdots p_n$, and $b=p_{n+1}$.

[b]Lemma 1:[/b] The $gcd(2^x+1,2^y+1)=3$ for relatively prime positive odd integers $x,y$, where $3$ does not divide either.

[b]Proof: [/b] Let $p$ be a prime dividing both expressions. Then $ord_p(2)|gcd(2x,2y)$ or since $x,y$ are odd, $2^x+1\equiv 2+1\equiv 3\pmod{p}$. Thus $p=3$, using LTE to show that $9$ does not divide either.
-----------------------

[b]Lemma 2:[/b] The expression $\frac{3(2^{ab}+1)}{(2^a+1)\cdot (2^b+1)}$ has a prime divisor relatively prime to both $2^a+1$ and $2^b+1$ where $a,b$ are relatively prime positive odd integers.

[b]Proof:[/b] Note that since $2^a+1,2^b+1$ are relatively prime except for one factor of $3$ by lemma 1 and LTE, thus we know that $\frac{3(2^{ab}+1)}{(2^a+1)\cdot (2^b+1)}$ is an integer.

Now, we have cases based on the whether the expressions for $2^a+1$ and $2^b+1$ are relatively prime to $\frac{3(2^{ab}+1)}{(2^a+1)\cdot (2^b+1)}$. The proof for the case where both are is immediate, and the other three are proved in the same way as the case where both are not.

Let $p|2^a+1$. Note that $\frac{2^{ab}+1}{2^a+1}\equiv -b\pmod{p}$, and since $b$ is prime, $p=b$ for divisibility and the only prime factor $\frac{2^{ab}+1}{2^a+1}$ and $2^a+1$ can share is $b$. By LTE, $v_b(2^{ab}+1)=v_b(2^a+1)+1$, thus $v_b(\frac{2^{ab}+1}{2^a+1})=1$.

Let $p|2^b+1$. Then $\frac{2^{ab}+1}{2^b+1}\equiv -a\pmod{p}$. Then all the primes both can share divide $a$ and we can use LTE to show that $v_{p_i}(\frac{2^{ab}+1}{2^b+1})=1$. Let $gcd(\frac{2^{ab}+1}{2^b+1}, 2^b+1)=k$.

We have that

\[\frac{3(2^{ab}+1)}{b\cdot (2^a+1)\cdot (2^b+1)\cdot k}\ge\frac{3(2^{ab}+1)}{b\cdot (2^a+1)\cdot (2^b+1)\cdot a}> 1\]

Then $\frac{3(2^{ab}+1)}{b\cdot (2^a+1)\cdot (2^b+1)\cdot k}$ is relatively prime to $2^a+1,2^b+1$ and has a prime divisor distinct from those in $2^a+1,2^b+1$.
----------------------

Now, to the problem, when we "add" $b$ to the exponent we have that $2^{ab}+1$ has a prime divisor added from $2^b+1$ by lemma 1 not in $2^a+1$. However, $\frac{3(2^{ab}+1)}{(2^a+1)\cdot (2^b+1)}$ "adds" another prime divisor to $2^{ab}+1$ and we obtain at least two new prime divisors. Thus our inductive step is complete.

Applying Zsigmondy's Theorem $2^{p_1p_2\ldots p_n}+1$ has atleast $2^n$ distinct prime factors.
Because we can induct on $n$ and as $2k+1\mid 2m+1\implies 2^{2k+1}+1\mid 2^{2m+1}+1$ we get more $2^n$ factors, hence its true. For the base case $2^p+1$ has a factor distinct from $2^1+1=3$.

Note that the exceptional case of $2^3+1$ never happens as all primes are greater than $3$.

Thus it has $\ge 2^{2^n}$ distinct factors.

Without loss of generality let $p_1<p_2<...<p_n$.Then by Zsigmondy,there exists a prime divisor $q_i$ of $2^{p_i}+1$ which does not divide $2^{p_j}+1$ for all $j<i$(paricularly $3$).Thus there are at least $n+1$ prime factors(i.e.$3,p_1,p_2,....,p_n$) of $2^{p_1p_2.....p_n}+1$.Again by Zsigmondy,there exists a disinct prime divisor $r_1$ of $2^{p_1p_2}+1$ which does not divide $2^{p_1}+1$ and $2^{p_2}+1$.More generally there exists a distinct prime divisor $r_i$ of $2^{p_1p_2....p_{i+1}}+1$ which does not divide $2^{p_1p_2....p_j}+1$ for all $j<i+1$.Thus we found $n-1$ more prime divisors of $2^{p_1p_2...p_n}+1$(i.e.,$r_1,r_2,....,r_{n-1}$).So there are atleast $2n$ distinct prime divisors of $2^{p_1p_2...p_n}+1$ and hence atleast $2^{2n}=4^n$ divisors.

We use induction. First the base case. Let $p$ be a prime greater than 3. If $2^p+1$ has less than $4$ divisors, then it must be of the form $r$ or $r^2$ for some prime $r$. But $2^p+1$ is divisible by $3$, so either it is equal to $3$ ($q=1$, impossible) or $9$ ($q=3$, impossible). Thus $2^p+1$ has at least $4$ divisors. Assume the hypothesis holds true for $n$.

Consider a set of $n+1$ distinct prime numbers $q<p_1<p_2<...<p_n$, all greater than $3$. Define $P=p_1p_2...p_n$. Note that $q$ does not divide $P$. By induction the hypothesis, $2^P+1$ has at least $4^n$ divisors. Consider the quotient  $x=(2^{Pq}+1)/(2^P+1)$. It suffices to show that (1) $x$ has at least $4$ divisors and (2) $x$ is relatively prime to $2^P+1$.

We prove (1) by contradiction. Assume $x$ has less than $4$ divisors, so it must be of the form $r$ or $r^2$ for some prime $r$. Since, $2^q+1$ divides $2^{Pq}+1$, $2^q+1$ divides $x(2^P+1)$. If $r$ does not divide $2^q+1$ then $2^q+1$ is relatively prime with $x$, thus $2^q+1$ divides $2^P+1$ so $q|P$ a contradiction. Thus $r$ divides $2^q+1$. Since $x \le r^2$ and $r \le 2^q+1$, we have the bound $x=(2^{Pq}+1)/(2^P+1) \le (2^q+1)^2$. The LHS is greater than $2^{Pq}/2^{P+1}=2^{Pq-(P+1)}$, and the $RHS$ is less than $2^{3q}$. Thus $Pq-(P+1)<3q$, which rearranges to $q<1+4/(P-3)$. The LHS is at least $5$ and the RHS is at most $3$, a contradiction.

We now prove (2). Let $t$ be a prime dividing $2^P+1$. By LTE, $v_t(2^{Pq}+1)=v_t(2^P+1)+v_t(q)$. But  $v_t(2^{Pq}+1)=v_t(x(2^P+1))=v_t(x)+v_t(2^P+1)$, so $v_t(x)=v_t(q)$. Thus either $t$ does not divide $x$ or $t=q$. If for every prime $t$ dividing $2^P+1$, $t$ does not divide $x$, then we have proved (2). So assume $q$ divides $2^P+1$. Note that $2^{2P}$ is congruent to $1\mod q$. By FLT, we also have that $2^{q-1}$ is congruent to $1 \mod q$. Thus $2^{\gcd(2P,q-1)}$ is $1 \mod q$. But $q$ is smaller than any of the primes dividing $P$, thus $q-1$ is relativeily prime to $P$. So $\gcd(2P,q-1)=2$ and we get $4$ is $1 \mod q$ or $q=3$, a contradiction. Thus $q$ does not divide $2^P+1$ and (2) is proved.

A very nice problem in my opinion.

We induct on $n$.

$\blacksquare$ $n=1$
It suffices to show that $\left(2^p_1 +1 \right)$ has atleast 4 divisors where $p_1 \geq 5$ . It is trivial because ( By [b]LTE[/b] ) , $\left(2^p_1 +1 \right)$ cannot be a power of 3 , and hence is divisible by atleast $2$ distinct primes.

$\blacksquare$ (Induction hypothesis) Assume that $\left(2^{ p_1p_2 \cdots p_k}+1\right)$ has atleast $4^k$ divisors.

$\blacksquare$ $n=k+1$
Pick a primitive prime factor of   $\left(2^{ p_1p_2 \cdots p_kp_{k+1}}+1\right)$ and call it $q_1$.Pick a primitive prime factor of   $\left( 2^{p_{k+1}} +1 \right)$ and call it $q_2$.Note that $q_1$  and $q_2$ are greater than $3$ and are mutually distinct. By our choice of these primes, $gcd( q_1q_2 ,\left(2^{ p_1p_2 \cdots p_k}+1\right) )=1$.So we may write $\left(2^{ p_1p_2 \cdots p_kp_{k+1}}+1\right)=\left(2^{ p_1p_2 \cdots p_k}+1\right)\cdot q_1\cdot q_2 \cdot q$ for some integer$q$.This allows us to show that there are atleast $4^k \cdot 4=4^{k+1}$ divisors of  $\left(2^{ p_1p_2 \cdots p_kp_{k+1}}+1\right)$.

This completes our proof.

Let $d_1,d_2,\ldots,d_{2^n}$ be the divisors of $p_1p_2\ldots p_n$. By Zsigmondy's theorem $2^{d_i}+1$ has a primitive prime factor for all $i$ except for if $d_i=3$ which is not possible since $p_k>3$. Hence, we have at least $2^n$ distinct prime divisors of $2^{p_1p_2\ldots p_n}+1$, so at least $2^{2^n}$ divisors.

my solution:

let $ q=\Pi_{i=1}^{n}p_{i} $
obviously, $ 2^{r}+1|2^{q}+1 $,$ r|q $
here we have $ 2^n $ divisors,and we also have $ \frac{2^{q}+1}{2^{r}+1} $
so,we have $ 4^{n} $ divisors now
we only say why do not exist same divisors
it equals to say that exists x,y such that $ (2^{x}+1)(2^{y}+1)=2^{q}+1 $
it is same as $ 2^{x+y}+2^{x}+2^{y}=2^{q} $
compare the power of 2 then we have $ x=y=1,q=3 $ ( $ \rightarrow\leftarrow $ )
done!

[b]Lemma:[/b]$2^{p_{1}\dots p_{n}}+1$ has $2^n$ distinct prime divisors

[b]Proof:[/b]$p_{1}\dots p_{n}$ has $2^n$ distinct divisors.Let these are $1=d_{1}<\dots <d_{2^n}(d_{i}\neq 3)$.Since $p_{1}\dots p_{n}$ is odd,then $2^{d_{i}}+1\mid 2^{p_{1}\dots p_{n}}+1$.On the other hand,by [b]Zsigmondy's theorem[/b],
$\forall i\ge 2,\exists q_{i}$(prime) s.t. $q_{i}\mid 2^{d_{i}}+1$ and $q_{i}\nmid 2^{m}+1(1\le \forall m<d_{i})$.Let $3=q_{1}\mid 2^{d_{1}}+1$.Thus $1\le \forall i\le 2^n:q_{i}\mid 2^{p_{1}\dots p_{n}}+1$ and $q_{i}\neq q_{j}(i\neq j)$.Hence the proof is completed.$\blacksquare$

By [b]Lemma[/b],$2^{p_{1}\dots p_{n}}+1$ has at least $2^{2^n}=4^{2^{n-1}}$ divisors.Because $2^{n-1}\ge n$,completing the proof.$\blacksquare$ :coool:

After Hardship of nearly 12 hrs I did it.

[quote=ISL 2002 N3]Let $p_1,p_2,\ldots,p_n$ be distinct primes greater than $3$. Show that $2^{p_1p_2\cdots p_n}+1$ has at least $4^n$ divisors.[/quote]
[hide=Solution]
[b][color=#00f]Claim 1 :[/color][/b] $ \nu_3(2^p+1)=1$ for any odd prime $p$
[b][color=#351C75]Proof : [/color][/b] Let $p=2k+1$  $\;$ so  $\;$ $2^p+1$ $=$ $2^{2k+1}+1$ $\equiv 4^k\cdot 2+1\equiv 2+1$ $=$ $3\equiv 0 \pmod{3}$ $\;$ .Now by LTE we get \[\nu_3(2^p+1)=\nu_3(2+1)+\nu_3(p)=1+0=1\]This proves the Claim.$\square$
--------
We proceed by Induction.In the base clearly $\tau(33)\geq 4$.Now assume that it is true for $i\leq n$.$\;$ For $n+1$ Note that $\gcd(2^{p_{n+1}}+1,\ell)=\{1,3\}$ where $\ell\mid 2^{p_1p_2\cdots p_n}+1$.Indeed suppose $t=\gcd(2^{p_{n+1}}+1,\ell) \neq 3$.Then $\exists \; j\;$ such that $t\mid 2^j+1$ and $t\mid 2^{p_{n+1}}+1\;$.Hence \[t\mid \gcd(2^j+1,2^{p_{n+1}}+1)=2^{\gcd(j,p_{n+1})}+1 = 3\].A contradiction.Now consider the sets \[A=\{\ell : \ell \mid  2^{p_1p_2\cdots p_n}+1\}\]  \[B=\{ 1,3,q,2^{p_{n+1}}+1\}\]. where $q$ is a prime such that $q\mid 2^{p_{n+1}}+1$ and $q\nmid 2^i+1$ for all $1\leq i\leq p_{n+1}-1$.Such a prime clearly exists by Zsigmondy's Theorm(The exception $2^3+1$ also doesnt pose a problem since $p_i\geq 5$).Now note that $A\cap B=\{1,3\}$.By induction Hypothesis we get $|A|\geq 4^n$.Thus \[\tau(2^{p_1p_2\cdots p_{n+1}}+1)\geq 4^n+\underbrace{2\cdot 4^n}_{\text{Multiplying $2^{p_{n+1}}+1$,q with A}} + \underbrace{4^n-2}_{\text{Multiplying 3 with A/\{1,3\}}}+\underbrace{2}_{\text{1,$2^{p_1p_2\cdots p_{n+1}}+1$
}} \geq 4^{n+1}\] as desired.$\blacksquare$
[/hide]
[color=#f00]Remark[/color]-The above solution looks long compared to others but its just overly formalised and idea is essentially the same

Essentially this is wrong :(

we will induct on $n$
for n=1 it's trivial
suppose it's true for n-1
for (n):
let $p_i < p_{i+1}$    let $q=p_1$ and $p=\prod_{i=2}^n{p_i}$
$2^{pq}+1=(2^{p}+1)(A)$
it's easy that $gcd((2^{p}+1),(A))=gcd((2^{p}+1),q)$

[color=#600][b]claim[/b][/color]:  $q$ doesn't divide $2^p+1$ and $A$

suppose it does
$q|2^p+1$
$q|4^p -1$
$q|4^{q-1}-1$
$q|4^{gcd(2p,q-1)}-1$
$q|15$
if $q=5  $
but $16^p-8^p+4^p-2^p+1 \equiv 1 mod(5)$

then $A$ has a new prime divisor and from the induction hypothesis we're done

 :D

By Zsigmondy's, every $2^k+1$ has a primitive prime factor. Now $p_1p_2...p_n$ has $2^n$ factors. Let d be a factor then, $2^d+1|2^{p_1p_2...p_n}+1$. So we get at least $2^n$ prime factors. Thus, there are at least $2^{2^n}$ divisors.

[quote=math_pi_rate]Nice problem. Here's my solution: Let $X_n=2^{p_1p_2 \dots p_n}+1$. We induct on $n$. For $n=1$, the number $2^p+1$ has 4 factors, namely $1,3,\frac{1}{3}(2^p+1),2^p+1$ (since $p>3$, so by Catalan Conjecture, we are assured of the distinctness of these four numbers). Assume the result is true for $n$. Consider $X_{n+1}$. Note that, by Zsigmondy Theorem, there exists some prime number $q$, such that $q \mid X_{n+1}$ but $q \nmid X_n$. Also, $X_n \mid X_{n+1}$, which along with the induction hypothesis gives the existence of $2 \times 4^n$ factors of $X_{n+1}$ (Each divisor of $X_n$, and its corresponding quotient on division by $X_{n+1}$). Also, each of these $4^n$ factors of $X_n$, on multiplication with $q$, give another factor of $X_{n+1}$. Thus, we again get $2 \times 4^n$ factors of $X_{n+1}$ (Each divisor of $X_n$ multiplied by $q$, and the corresponding quotient of these numbers on division by $X_{n+1}$). Thus, we get a total of $2 \cdot 4^n+2 \cdot 4^n=4^{n+1}$ factors of $X_{n+1}$, completing the induction step. $\blacksquare$[/quote]

Absolute example of a 3/7 proof... there are many details that you have to work out to assure that this solution is valid. For example, in your first argument, why is the intersection of the set of quotients and the set of divisors of $X_n$ null? There are even more problems when you reach your second argument, for example, why are the divisors of $X_n$ multiplied with $q$ distinct from the quotients of $X{n+1}$ divided by the set of divisors of $X_n$?

Btw, there is also a way to avoid the use of Zsigmondis by proving some elementary results.

However, the main idea of the solution is correct and you can be assured that the problem can be solved by your logic (just tried it out on my notebook).

Another(surprisingly short) Zsig solution: :D
Consider the set $T$ of divisors of $p_1p_2 \dots p_n$ and order it's elements as $a_1,a_2 \dots a_{2^n}$ where $a_i<a_j$ when $i<j$. Note that by Zsig, we get that every single number of the form $2^{a_i}+1$ adds a new prime divisor to $2^{p_1p_2 \dots p_n}+1$ giving us a total of $2^n$ prime divisors to it, making its' total number of divisors $\geq 2^{2^n}$., which is far more than required.$\square$

[b][u]Solution with Zsigmondy for proving the stronger bound[/u][/b]
Let $ \Pi=p_1p_2\dots p_n$. Then by Zsigmondy's Theorem, for every positive $d$ such that $d| \Pi$, the number $2^d+1$ has a primitive prime factor (the exceptional case of $d=3$ need not be considered since $p_i>3$ for all $1\leq i\leq n$). Also for odd $a,b$ such that $a|b$, we have $2^b+1=(2^a)^{b/a}\equiv (-1)^b+1\equiv 0\pmod{2^a+1}$, so $2^d+1|2^ \Pi+1$. Thus each number of the form $2^d+1$ where $d| \Pi$ contributes an unique prime factor to $2^ \Pi+1$. Since there are $2^n$ such $d$, so there are at least $2^{2^n}$ positive divisors of $2^ \Pi+1$. $\blacksquare$

[b][u]Elementary solution for proving the original weak bound [/u][/b]
We will proceed by induction. First we note that for any odd integer $a$, we have $2^a+1\equiv 0\pmod 3$.
Now for the base case, note that $2^{p_1}+1$ has $4$ divisors $1,3,\frac{2^{p_1}+1}{3},2^{p_1}+1$. These are distinct since $\frac{2^{p_1}+1}{3}>\frac{2^3+1}{3}=3$ since $p_1>3$. Now suppose for some $n\geq 1$, the number $A_n=2^{p_1p_2\dots p_n}+1$ has at least $4^n$ distinct positive divisors. Now consider the number $A_{n+1}=2^{p_1p_2\dots p_np_{n+1}}+1$. We note that $A_n|A_{n+1}$ and $2^{p_{n+1}}+1|A_{n+1}$ (proof in previous solution). Now we prove some lemmas.

[b]Lemma 1:[/b]For relatively prime positive integers $a,b$, we have $\gcd(2^a+1,2^b+1)\leq 3$.
[b]Proof:[/b] We know that  $\gcd(2^{2a}-1,2^{2b}-1)=\gcd((2^a-1)(2^a+1), (2^b-1)(2^b+1))= 2^{\gcd(2a,2b)}-1=2^{2}-1=3$. So $\gcd(2^a+1,2^b+1)\leq 3$. $\square$

[b]Lemma 2:[/b] For any positive integers $a,b>3$ the inequality $3\cdot(2^{ab}+1)>(2^a+1)(2^b+1)^2$ holds true.
[b]Proof:[/b] We have $ab>2(b-1)\implies ab-b-1>b-1\implies 2^{ab-b-1}>2^{b-1}+1\implies 2^{ab-1}>2^{2b-1}+2^b$. We also have $b(a-2)>a\implies ab-1>a+2b-1\implies 2^{ab-1}>2^{a+2b-1}$. Again, we have $(a-1)(b-1)>2\implies ab-a>b+1\implies 2^{ab-a}>2^{b+1}+1\implies 2^{ab-1}>2^{a+b}+2^{a-1}$. Thus adding these up, we have $3\cdot 2^{ab-1}+1>3\cdot 2^{ab-1}>2^{2b-1}+2^{b}+2^{a+2b-1}+2^{a+b}+2^{a-1}$ or $3\cdot 2^{ab}+3>2^{2b}+2^{b+1}+2^{a+2b}+2^{a+b+1}+2^{a}+1$ or $3\cdot(2^{ab}+1)>(2^a+1)(2^b+1)^2$, as desired. $\square$

By [b]Lemma 1[/b], we have $\gcd(2^{p_{n+1}}+1,A_n)=3$. Thus we deduce that $\frac{(2^{p_{n+1}}+1)A_n}{3}\bigg|A_{n+1}$. Further we note that $\frac{(2^{p_{n+1}}+1)A_n}{3}=\frac{2^{p_1p_2\dots p-n+p_{n+1}}+2^{p_{n+1}}+2^{p_1p_2\dots p-n}+1}{3}<\frac{A_{n+1}+A_{n+1}+A_{n+1}}{3}=A_{n+1}$. Thus let $d=\frac{2^{p_{n+1}}+1}{3}$ and $A_{n+1}=A_{n}dd'$ for some $d'>1$. We may note that $\gcd(A_n,d)=1$. Now if $d'|A_n$, then $A_ndd'=A_{n+1}|A_n^2d$, which implies that $3(2^{p_1p_2\dots p_{n+1}}+1)|(2^{p_{n+1}}+1)(2^{p_1p_2\dots p_n}+1)^2$. Then $3(2^{p_1p_2\dots p_{n+1}}+1)\leq (2^{p_{n+1}}+1)(2^{p_1p_2\dots p_n}+1)^2$. But this can be ruled out using [b]Lemma 2[/b], if we take $a=p_{n+1}$ and $b=p_1p_2\dots p_n$. Thus we see that $d'\nmid A_n$.
So for each positive divisor $k$ of $A_n$, we have the unique quadruplet $(k,dk,d'k,dd'k)$ of distinct positive divisors of $A_{n+1}$. By our induction hypothesis, there are at least $4^n$ possibilities for $k$, thus giving us at least $4\cdot 4^n=4^{n+1}$ distinct positive divisors of $A_{n+1}$.
Thus our proof is complete. $\blacksquare$

[quote=IMOSL 2002]Let $p_1,p_2,\ldots,p_n$ be distinct primes greater than $3$. Show that $2^{p_1p_2\cdots p_n}+1$ has at least $4^n$ divisors.[/quote]

We will start out with some lemmas:

[color=#ff9a00][b]Lemma 1: [/b][/color]For $a,b$ being positive integers we hae $\gcd(2^a+1,2^b+1)\mid 2^{\gcd(a,b)}+1$.
[i]Proof:[/i]
Suppose $m=\gcd(2^a+1,2^b+1)$. Notice that $m$ is odd. So,
$$\begin{cases} 2^a\equiv -1 \pmod{m} \implies 2^{2a}\equiv 1 \pmod{m}\\ 2^b\equiv -1 \pmod{m}\implies 2^{2b}\equiv 1 \pmod{m}\end{cases}$$So, $2^{2\gcd(a,b)}=2^{\gcd(2a,2b)}\equiv 1 \pmod{m}\implies m\mid(2^{\gcd(a,b)}-1)(2^{\gcd(a,b)}+1)$. If $m\mid 2^{\gcd(a,b)}+1$ then we are done. Suppose not. Since,$$\gcd(2^{\gcd(a,b)}+1,2^{\gcd(a,b)}-1)=\gcd(2, 2^{\gcd(a,b)}-1)=1$$it follows that $m\mid 2^{\gcd(a,b)}-1\mid 2^a-1$. But $m\mid 2^a+1$. Thus, $m\mid \gcd(2^a-1,2^a+1)=\gcd(2,2^a-1)=1\implies m=1$ contradicting that $m\nmid 2^{\gcd(a,b)}+1$. $\square$

[color=#ff9a00][b]Lemma 2:[/b][/color] For integers $a,b \ge 5$ we have $9(2^{ab}+1)> (2^a+1)^2(2^b+1)^2$.
[i]Proof:[/i]
we have \begin{align*}   (2^a+1)^2(2^b+1)^2&=(2^{2a}+2^{a+1}+1)(2^{2b}+2^{b+1}+1) \\& <(3\cdot 2^a+1)(3\cdot 2^b+1) \\&<9(2^{2a}+1)(2^{2b}+1)    \\& =9(2^{2b+2a}+2^{2b}+2^{2a}+1)\\&< 9(2^{2a+2b+2}+1)\\&< 9(2^{ab}+1)\end{align*} $\square$.

[color=#ff9a00][b]Lemma 3:[/b][/color] $v_3(2^p+1)=1$ where $p$ is a prime $p\ge 5$
[i]Proof:[/i] Since, $p$ is odd and $3\mid 2+1$, by [color=#00f]LTE[/color] Lemma $$v_3(2^p+1)=v_3(2+1)+v_3(p)=1.$$ $\square$

[color=#f00][b]Main Proof:[/b][/color]
We use induction on $n$. Let $m_k=2^{p_1p_2\cdots p_k}+1$ and $a_k=p_1p_2\cdots p_k$.
For $n=1$ we consider $m_1=2^{p_1}+1$. Now, $$2^{p_1}+1\equiv -1+1\equiv 0\pmod{3}$$ since $p_1$ is odd. Also, as $p_1>3\implies m_1>9$ and so, $\tfrac{m_1}{3}$ is also a divisor of $m_1$. So, $1,3, \tfrac{m_1}{3},m_1$ are divisors of $m_1$ completing the base case.

we assume the statement is true for $n=k$ and we show it for $n=k+1$.
As, $3\mid 2^{a_k}+1$ and $3\mid 2^{p_{k+1}}+1$ and from [color=#ff9a00]Lemma 1[/color] we have $\gcd(m_k,2^{p_{k+1}}+1)=\gcd(2^{a_k}+1,2^{p_{k+1}}+1)=3$. Thus, from [color=#ff9a00]Lemma 3[/color] we get $$\gcd\left(2^{a_k}+1,\frac{2^{p_{k+1}}+1}{3}\right)=1. (*)$$
It is clear that $m_k\mid m_{k+1}$ and $2^{p_{k+1}}+1\mid m_{k+1}$ since, $a_{k+1}$ is odd.  So, from $(*)$ we can write $$m_{k+1}=m_k\cdot \frac{2^{p_{k+1}}+1}{3}\cdot c_k (**)$$ for some positive integer $c_k$. From our induction hypothesis we have $4^k$ divisors of $m_k$ say $d_1,d_2,\dots, d_{4^k}$. We also get another $4^k$ divisors namely $d_i\cdot \frac{2^{p_{k+1}}+1}{3}$ for $1\le i\le 4^k$. So, we get $4^k\cdot 2$ divisors from $m_k\cdot \frac{2^{p_{k+1}}+1}{3}$. We arrange these $4^k\cdot 2$ divisors in ascending order as $d_1<d_2<\dots < d_{4^k\cdot 2} (***)$. We consider $$d_1c_k,d_2c_k,\dots ,d_{4^k\cdot 2}c_k.$$ So, by $(**)$ we know that $$d_1,d_2,\dots , d_{4^k\cdot 2},d_1c_k,d_2c_k,\dots ,d_{4^k\cdot 2}c_k$$ are all divisors of $m_{k+1}$.
We claim that $d_1c_k>d_{4^k\cdot 2}$. Since, $d_1\ge 1$ and $d_{4^k\cdot 2}\le m_k\cdot \frac{2^{p_{k+1}}+1}{3}$ it suffices to show
\begin{align*} & c_k>m_k\cdot \frac{2^{p_{k+1}}+1}{3} \\ \iff &  m_{k+1} > \left(m_k\cdot \frac{2^{p_{k+1}}+1}{3}\right)^2 \\ \iff & 9(2^{a_k\cdot p_{k+1}} +1)>(2^{a_k}+1)^2(2^{p_{k+1}}+1)^2\end{align*} which follows from [color=#ff9a00]Lemma 2[/color].

Hence, we have proved that $d_1,d_2,\dots , d_{4^k\cdot 2},d_1c_k,d_2c_k,\dots ,d_{4^k\cdot 2}c_k$ are all distinct (due to $(***)$) completing the inductive step. $\blacksquare$

[quote=darij grinberg]I don't understand why $ \Phi_{2a}(2) | 2^b - 1, \Phi_{2b}(2) | 2^b + 1$.[/quote]

The second statement is true because $\forall k, 2^k + 1 = \frac{2^{2k}-1}{2^k-1} = \frac{\prod_{d|2k}^{} \Phi_d(x)}{\prod_{d|k}^{} \Phi_d(x)} = \prod_{d|k}^{} \Phi_{2d}(2)$. Now, $\Phi_{2d}(2) \mid \prod_{d|k}^{} \Phi_{2d}(2) \Longrightarrow \Phi_{2d}(2) \mid 2^k+1$ by the previous relation. The first statement should be obvious by similar reasoning

Shooting sparrows with cannons...
Consider the set of all divisors of $p_1p_2\ldots p_n$; clearly there are $2^n$. For each divisor $d$, $2^d+1$ has a primitive prime factor (i.e. one that is not a factor of any $2^k+1$ for $k<d$). If we consider the set of all primes $p$ dividing $2^d+1$ for some divisor $d$ of $p_1p_2\ldots p_n$, then the previous fact implies that there are at least $2^n$ elements of that set. Now note that if some prime $p$ divides $2^d+1$, it must divide $2^{p_1p_2\ldots p_n}+1$. To see this, rewrite $p_1p_2\ldots p_n$ as $dk$ where $k$ is odd. Then we have:
$$p \mid 2^d+1 \implies 2^d \equiv -1 \pmod{p} \implies 2^{dk} \equiv (-1)^k \equiv -1 \pmod{p} \implies p \mid 2^{dk}+1$$
which means that there are at least $2^n$ divisors of $2^{p_1p_2\ldots p_n}+1$. This implies that there are at least $2^{2^n}\geq 4^n$ divisors of $2^{p_1p_2\ldots p_n}+1$.

We prove a better result than required, $2^{2^{n-1}},$ only by using cyclotomic polynomials!
[rule]
Let $p_1\cdot p_2\cdot...\cdot p_n=c.$ Then, bearing in mind that $c$ is odd, we manipulate our expression as such: \[2^c+1=\frac{2^{2c}-1}{2^c-1}=\prod_{d\mid 2c}\Phi_d(2)\cdot\bigg(\prod_{d\mid c}\Phi_d(2)\bigg)^{-1}=\prod_{d\mid c}\Phi_{2d}(c).\qquad (\dagger)\]Now, let $D$ be the set of divisors of $c.$ Define the following partial ordering: for $a,b\in D,$ say that $a\preceq b$ if $a/b$ is a prime number. By Theorem 5.6 of [color=#c00][1][/color] and the fact that $c$ is squarefree, it follows that if $a,b\in D$ are incomparable by $\prec,$ then  $\gcd\big(\Phi_{2a}(2),\Phi_{2b}(2)\big)=1.$

By Lemma 7 of [color=#c00][2][/color] we get that $\Phi_{2d}(2)>1$ for all $d>2$ and since $\Phi_2(2)=3>1$ then for all $d\geq 1, \ \Phi_{2d}(2)>1.$

Hence, if $a_1,a_2,...,a_k\in D$ form an antichain $C^{-1},$ then there are at least $|C^{-1}|$ prime numbers dividing the RHS of $(\dagger)$ and, consequently, dividing $2^c+1.$ Therefore, we get that $\tau(2^c+1)\geq 2^{|C^{-1}|}.$ In order to get our desired bound, we only have to show that there exists some antichain of size at least $2^{c-1}$

Let $\omega(k)$ denote the number of primes dividing $k.$ Consider the sets $D_0$ and $D_1$ defined as follows \[D_0:=\{d\in D:\omega(d)\equiv 0\bmod{2}\}, \ D_1:=\{d\in D:\omega(d)\equiv 1\bmod{2}\}.\]One can easily see that $D_0$ and $D_1$ are disjoint, their union is $D$ itself, and both are antichains.

Hence, $\max\big(|D_0|,|D_1|\big)\geq |D|/2=2^{n-1}$ so we found an antichain of size at least $2^{n-1},$ completeing our proof.
[rule]
[color=#c00][1][/color] [url=https://www.whitman.edu/Documents/Academics/Mathematics/2015/Final%20Project%20-%20Porter,%20Brett.pdf]Cyclotomic Polynomials, 2015, Brett Porter[/url]
[color=#c00][2][/color] [url=https://pommetatin.be/files/zsigmondy_en.pdf]Zsigmondy's Theorem, 2014, Bart Michaels[/url]

NT is  :love:

[color=blue][b]Claim 1.[/b][/color] If $k$ is an odd positive integer and $p$ is a prime, then we have $a^p+1\mid a^{kp}+1$.
[i]Proof.[/i] Notice that
\begin{align*}
    (a^p+1)&(a^{(k-1)p}-a^{(k-2)p}+a^{(k-3)p}-\dots+1) \\ &= (a^{kp}-a^{(k-1)p}+a^{(k-2)p}-\dots+a^p) + (a^{(k-1)p}-a^{(k-2)p}+a^{(k-3)p}-\dots+1) \\
    &=a^{kp}+1
\end{align*}

Then because of Claim 1, we know that for all $1\le i\le n$ we have $2^{p_i}+1\mid 2^{p_1p_2\cdots p_n}+1$. Let $S$ be the divisors of the number $p_1p_2\hdots p_n$ in [b]sorted[/b] order meaning that $S_1 < S_2 < \dots$. It is easy to see that there are $2^n$ elements in $S$. Let $S_1$ denote the first element of the set. Also let $i, j$ be some positive integers such that $1\le i\le 2^n$ and $j<i$. Now, call a prime "new" if it divides $2^{S_i}+1$ and none of the numbers $2^{S_j}+1$ divide this "new" prime. Now considering $S_1 = 1$, we have $2^{S_1}+1=3$ which is a "new" prime. Now for all $1<k\le 2^n$ we consider the number $2^{S_k}+1$. By Zsigmondy's it must have a "new" prime divisor since the set $S$ is sorted. Thus we can conclude that there are $2^{2^n}$ divisors of $2^{p_1p_2\hdots p_n}+1$. Since $2^{2^n}$ is obviously greater than or equal to $4^n$, we are done.

ISL marabot solve

Let $d$ be one of the $2^n$ divisors of $p_1 p_2p_3\cdots p_n$.

Claim: $2^d+1\mid 2^{p_1 p_2 p_3\cdots p_n}+1$.
Suppose a prime power $p^k$ divides $2^d+1$. Then $2^d\equiv -1\pmod {2^k}$. Since all the primes are odd, $2^{p_1p_2 p_3\ldots p_n}\equiv -1\pmod {2^k}$. $\blacksquare$

By Zsigmondy's, $2^d+1$ has a primitive prime factor for all divisors $d$. So $2^{p_1p_2\cdots p_n}+1$ has at least $2^n$ prime factors, so it has at least $2^{2^n}\ge 2^{2n}=4^n$ divisors.

For $n=1$ we have that some divisors are $1, 3, \frac{2^{p_1}+1}{3}, 2^{p_1}+1$ hence this case is done.
For $n=2$ we will use the cyclotomic representation of $2^{p_1p_2}+1$
$$2^{p_1p_2}+1=3 \cdot \Phi_{2p_1}(2) \cdot \Phi_{2p_2}(2) \cdot \Phi_{2p_1p_2}(2)$$
Now we verify that $v_3(2^{p_1p_2}+1)=v_3(2+1)+v_3(p_1p_2)=1$ and $\frac{2p_1}{2p_2}=\frac{p_1}{p_2}$ which is not a power of a prime number, hence we have guaranted $2^3=8$ prime factors but since none of the products u can create is $2^{p_1p_2}+1$ or $1$ we have $16$ divisors in total and hence on this case we are done.
For $n \ge 3$ we will use again the cyclotomic representation of $2^{p_1p_2 \cdots p_n}+1$
$$2^{p_1p_2 \cdots p_n}+1=\prod_{k \mid p_1p_2 \cdots p_n} \Phi_{2k}(2)$$
Now from all of these $2^n$ factors we can notice that if we look for all $k$ such that $\gcd(\Phi_{2k}(2), \Phi_{2p_n}(2))=1$ then we are just looking for $\frac{k}{p_n}$ not being a power of a prime number which happens always except on $n-1$ cases, hence we have guaranted $2^n-n+1$ prime fractors hence we have guaranted at least $2^{2^n-n+1}$ divisors.
Now we skip all we did so far and we will show by induction that $2^n \ge 3n-1$ for all $n \ge 3$
For $n=3$ we get equality so now we do inductive step, if it holds for $n=k$ we will prove it for $n=k+1$
$$2^{k+1}=2 \cdot 2^k \ge 6k-2 \ge 3k+2$$
Hence it holds for all $n$ which means that we have $2^{2^n-n+1} \ge 4^n$ divisors guaranted hence we are done  :D

[quote=grobber]. On the other hand, we clearly have $\left(\frac{2^{p_n}+1}3\right)^2<\frac{2^N+1}{2^{N'}+1}$, which means that $\frac{2^N+1}{2^{N'}+1}$ has at least four divisors $1=d_1,d_2,d_3,d_4$. For each $d|2^{N'}+1$, each of $d_id$ is a divisor of $2^N+1$, and all $d_id$ are different because $(d_i,d)=1$, hence the result: $2^N+1$ has at least $4\cdot 4^{n-1}=4^n$ divisors.[/quote]

Can you please give more clarity on this part of the proof. I did not get it.

[hide = Proof]
We use induction on the number of primes. The base case is (as usual) trivial and so we immediately assume the induction hypothesis. Namely that $2^{p_1p_2 \cdots p_n} + 1$ has at least $4^n$ divisors.

[b][u]Lemma[/u]: [/b] If $\operatorname{gcd} (a, b) = 1,$ with $a, b$ odd, then $\operatorname{gcd} (2^a + 1, 2^b + 1) = 3$.

With this, let $a = p_1p_2 \cdots p_n$ and let $ b = p_{n + 1}$. Then we have that $2^{ab} + 1 = (2^a + 1)(2^{a(b - 1)} - 2^{a(b - 2)} + \cdots + 2^a - 1)$. Thus $2^{ab} + 1$ is divisible by $2^a + 1, 2^b + 1$, and as $2^a + 1$ and $(2^b + 1)/3$ are coprime, $2^{ab} + 1$ is also divisible by $(2^a + 1)(2^b + 1)/3$, and therefore has a minimum of $2 \cdot 4^n$ factors by the induction hypothesis.

[b]Lemma: [/b] Let $x > y$ be positive integers. Then $d(xy) \geq 2d(y)$, where $d(x)$ is the divisor function.
[hide = Proof of lemma] Indeed if some integer $k \mid y$, $xk$ is a divisor of $xy$ but not $y$. [/hide]

Now let $2^{ab} + 1 = K(2^a + 1)(2^b + 1)/3$. Now as $((2^a + 1)(2^b + 1)/3)^2 < 2^{ab} + 1$, we have that $K > (2^a + 1)(2^b + 1)/3$. With the above lemma, we then have \[d(2^{ab} + 1) = d(K(2^a + 1)(2^b + 1)/3) \geq 2d((2^a + 1)(2^b + 1)/3) \geq 4^{n + 1},\] as desired. $\blacksquare$ [/hide]

[quote=anantmudgal09]I have a highly overkill-based solution....

We proceed by induction on $n$ checking the base case as in other solutions.

Note that $2^{p_1...p_{n+1}}+1$ is divisible by $2^{p_1...p_n}+1$ and by Zsigmondy it must have a prime divisor not dividing the second ugly expression.

Moreover,it is evident by Mihailescu's theorem that $(2^{p_1...p_n})^{p_{n+1}}+1 \not= q^m$ where $q$ is a prime.

So, we that the induction step is complete and this expression has at least $2n$ distinct prime divisors for every $n$ meaning $4^n$ divisors at  least.

This was highly overpowered with not much insight.
Will post an elementary solution later.[/quote]

I understand the Zsigmondy and Mihailescu theorem part. But I do not understand how the induction is complete. Can someone help me understand.
Thanks, MathWhiz214

Let the divisors of $p_1p_2 \dots p_n$ be $d_1, d_2, d_3, \dots, d_{2^n}$. Note that $2^{d_i}+1$ has a primitive prime factor not dividing $2^{d_j}+1$ for any $j<i$ by Zsigmondy's Theorem. Note that each of these primes divides $2^{p_1p_2\dots p_{2^n}}$, so we have there is at least $2^{2^n} \ge 2^{2n}=4^n$ prime factors.

We proceed by induction. WLOG, let $p_1<p_2<\dots < p_n$. Clearly, any prime must be odd, so $a_1=2^{p_1}+1$ has divisors $1$, $3$, $\tfrac{a_1}{3}$, and $a_1$.
\\$~$\\
Now, suppose that $a_n=2^{p_1p_2\dots p_n}+1$ has at least $4^n$ divisors. Consider $a_{n+1}=2^{p_1p_2\dots p_{n+1}}+1$. Note that $2^{p_1p_3\dots p_n p_{n+1}}+1\mid a_{n+1}$. This contains a prime factor not already divisible by $a_n$, and $2^{p_2p_3\dots p_n}+1$ contains an additional prime factor not already divisible by $a_n$, so $\tau(a_{n+1})\ge 4\tau(a_n)$ as desired.

Clearly, this is true when $n=1$, since $2^{p_1}+1$ is larger than 9 and divisible by 3.\\

Now, we will induct. Suppose that $$N=2^{p_1\cdots p_n}+1$$ has $d$ divisors. We will then show that $$M=2^{p_1\cdots p_np_{n+1}}+1$$ has at least $4d$ divisors. Note that we have $N|M$ and $2^{p_{n+1}}+1|M.$\\

Claim 1: $$\gcd(N,2^{p_{n+1}}+1)=3.$$ Clearly, they are both odd but divisible by 3. Now, suppose for the sake of contradiction that they are divisible by some other prime $p\geq5.$ Then, $$2^{p_1\cdots p_n}\equiv -1\pmod p$$ and $$2^{p_{n+1}}\equiv -1\pmod p.$$ This would mean that $$ord_p(2)|2p_1\cdots p_n$$ and $$ord_p(2)|2p_{n+1}.$$ However, since the $p_i$ are distinct odd primes, we must then have $$ord_p(2)|2,$$ clearly a contradiction if $p\geq5.$\\

Thus, $$N\cdot\frac{2^{p_{n+1}}+1}{3}|M,$$ and furthermore $N$ is relatively prime to $\frac{2^{p_{n+1}}+1}{3}$, since $2^{p_{n+1}}+1$ is not a multiple of 9 as $p_{n+1}$ is not a multiple of 3.\\

Claim 2: $$N\cdot\frac{2^{p_{n+1}}+1}{3}<\sqrt{M}.$$ Note that $N\geq33$ and $p_{n+1}\geq5$. We can use the relation $$M=(N-1)^{p_{n+1}}+1.$$ Plugging this into the inequality gives $$N^2(2^{p_{n+1}}+1)^2<9((N-1)^{p_{n+1}}+1).$$ This also becomes $$2\log_2(N)+2\log_2(2^{p_{n+1}}+1)<\log_2(9)+\log_2((N-1)^{p_{n+1}}+1).$$ Clearly, it suffices to show that $$2\log_2(N)+2\log_2(2^{p_{n+1}}+1)<p_{n+1}\log_2(N-1).$$ Now, since $p_{n+1}\geq5$, we have $$\log_2(2^{p_{n+1}}+1)<p_{n+1}+0.5,$$ so it suffices to show that $$2\log_2(N)+2p_{n+1}+1<p_{n+1}\log_2(N-1).$$ This is equivalent to $$p_{n+1}(\log_2(N-1)-2)>2\log_2(N)+1.$$ Note that $N\geq33$, so $\log_2(N-1)-2$ is positive. Thus, it suffices to show that this is true for the smallest value of $p_{n+1}$, which is 5. In this case, it becomes $$5\log_2(N-1)>2\log_2(N)+11,$$ which exponentiated becomes $$(N-1)^5>2048N^2.$$ This is clearly true for $N\geq33$, so we have shown Claim 2.\\

To recap, we now know that:\\

1. $N(\frac{2^{p_{n+1}}+1}{3})$ is a factor of $M$.\\

2. $N$ is relatively prime to $\frac{2^{p_{n+1}}+1}{3}.$\\

3. $N(\frac{2^{p_{n+1}}+1}{3})<\sqrt{M}.$\\

From (2), we have that $N(\frac{2^{p_{n+1}}+1}{3})$ has at least $2d$ factors, since the divisor function is multiplicative when they are relatively prime. Thus, $M$ has at least $2d$ factors that are less than $\sqrt{M}$. Therefore, $M$ has at least $4d$ factors, so we are finally done.

Take an arbitrary $d\mid p_1p_2...p_n$; this implies $2^d+1\mid 2^{p_1 p_2... p_n}+1$. By Zsigmondy's, $2^d+1$ has a prime p s.t. $p\nmid2^{d_0}+1\forall d_0<d$, which implies for each d (2^n of them) there's at least a prime factor in $2^{p_1p_2...p_n}+1$ (built by taking smallest d to largest, each one is distinct), implying the expressions has at least $2^{2^n}\ge2^{2n}=4^n$ factors. $\blacksquare$

@below indeed, zsigmondy has a harder proof than this problem itself, but zsigmondy does not immediately kill, nor does it generalize;

[quote=huashiliao2020]Take an arbitrary $d\mid p_1p_2...p_n$; this implies $2^d+1\mid 2^{p_1 p_2... p_n}+1$. By Zsigmondy's, $2^d+1$ has a prime p s.t. $p\nmid2^{d_0}+1\forall d_0<d$, which implies for each d (2^n of them) there's at least a prime factor in $2^{p_1p_2...p_n}+1$ (built by taking smallest d to largest, each one is distinct), implying the expressions has at least $2^{2^n}\ge2^{2n}=4^n$ factors. $\blacksquare$[/quote]

But Zsigmondy's Thm isn't an easy one. So I think the solution is rather meaningless.  :juggle:


integration
logarithms
calculus
calculus computations

If $ \bold{F}(x,y) \equal{} \frac {k(x \bold{i} \plus{} y \bold{j})}{x^{2} \plus{} y^{2}}$ find the work done by $ \bold{F}$ in moving a unit charge along a straight line segment from $ (1,0)$ to $ (1,1)$.

So $ \bold{F}(1,y) \equal{} \frac {k(\bold{i} \plus{} y \bold{j})}{1 \plus{} y^{2}}$. Then $ x \equal{} 1, \ y \equal{} y$.
$ k \int_{0}^{1} \frac {y}{1 \plus{} y^{2}} \ dy$

$ u \equal{} 1 \plus{} y^{2}$

$ du \equal{} 2y \ dy$

$ \frac {k}{2} \int \frac {du}{u}$

$ \equal{} \frac {k}{2} \int_{0}^{1} \ln|1 \plus{} y^{2}|$

$ \equal{} \frac {\ln 2}{2}$.

Is this correct?

I believe you're missing a $ k$ on your final answer.  There is also one step that may of just been a notational error.  When you say $ \equal{} \frac {k}{2} \int_{0}^{1} \ln|1 \plus{} y^{2}|$, I believe you meant $ \equal{} \frac {k}{2} \ln |1 \plus{} y^2|_0^1$

Full Solution
[hide]Our equation if $ \bold{r}(y) \equal{} < 1,y >$, $ 0 < \equal{} y < \equal{} 1$.

$ W \equal{} \int_C \bold{F} \cdot d \bold{r}$
$ W \equal{} \int_0^1 \bold{F}(1,y) \cdot \bold{r}'(y) ~dy$
$ W \equal{} \int_0^1 \left < \frac {k}{1 \plus{} y^2}, \frac {ky}{1 \plus{} y^2} \right > \cdot < 0,1 > ~dy$
$ W \equal{} \int_0^1 \frac {ky}{1 \plus{} y^2} ~dy$
$ W \equal{} \frac {k}{2} \int_1^2 \frac {du}{u}$
$ \boxed{W \equal{} \frac {k \cdot \ln 2}{2}}$[/hide]


One has several heaps of coins. Players A and B may do one move in turn. Define a move as follows: a player may take away one coin from a certain heap, but he may also take one coin from several heaps in the same time IFF those heaps have the same number of coins [although there might be some heaps having the same number of coins from which no coins is taken.] The player taking the last coin(s) wins. What's the best strategy for both players?

What is UWC?

I have analyzed some cases and I don't see any regularity.

UWC is "Universitaire Wiskunde Competitie" = Universitary Maths Competition.
Some of the problems can be solved by quite elementary means (such as this one),
although the competition is for university students in Flanders and the Netherlands.

This is a very hard problem;
there s a solution, although you might not see any regularity.
We discussed it in IMO training last weekend.

I mean I can't get closed answer,  though I can easy obtain right answer for each particular situation.

There is a "best strategy" which is the same for all possible situations.

A hint:

if $a = \sum_{i = 0}^{\infty}a_i2^i$ and $b = \sum_{i = 0}^{\infty}b_i2^i$ where $a_i,b_i \in \{0,1\}$ define $a * b = \sum_{i = 0}^{\infty}c_i2^i$ where $c_i = 0$ if $a_i = b_i$ and $c_i = 1$ otherwise. Then you should work in the commutative group $\mathbb{N}, *$.

It says me nothing. And I hate algebraical methods, because high algebra (group theory and so on) is my weakest side.

Well in our group 0 is the neutral element and each element is its own inverse.

Given a certain situation $S$ let's call $a_i$ the number of heaps containing $i$ coins.
Define $A(s) = a_1 * a_3 * a_5 *...$ (notice there is only a finite number of terms).

[u]Claim[/u]
When $A(s) \neq 0$, the player who begins can force a victory.
If $A(s) = 0$ then the player who does not begin can force a victory.

To prove this you should prove three things:

1) If $A(s) = 0$ then the player who begins cannot end the game.
2) If $A(s) = 0$ then each move will give a situation $s'$ for which $A(s') \neq 0$.
3) If $A(s) \neq 0$ then there exists a move which results in a situation $s'$ such that $A(s') = 0$.

So, try it guys :)

Looks like in NIM-like games one should always look at the base $2$ representations of the numbers of items in the heaps. The solution to NIM is something similar.

[quote]The solution to NIM is something similar.[/quote]
It is my opinion too.

Well, let's look at a variation on the theme of Nim:

Consider the original Nim game, where we have a certain number of piles with some coins in each pile.  We must take at least one coin per turn, and any number of coins from at most one pile.

Now let's change each of coins in the first pile to, say groups of $a_1$ coins each; each of the coins in the second pile to groups of $a_2$ coins each etc, where $a_1, a_2, \ldots$ are all odd numbers.

In addition we create some more piles with groups of $b_1, b_2, \ldots$ coins similar to the above, where $b_1, b_2, \ldots$ are even. (We may shift groups between piles later on.)

Now we notice that the piles with an even number of coins don't really matter, because if player A takes 1 coin each from some of the groups with $b_1$ coins, player B can take 1 coin each from exactly those same groups, and those piles now have $b_1 - 2$, an even number of coins.  For every move of player A to some pile with groups of even number of coins, player B just mirrors that action.  So all that the first player has to do is to be the first person to make all the groups have an even number of coins.

So essentially, this game is just Nim in disguise.


Let $S_n$ be the sum of a sequence. Prove that the sequence is arithmetic if and only if $S_n=\frac{n(n+1)}{2}$.

Why if and only if.
According to what you wrote $a_1=1$.
So if a sequence $a_n$ is an arithmetic sequence, then $a_1=1$, but it's not true.
Trivial counterexaple: $5,10,15,...$
I think it should be like this:
Let $S_n$ be a sum of a sequence $a_n$ and $S_n=\frac{n(n+1)}{2}$. Prove, that $a_n$ is an arithmetic sequence. If yes, here is the solution:

$\sum_{k=1}^{n-1} a_k=\frac{(n-1)n}{2}$
$\sum_{k=1}^{n} a_k=\frac{n(n+1)}{2}$
$\sum_{k=1}^{n+1} a_k=\frac{(n+1)(n+2)}{2}$

We subtract the second equation from the third and we get:

$a_{n+1}=\frac{(n+1)(n+2)}{2}-\frac{n(n+1)}{2}$

Now we subtract the first equation from the second and we have:

$a_n=\frac{n(n+1)}{2}-\frac{(n-1)n}{2}$

$a_{n+1}-a_n=\frac{(n+1)(n+2)}{2}-\frac{n(n+1)}{2}-(\frac{n(n+1)}{2}-\frac{(n-1)n}{2})$
$a_{n+1}-a_n=\frac{1}{2}(n^2+2n+n+2-n^2-n-n^2-n+n^2-n)$
$a_{n+1}-a_n=1$, and $a_1=1$, so $a_n$ is an arithmetic sequence


Has anyone here done the math program at UM? How is it (in general)? Also, how generous is the merit aid?

I went to grad school at UM and know a bit about the honors classes.  My guess is that experiences in the program vary widely depending on who happens to be teaching the courses you take.  The teaching at UM is pretty uneven, unfortunately.  The content of the courses is very good.

How generous the merit aid is depends on how much money the department has at the time---it's a state school, and is also supported by the federal government, so their funding levels depend to some extent on what's going on in the state and federal governments at any given time.  I think they have a VIGRE grant right now, so the merit aid should be pretty good (though they might not have included the honors program in their VIGRE).


In any triangle  ABC  prove that
[tex] ab+bc+ca \leq 2R(m_a + m_b + m_c) [/tex]

Thanks!

We have: [tex]2R(m_a+m_b+m_c)\geq 2R(h_a+h_b+h_c)=ab+bc+ca[/tex].

The stronger following inequality also holds:
   $2R(m_a+m_b+m_c) \geq a^2+b^2+c^2 $ by proving $4Rm_a \geq b^2+c^2$ :D


abstract algebra
linear algebra
matrix
group theory
superior algebra
superior algebra unsolved

Hi all

Quick question: Why is it that if we have a representation of a finitely generated abelian group over an algebraically closed field, then one can choose a basis such that every group element is represented by a diagonal matrix? I know that for any one element we can choose a basis such that it is a diagonal matrix, but I am not sure how to use the abelian property to show that we can find one basis that works for all elements. =/ The only time I can think of when this is obviously true is when there is an element g such that its representation has all its eigenvalues of multiplicty 1 but in general I can't think of a proof.

Thanks for the help.

Any family of diagonalizable matrices that commute with each other is simultaneously diagonalizable. There's a proof of the two-matrix case [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?&t=175612]here[/url], and extending to more is simple.


group theory
abstract algebra
superior algebra
superior algebra unsolved

Prove that $ A_n$ is the only subgroup of $ S_n$ of index less than $ n$.

Consider a subgroup $ H$ of index less than $ n$. Then consider the left action of $ S_n$ on $ S_n/H$. This induces a homomorphism from $ S_n$ to $ S_m$, where $ m \equal{} \left| \frac {S_n}{H} \right| < n$. Therefore this map has a nontrivial kernel lying in $ H$. For $ n \ge 5$, the only nontrivial normal subgroup is $ A_n$. Thus we are done for $ n \ge 5$. For $ n \equal{} 1,2,3,4$ we can finish with a case by case analysis.


Να και μια συνδυαστική για να κάνουμε τη διαφορά :lol: :
Για κάθε $ n\geq2$ βρείτε το μεγαλύτερο θετικό ακέραιο $ k$ για τον οποίο μπορούμε να διαλέξουμε  $ k$ διαφορετικά στοιχεία από το σύνολο $ \{ 1,2,...,n\}$ έτσι ώστε το άθροισμα κάθε ζευγαριού από τους  $ k$ ακεραίους που επιλέξαμε να μη διαρείται από τη διαφορά τους.

Ονομάζω $ k_n$ τον μέγιστο $ k$ για το σύνολο $ \{1,2,...,n\}$. Βρίσκουμε $ k_2 \equal{} 0,k_3 \equal{} 0,k_4 \equal{} 2,k_5 \equal{} 2,k_6 \equal{} 2$ γιατί τα (1,4),(1,5),(1,6)και (2,5) είναι τα μόνα ζεύγη $ (x,y)$ με $ 1\le x\le6$ και $ 1\le y\le6$ και $ x < y$ που ικανοποιούν τη σχέση $ y \minus{} x\nmid y \plus{} x$. Τώρα θα δείξουμε επαγωγικά αν $ k_{3m \plus{} 1} \equal{} m \plus{} 1$ και  $ k_{3m \plus{} 2} \equal{} m \plus{} 1$ και $ k_{3m \plus{} 3} \equal{} m \plus{} 1$ τότε $ k_{3m \plus{} 4} \equal{} m \plus{} 2$ και $ k_{3m \plus{} 5} \equal{} m \plus{} 2$ και $ k_{3m \plus{} 6} \equal{} m \plus{} 2$.
Ισχύει ότι $ k_i\le k_{i \plus{} 1}\le k_i \plus{} 1$ για κάθε $ i\ge4$. Η πρώτη ανισότητα είναι προφανής. Για τη δεύτερη αν $ k_{i \plus{} 1}\ge k_i \plus{} 2$ τότε θα υπάρχει σύνολο που έχει τουλάχιστον $ k_i \plus{} 2$ στοιχεία από το σύνολο $ \{1,2,3,...,i \plus{} 1\}$ άρα τουλάχιστον $ k_i \plus{} 1$ από αυτά ανήκουν στο $ \{1,2,3,...,i\}$ άρα $ k_i\ge k_i \plus{} 1$, άτοπο. Άρα $ k_{i \plus{} 1}\le k_i \plus{} 1$
Το σύνολο $ \{1,4,7,...,3m \plus{} 4\}$ έχει $ m \plus{} 2$ στοιχεία και ανά 2 στοιχεία ικανοποιούν τη σχέση $ y \minus{} x\nmid y \plus{} x$ άρα $ k_{3m \plus{} 4}\ge m \plus{} 2$. Όμως $ k_{3m \plus{} 4}\le k_{3m \plus{} 3} \plus{} 1 \equal{} m \plus{} 2$ . Άρα $ k_{3m \plus{} 4} \equal{} m \plus{} 2$.
Ισχύει ότι $ m \plus{} 2 \equal{} k_{3m \plus{} 4}\le k_{3m \plus{} 5}\le k_{3m \plus{} 4} \plus{} 1 \equal{} m \plus{} 3$. Αν $ k_{3m \plus{} 5} \equal{} m \plus{} 3$ τότε θα υπάρχει σύνολο που έχει $ m \plus{} 3$ στοιχεία από το σύνολο $ \{1,2,3,...,3m \plus{} 5\}$ και επειδή $ k_{3m \plus{} 4} \equal{} m \plus{} 2$ τότε στο σύνολο που θα έχει $ m \plus{} 3$ στοιχεία θα πρέπει να περιέχει το $ 3m \plus{} 5$, γιατί αλλιώς  $ m \plus{} 2 \equal{} k_{3m \plus{} 4}\ge m \plus{} 3$, όμως $ (3m \plus{} 5) \minus{} (3m \plus{} 4)\mid (3m \plus{} 5) \plus{} (3m \plus{} 4)$ άρα το $ 3m \plus{} 4$ δεν θα ανήκει στο σύνολο άρα το σύνολο θα περιέχει τουλάχιστον $ m \plus{} 2$ στοιχεία $ \le 3m \plus{} 3$ άρα $ m \plus{} 1 \equal{} k_{3m \plus{} 3}\ge m \plus{} 2$, άτοπο. Άρα $ k_{3m \plus{} 5} \equal{} m \plus{} 2$
Ισχύει ότι $ m \plus{} 2 \equal{} k_{3m \plus{} 5}\le k_{3m \plus{} 6}\le k_{3m \plus{} 5} \plus{} 1 \equal{} m \plus{} 3$. Αν $ k_{3m \plus{} 6} \equal{} m \plus{} 3$ τότε θα υπάρχει σύνολο που έχει $ m \plus{} 3$ στοιχεία από το σύνολο $ \{1,2,3,...,3m \plus{} 6\}$ και επειδή $ k_{3m \plus{} 5} \equal{} m \plus{} 2$ τότε στο σύνολο που θα έχει $ m \plus{} 3$ στοιχεία θα πρέπει να περιέχει το $ 3m \plus{} 6$ γιατί αλλιώς  $ m \plus{} 2 \equal{} k_{3m \plus{} 5}\ge m \plus{} 3$, όμως $ (3m \plus{} 6) \minus{} (3m \plus{} 4)\mid (3m \plus{} 6) \plus{} (3m \plus{} 4)$ και $ (3m \plus{} 6) \minus{} (3m \plus{} 5)\mid (3m \plus{} 6) \plus{} (3m \plus{} 5)$ άρα το $ 3m \plus{} 4$ και το $ 3m \plus{} 5$ δεν θα ανήκουν στο σύνολο άρα το σύνολο θα περιέχει τουλάχιστον $ m \plus{} 2$ στοιχεία $ \le 3m \plus{} 3$ άρα $ m \plus{} 1 \equal{} k_{3m \plus{} 3}\ge m \plus{} 2$, άτοπο. Άρα $ k_{3m \plus{} 6} \equal{} m \plus{} 2$. Άρα η επαγωγή ολοκληρώθηκε.
Κάθε σύνολο $ \{1,4,...,3t \plus{} 1\}$ αποτελεί παράδειγμα για τους $ n \equal{} 3t \plus{} 1,3t \plus{} 2,3t \plus{} 3$ γιατί ανά 2 στοιχεία ικανοποιούν τη σχέση $ y \minus{} x\nmid y \plus{} x$.

Γειά σου ρε Τάσο!!!! Έγραψες πάλι!!!!!! ( Νομίζω ξέρεις ποιός ειμαι ε?)

Τάσο ωραία λυση :10:  . Μπράβο!!!


geometry
3D geometry
sphere
analytic geometry

Eight spheres of radius 1, one per octant, are each tangent to the coordinate planes. What is the radius of the smallest sphere, centered at the origin, that contains these eight spheres?

$ \textbf{(A)}\ \sqrt 2\qquad
\textbf{(B)}\ \sqrt 3\qquad
\textbf{(C)}\ 1 \plus{} \sqrt 2\qquad
\textbf{(D)}\ 1 \plus{} \sqrt 3\qquad
\textbf{(E)}\ 3$

See the centers of the spheres,you will find a cube with its edge of 2,then it's easy to get the answer.The answer is D(sqr(3)+1). :P

Please hide your answer.

[hide="Answer"]We have each sphere internally tangent to the larger sphere. Each smaller sphere has center at $(\pm 1,\pm 1,\pm 1)$, so the distance from there to the origin is $\sqrt{(\pm 1)^2+(\pm 1)^2+(\pm 1)^2}=\sqrt{3}$, and the radius on the other side of the sphere's center is $1$, so we have $1+\sqrt{3}\Rightarrow \boxed{D}$.[/hide]

Sorry for reviving the post.
If I am not asking for too much, can someone post a diagram.
Also, for problems like this, how can tell instantly that the "coordinate planes" is refering to x,y,z coordinate plane?
Thanks.


Proof that:

$ \tfrac{1}{2} \plus{} \tfrac{1}{2}\cos(\pi x) \le (1 \minus{} x^2)^2$
for $ \minus{} \infty \le x \le \infty$, but especially for $ \minus{} 1 \le x \le 1$ if a proof for this range is simpler

By expanding and simplification:

$ \cos(\pi x) \le 1 \minus{} 4x^2 \plus{} 2x^4$

This is as fas as I came. I tried analyzing derivatives up to the 3rd, and didn't find a anything there.

Try using an over approximation in the taylor series of $ \cos(\pi x)$.

Maybe we can use the following identity for the left side:
\[ \frac{1}{2} \plus{} \frac{1}{2} \cos(\pi x) \equal{} \cos^2(\frac{\pi}{2} x) \, .
\]

I tried taylor series. no luck.

I tried [b]Ravi B[/b]'s identity. I came up with this:

$ \cos^2 \tfrac{1}{2}\pi x \le (1 - x^2)^2$

Taking square root:
$ \cos \tfrac{1}{2}\pi x \le 1 - x^2 \quad \mbox{for} \quad 0 < |x| < 1$

Divide $ x$ by $ \tfrac{1}{2}\pi$:
$ \cos x \le 1 - (\frac {2}{\pi}x)^2 \quad \mbox{for} \quad 0 < |x| < \tfrac{1}{2}\pi$

Dividing by 2 and rewriting:
$ \tfrac{1}{2} - \tfrac{1}{2}\cos x \ge (\frac {\sqrt {2}}{\pi}x)^2 \quad \mbox{for} \quad 0 < |x| < \tfrac{1}{2}\pi$

Taking square root again:
$ \sin \tfrac{1}{2}x \ge \frac {\sqrt {2}}{\pi}x \quad \mbox{for} \quad 0 < x < \tfrac{1}{2}\pi$

Enumerating the formulae and derivatives:
\begin{align} \sin \tfrac{1}{2}x \\
\frac {\sqrt {2}}{\pi}x \\
\frac {\partial}{\partial x} \sin \tfrac{1}{2}x & = \frac {1}{2} \cos \frac {1}{2}x \\
\frac {\partial}{\partial x} \frac {\sqrt {2}}{\pi}x & = \frac {\sqrt {2}}{\pi} \end{align}

In the range $ 0 \le x \le \tfrac{1}{2}\pi$, derivative $ \mbox{(3)}$ is positive and is higher than derivative $ \mbox{(4)}$ at $ x = 0$. Therefore, the linear line $ \mbox{(2)}$ which intersects $ \mbox{(1)}$ at, and only at $ x = 0 \lor x = \tfrac{1}{2}\pi$ within this range must be greater than or equal to $ \mbox{(1)}$ within this range.

Is this proof correct? Can't it be done simpler?

[edit]writing style[/edit][edit]fixed small errors[/edit]

Your proof looks correct to me.  Nice work.

[quote="Zom-B"]No it wasn't/isn't. I already found and fixed 2 small errors. I found another one that's not as critical. I intentionally didn't fix it.

Proof theeself worthy by correcting me.[/quote]

One could say that there's a hole in the solution as you never consider negative values for the roots. I'm positive that those wouldn't lead anywhere, but for a rigorous proof you'd have to consider them.


combinatorics solved
combinatorics
Sequences
Recurrence
duplicate

A chameleon repeatedly rests and then catches a fly. The first rest is for a period of 1 minute. The rest before catching the fly $2n$ is the same as the rest before catching fly $n$. The rest before catching fly $2n+1$ is 1 minute more than the rest before catching fly $2n$.

How many flies does the chameleon catch before his first rest of 9 minutes?
How many minutes (in total) does the chameleon rest before catching fly 98?
How many flies has the chameleon caught after 1999 total minutes of rest?

[color=#cc0000][mod says: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=19786& ][/color]

for a solution just check out:

 http://www.kalva.demon.co.uk/short/soln/sh99c3.html

cheers!