function
group theory
abstract algebra
algebra unsolved
algebra

Find all non-decreasing functions $f: \mathbb R \to \mathbb R$ satisfying \[ f(x\plus{}f(y))\equal{}f(f(x))\plus{}f(y),\quad \forall x,y \in \mathbb R.\]

Let $ a\equal{}f(f(0))$. Then $ x\equal{}0$ give $ f(f(y))\equal{}f(y)\plus{}a$, $ y\equal{}0$ give $ f(0)\equal{}0\to a\equal{}0$. Therefore $ f(f(x))\equal{}f(x),f(0)\equal{}0$. It mean, that $ f$ is proektor $ f: R\to D$
$ x\equal{}\minus{}f(y)$ give $ f(\minus{}f(y))\equal{}\minus{}f(y)$. It mean, that $ D$ is symmetric.
Because $ f$ is non decrease, exist $ b\equal{}f(0^\plus{})$. If $ b>0$, then for $ 0<x\le b$ we get $ f(b)\le f(f(x))\equal{}f(x)\le b$
and for $ \minus{}b<x<0$ we get $ f(\minus{}b)\ge f(f(x))\equal{}f(x)\ge \minus{}b$. Together it give $ b\equal{}0$ and $ f$ is continiously in 0.
It give $ f(x)\equal{}0$ or $ f(x)\equal{}x$.

[quote="KDS"]Find all non decreasing functions $ f: R\to R$ satisfying $ f(x \plus{} f(y)) \equal{} f(f(x)) \plus{} f(y)$ $ \forall x,y \in R$[/quote]

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

$ P(0,0)$ $ \implies$ $ f(0) \equal{} 0$
$ P(0,x)$ $ \implies$ $ f(f(x)) \equal{} f(x)$ and so $ P(x,y)$ may be written $ Q(x,y)$ : $ f(x \plus{} f(y)) \equal{} f(x) \plus{} f(y)$
$ Q( \minus{} f(x),x$ $ \implies$ $ f( \minus{} f(x)) \equal{} \minus{} f(x)$

So $ f(\mathbb R)$ is an additive subgroup of $ \mathbb R$ and $ f(x) \equal{} x$ $ \forall x\in f(\mathbb R)$. Then :

$ f(x) \equal{} 0$ $ \forall x$ is a solution.
If $ f(x)$ is not the zero function, $ f(\mathbb R)\cap\mathbb R^ \plus{} _*\ne \emptyset$ and let $ a \equal{} \inf (f(\mathbb R)\cap \mathbb R^ \plus{} _*)$

1) $ a \equal{} 0$
So $ f(\mathbb R)$ is dense in $ \mathbb R$ and so $ f(x) \equal{} x$ $ \forall x$ since $ f(x)$ is non decreasinf and since $ f(x) \equal{} x$ for all $ x$ in a set dense in $ \mathbb R$

2) $ a > 0$
Then $ f(\mathbb R) \equal{} a\mathbb Z$
$ Q(x,a)$ $ \implies$ $ f(x \plus{} a) \equal{} f(x) \plus{} a$ and so $ f(x)$ is defined exaclty on $ \mathbb R$ when it's defined on $ [0,a)$
And since $ f(0) \equal{} 0$, $ f(a) \equal{} a$ and $ f(x)$ non decreasing,
either $ \exists b\in(0,a]$ such that $ f(x) \equal{} 0$ $ \forall x\in[0,b)$ and $ f(x) \equal{} a$ $ \forall x\in[b,a)$ and so $ f(x) \equal{} a[\frac {x \plus{} a \minus{} b}a]$

either $ \exists b\in[0,a)$ such that $ f(x) \equal{} 0$ $ \forall x\in[0,b]$ and $ f(x) \equal{} a$ $ \forall x\in(b,a)$ and so $ f(x) \equal{} \minus{}a[\frac { \minus{} x \plus{} b}a]$

And it is easy to check that these two functions indeed are solutions.

3) synthesis of solutions

$ f(x) \equal{} 0$ $ \forall x$

$ f(x) \equal{} x$ $ \forall x$

$ f(x) \equal{} a[\frac {x \plus{} b}a]$ with $ a > b \ge 0$

$ f(x) \equal{} \minus{}a[\frac { \minus{} x \plus{} b}a]$ with $ a > b \ge 0$


[hide]Add 1 to both sides. $(m+ 1)(n+1) = 14$. The factors of 14 are $(1, 14)$ and $(2, 7)$. This makes $m = 0$ and $n = 13$, and $m = 1$ and $n = 6$. Of course the values can be reversed so $n$ can also equal 0 and 1.[/hide]

yeah, when you look at that and other equations similar, always look to factor.  Like unit fractions: 1/x+1/y=a/b You can factor it all the way down to (ax-b)(ay-b)=b 2
Factoring is reallly nice

Also tarquin: what about m=-2 n=-15, and m=-3 n=-8
(and switching m and n of course)

I found the positive integer values of $m$ and $n$. Technically, there is an infinite amount.

Oh I thought he said integers so it would be finite, so I did negative too

Sorry about that.  I meant positive integers.

If he had been looking for anything, it would be m=(13-n)/(n+1). As is, (m+1)(n+1)=14, so m+1=7 and n+1=2 or vice versa, and m,n=6,1.

[hide]This is called Simon's Favorite factoring trick. (AoPS t-shirts!)It says that
xy+x+y=z --> (x+1)(y+1)=z+1
just apply
(n+1)(m+1)=14
factors of 14= 1,2,7,14
each factor can be (m+1) or (n+1), so minus 1 to each
1,6 (and negative stuff+0+13, but that's extraneous, positive remember, and 13 is counterpart of 0)
>>1,6<<
[/hide]

[quote="jb05"]Where did that name come from (Simon's Favorite Factoring Trick)? I've never heard it before I came to this site.[/quote]
It is an inside joke among AoPS users.  Simon is an active member of this Web site, and a moderator of some of the more advanced forums.  A search of the phrase revealed [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=43468#p43468]an early self-reference to the term[/url].

[b][size=200]<3 Simon[/size][/b]

[quote="h_s_potter2002"]If mn+m+n = 13, then what are the possible values of m and n?[/quote]

[hide="something"]
mn + m + n + 1 = 14
(m + 1)(n + 1) = 14

[b](0, 13)
(1, 6)
(6, 1)
(13, 0)
[/b]

[/hide]


geometry
calculus
integration
analytic geometry
calculus computations

That's an odd choice of English; here's what I think you said, in standard language:
Find the area of the region bounded by:
(equations)

They say that math is the same in all countries, but this post shows the contrary. :)  English isn't my native language. Any idea on the (equations)?

There was no problem translating those; they're the same either way.

This is a routine calculus exercise, and I'd rather leave it to someone else.

a)
Complete the squares!
This region, call it $\mathcal{D}$ is a circle $(x-1)^{2}+y^{2}=4$ centered at $(1,0)$ and circle $(x-2)^{2}+y^{2}=1$ centered at $(2,0)$ and cut by the line $y=x$ and the line $y=0$. Draw it!. Now the area of it is equal to the area of the region when $x\in [0,1]$ and the region when $x\in [1,2]$. Why I chose these point will become clear if you draw the figure, because between these points the regions are simply bounded by two curves, so we have

\[area(\mathcal{D})=\int_{0}^{1}dx\int_{\sqrt{1-(x-1)^{2}}}^{\sqrt{4-(x-2)^{2}}}dy+\int_{1}^{2}dx\int_{x}^{\sqrt{4-(x-2)^{2}}}dy \]

b)
This is much easier! Now $x=0$ and $y=0$ are the coordinate axes. $x+y=1$ is a strait line
intersecting these axes at $(0,1)$ and $(1,0)$, (why?). So the region becomes a right triangle. Draw it ! The area of this one is just half the unit [url=http://en.wikipedia.org/wiki/Unit_square]square[/url], that is $\frac12$

[color=green]Perhaps you or someone else could finish the integral.[/color]


function
real analysis
real analysis unsolved

Let $ f: [a, b]\to\mathbb{R}$ be a continuous and non-injective function such that $ f(a)=f(b)$. Prove that there are many infinitely $ x_{i}\neq x_{j}\in (a, b)$ such that $ f(x_{i})=f(x_{j})$.

This is pretty direct from the Intermediate Value Theorem.  My reasoning would be as follows:

If $ f$ is constant we are done.  If not, there is a $ c\in (a,b)$ such that $ f(c)>f(a)$ (without loss of generality, else consider $ -f$).  The Intermediate Value theorem says that all values between $ f(c)$ and $ f(a)$ are achieved on the interval $ [a,c]$.  Similarly, all values between $ f(c)$ and $ f(a)$ are achieved on the interval $ [c,b]$.  These values provide the infinite set that you are looking for.


How do you get the symbol for the Real part function (Re(z)) and the Imaginary part function (Im(z)) in LaTeX?


Let $ d$ and $ e$ denote the solutions of $ 2x^2\plus{}3x\minus{}5\equal{}0$. What is the value of $ (d\minus{}1)(e\minus{}1)$?

$ \textbf{(A)}\ \minus{}\frac{5}{2} \qquad
\textbf{(B)}\ 0 \qquad
\textbf{(C)}\ 3 \qquad
\textbf{(D)}\ 5 \qquad
\textbf{(E)}\ 6$

$ (d \minus{} 1)(e \minus{} 1) \equal{} de \minus{} d \minus{} e \plus{} 1 \equal{} de \minus{} (d \plus{} e) \plus{} 1$

By Vieta's, $ de \equal{} \frac { \minus{} 5}{2}$ and $ d \plus{} e \equal{} \frac { \minus{} 3}{2}$

Thus $ de \minus{} (d \plus{} e) \plus{} 1 \equal{} \minus{} 2.5 \plus{} 1.5 \plus{} 1 \equal{} 0$

Alternatively, we quickly see 1 is a root, meaning either $ d \minus{} 1$ or $ e \minus{} 1$ is 0, making the product 0. Either way, the answer is $ \boxed{\text{B}}$

If I understand it well so its B
------------------------------
LOL when I post this I find you come on the first so I edit this  :mad:   :)  :D
But what is "Vieta's" thing. Can you explain it please? I do it by the quadratic formula.

Vieta's formulas are a way of relating the roots of a polynomial to its coefficients. For a cubic, for example, we have $ ax^3\plus{}bx^2\plus{}cx\plus{}d\equal{}a(x\minus{}r_1)(x\minus{}r_2)(x\minus{}r_3)$. Dividing by $ a$ and multiplying out the RHS, we have $ x^3\plus{}\frac{b}{a}x^2\plus{}\frac{c}{a}x\plus{}\frac{d}{a}\equal{}x^3\minus{}(r_1\plus{}r_2\plus{}r_3)x^2\plus{}(r_1r_2\plus{}r_2r_3\plus{}r_3r_1)x\minus{}r_1r_2r_3$. Since these two are the same polynomial, we have that $ r_1\plus{}r_2\plus{}r_3\equal{}\minus{}\frac{b}{a}$, $ r_1r_2\plus{}r_2r_3\plus{}r_3r_1\equal{}\frac{c}{a}$, and $ r_1r_2r_3\equal{}\minus{}\frac{d}{a}$. These can easily be generalized to all polynomials.

$ r_1$, $ r_2$, and $ r_3$ are the roots of the polynomial.

[quote="hasan4444"]:(
I don't know a lot of concepts here but what a variable mean when its have a subscript. I only know it in matrices because that what I studied until now  :( .[/quote]

Usually, a subscript is used in a case where many variables are involved and there are too many to be represented by letters.

Suppose a problem had 26 different variables all represented by distinct letters. It wouldn't be so fun to figure out what variable has what would it?

In this case, they are used for readability. It's easier to see that all of $ r_i$ are roots because of the letter $ r$.

This is a great example of a problem where using Vieta's is less important than [i]understanding[/i] Vieta's.

[hide="Let me explain"] Vieta's is based on factorization:  we write $ 2x^2 \plus{} 3x \minus{} 5 \equal{} 2(x \minus{} d)(x \minus{} e)$.  Now, given this expression, how would we go about computing $ (d \minus{} 1)(e \minus{} 1)$?

Well, those two expressions look awfully similar.  Substituting $ x \equal{} 1$ gives $ 2(1 \minus{} d)(1 \minus{} e) \equal{} 2(d \minus{} 1)(e \minus{} 1) \equal{} 2 \plus{} 3 \minus{} 5 \equal{} 0$. [/hide]

vieta's just tells us that in a quadratic like this one, the product of the roots is $ \frac {c}{a}$ and the sum of the roots is $ \minus{} \frac {b}{a}$

where a= the coeficient of the $ x^2$terms
b= the coeficient of the x term
and c is the constant

expanding (d-1)(e-1) gives us de - (d+e) +1

we quickly notice that de is the product of the roots
d+e is the sum of the roots.

so we plug these in to get de= $ \minus{} \frac {5}{2}$
d+e = $ \frac {3}{2}$

for the solution we get $ \minus{} \frac {5}{2}\plus{}\frac {3}{2}\plus{}1 \equal{}\boxed {0}$

We expand $(d-1)(e-1)$, which gives $de - d - e + 1$, and regrouping, we have $de - (d+e) + 1$.

By vietas we have: $de = \frac{-5}{2}$, and $d+e = -\frac{3}{2}$.

Therefore we have $\frac{-5}{2} - \left(-\frac{3}{2}\right) + 1 \rightarrow -\frac{2}{2} + 1 \rightarrow \boxed{0}$.

$2x^2+3x-5=2(x-d)(x-e).$ Putting 1 both sides we get, $$2+3-5=2(1-d)(1-e)\implies0.$$ Is the correct answser......
Vietas Relation :love:


[hide="Hint"]How many two-digit integers have a remainder of 1 when divided by 3?[/hide]

[quote="now a ranger"]How many distinct four-digit numbers are divisible by 3 and have 23 as their last two digits?[/quote]
My was is pretty long but whatever.

[hide]Okay so we have this:_ _23. So the sum right now is 5. The closest multiple of 3 is 6. So the only ordered pair that works is 1 and 0 in that order. The next one is 9, so two digits have to be added to 4. All combinations are 4 and 0,3 and 1,2 and 2,1 and 4. The next one is 12. So two numbers have to be added to 7. The combinations are 7 and 0, 6 and 1, 5 and 2, 4 and 3, 3 and 4, 2 and 5, and 1 and 6. You realize that the sum the two numbers must add up to increases by three. So the next one is 10. The combinations are 9 1,8 2, 7 3, 6 4, 5 5, 4 6, 3 7, 2 8, and 1 9. Then the next one is 13. The combos for that are 9 4, 8 5, 7 6, 6 7, 5 8, and 4 9. Then the combos for 16 are 9 7, 8 8, and 7 9. Then 19 is one you can't do so it stops here. Count all the solutions and you get 30. [/hide]
I'm sure there is a easier, and faster sloution than mine.

[quote="now a ranger"]How many distinct four-digit numbers are divisible by 3 and have 23 as their last two digits?[/quote]

[hide="solution"]The sum of the first tw digits must be 1 mod 3 because the sum of the last two is 2 mod 3.

When the first digit is one, the numbers are 10, 13, 16, and 19.

When the first digit is two, the numbers are 22, 25, an 28.

When the third digit is three, the numbers are 31, 34, and 37.

It repeats again for 4, 5, 6, 7, 8, an 9 because we tested all the residues mod 3.  So 3 times 10 is [b]30[/b].[/hide]


topology
geometry
rectangle
analytic geometry
real analysis
real analysis unsolved

See here for a definition: http://www.math.wisc.edu/~angenent/376.2005/zerocontent-problems.pdf

Here is my question: the set $ (x,y)$ such that $ x\equal{}0$ and $ y\equal{}\frac{1}{2^k}$ where $ k$ is a positive integer obviously has zero content.

However, does the set: $ (x,y)$ where $ x\equal{}\frac{1}{2^i}$ and $ y\equal{}\frac{1}{2^j}$ have zero content?

These sets have a one-to-one correspondence obviously, but if $ S_1$ and $ S_2$ are bounded sets that have a bijection, then if one has zero content, does the other?

No. But all countable sets have zero content. (Added: I was thinking of Hausdorff content, which is different from the thing defined in the PDF file.)

[quote="Altheman"]
However, does the set: $ (x,y)$ where $ x \equal{} \frac {1}{2^i}$ and $ y \equal{} \frac {1}{2^j}$ have zero content?[/quote]

take the `first' rectangle in your covering to be a square centered at $ 0$ with sides parallel to the coordinate axes and side length $ \ell$.  This square covers all but finitely many points (although the exact number depends on $ \ell$), which you can cover with arbitrarily small area.

There are still infinitely many points outside that square, but I think you mean we only need finitely many strips to cover the points outside that square.

You meant what you said, but you weren't right ;)

The points $ \left(\frac{1}{2}, \frac{1}{2^m}\right)$ won't be in your square.  You need one (arbitrarily narrow) strip along each axis.

[quote="JBL"]You meant what you said, but you weren't right ;)
[/quote]

I feel like sincerity is all that matters.  Anyways, I guess I had a bad mental image of the set at hand, I thought it looked like a set of points getting increasingly dense around the origin, whereas it is a set of points which gets dense along the coordinate axes.

Hi all!  This is my first time posting on this forum after lurking a bit, but this looks like a question I can handle so I figured I'd register and attempt an answer.   :P

There's an easy proof of what mlok said, that any countable set has zero content (by this definition).  Consider the set $ X \equal{} \{x_i | i \in {\mathbb Z}^\plus{}\}$.  Choose $ \epsilon > 0$.  Let the rectangle $ R_i$ be the square centered about $ x_i$ with side length $ \frac{\sqrt{\epsilon}}{i}$.  It's clear that $ X \subset \cup_i R_i$.  Then

\[ \sum_{i\equal{}1}^\infty \mathrm{area}(R_i) \equal{} \sum_{i\equal{}1}^\infty \left(\frac{\sqrt{\epsilon}}{i}\right)^2 \equal{} \epsilon \sum_{i\equal{}1}^\infty \frac{1}{i^2} \equal{} \frac{\epsilon\pi^2}{6}\]

$ \epsilon$ can be arbitrarily small, so $ X$ has zero content.


Melinda will roll two standard six-sided dice and make a two-digit number with the two numbers she rolls. For example, if she rolls a 6 and 3, she can either form 36 or 63. What is the probability that she will be able to make an integer between 10 and 20? Express your answer as a common fraction.

At least one number must be an one, but other than that, there are no restrictions. So the answer (if I'm correct) is $ \frac{25}{36}$.

it seems to me like you found the probability she [b]cannot[/b] get a number between 10 and 20

the correct answer is $ \frac{11}{36}$

let's think about this

if the first die shows a one, then the second die can show any number
if the second die shows a one, then the first die can show any number

each of these occurs with a probability of $ \frac{1}{6}$

however, we double counted the probability we get a $ (1,1)$, which shows up with a $ \frac{1}{36}$ probability

so our answer is $ \frac{1}{6}\plus{}\frac{1}{6}\minus{}\frac{1}{36}\equal{}\frac{11}{36}$

But: the numbers that you can make are

[b]11[/b], [b]12,[/b] 21, [b]13[/b], 31, [b]14[/b] 41 [b]15[/b] 51 [b]16[/b] 61 22 23 32 24 42 25 52 26 62 33 34 43 35 53 36 63 44 45 54 46 64 55 56 65 66

The ones in bold are the numbers between 10 and 20. There are 6. So then there should be a $\frac{6}{36} probability.

Why doesn't my way work?????????

The mistake you are making is that you are thinking that the first die = first digit and second die = second digit which is not what the problem says.

Therefore, we would double you result and get rid of $(1,1)$ once, because that would over counted.

[hide=Solution]The numbers $11,$ $12,$ $13,$ $14,$ $15,$ $16,$ $21,$ $31,$ $41,$ $51,$ and $61$ work. There are $11$ in total and $36$ different ways to roll the dice so the answer is $\frac{11}{36}.$[/hide]


This is from the AOPS VOl.1 book:

If q is an integer that can be expressed as the sum of two integer squares, show that both 2q and 5q can also be expressed as the sum of two integer squares. (mandelbrot #2)

-- Don't answer the question for me, just help me out. I have so far q= x^2 + y^2, or (x+y)^2 -2xy. However, i'm not sure what the question is asking for 2q and 5q. Does it mean that 2q and 5q can be expressed in the same way as q (x^2 + y^2, given some manipulations) ?

For the first one try grouping it into

[hide]
$ a^2\plus{}SOMETHING\plus{}b^2\plus{}a^2\minus{}SOMETHING\plus{}b^2$

[hide="Spoiler Alert!"]
If something=2ab, then we have to easy to factor squares.
[/hide]

[/hide]

thanks mewto, i was actually thinking along those lines but couldn't make it clear what that something should be. now that i see it, i feel pretty retarded  :oops:
Thanks

Let q=a^2+b^2
q=(a+b)^2-2ab
now add q to both sides
(rem q=a^2+b^2)
hence 2q=(a+b)^2+(a-b)^2. :lol:

Let $ q\equal{}a^2\plus{}b^2$

$ 5q\equal{}5a^2\plus{}5b^2\equal{}(a\plus{}2b)^2\plus{}(2a\minus{}b)^2$. If 2a<b, then reverse their order.


function
complex analysis
complex analysis unsolved

[quote="Ravi B"]Hmm, isn't $f(x) = (x^2 + x)/2$ a counterexample?[/quote]

 Yes yes, I've edited my post!! :D

[quote="dickchimney"]Suppose that $f$ is an entire function which satisfies : $f(0)=0$,$f(1)=1$ ,$f'(0)$ and $f'(1) \neq 0$. And $f(x) \neq 0 , 1$ for any other value of $x$
 Prove that $f$ is the identity map[/quote]

The conditions are equivalent to existence of entire $g,h$ such that:

$f(x) = x e^{g(x)}$  and
$f(x) - 1 = (x-1)e^{h(x)}$.

Eliminating $f$,

$ x  = \frac{1 - e^h}{e^g - e^h}$

Therefore, $e^{g(x)}=1$ only when $x$ = 1, which means that $g(x)$ omits infinitely many multiples of $2 \pi i$.  This is impossible by Picard's theorem, unless $g(x)$ is constant, i.e. $f$ is linear and so $f(x) = x$.

[quote="dickchimney"][quote="fleeting_guest"]
$ x  = \frac{1 - e^h}{e^g - e^h}$

Therefore, $e^{g(x)}=1$ only when $x=1$ [/quote]

 What if $x \neq 1$ and $e^g=e^h=1$ ??. This is a possibility, right??[/quote]

Yes, but I don't see whether or not this destroys the argument above.
I will think about it more.


I am wondering which parameters define spacing before and after text paragraphs or \item parts. Thanks!

\parskip for paragraphs and \parsep plus \itemsep for lists. See [url=http://www.tex.ac.uk/cgi-bin/texfaq2html?label=complist]How to adjust list spacing[/url].


abstract algebra
superior algebra
superior algebra unsolved

Let $ (G, \cdot ) $ be a group. Show that
a) If $ \exists a \in G$ and $n \in {\mathbb N}, n$ even , such that $x^{n+3}=a^{n+2}x^{n+1}a^n$ for any $x \in G$ then $ (G, \cdot ) $ is abelian;
b) If $ \exists a \in G$ and $n,p,q \in {\mathbb N}$ such that $|p-q|=1$ and $a^nx^{2n+p}a^{n+q}=x^{n+q}a^{2n+p}x^{n}$ for any $x \in G$ then $ (G, \cdot ) $ is abelian.

 :ninja:

Let me try

a) substitute $x=a$ we obtain
\[
a^{n+3}=a^{3n+3}\Leftrightarrow a^{2n}=e
\]

substitute $x=e$ we obtain
\[
e=a^{2n+2}
\]
Hence $|G|\mid 2n$ and $|G|\mid 2n+2$. It follows taht $|G|\mid 2$. So $G$ is the trivial group or a group with order 2, both of them are commutative.

For part b)

Substitute $x=e$ to obtain
\[
a^{2n+q}=a^{2n+p}\Leftrightarrow a^{|p-q|}=e\Leftrightarrow a=e (\text{ by assumption})
\]

Since $a=e$, then we have
\[
x^{2n+p}=x^{2n+q}
\]
which implies (as above) that $x=e$. So $G$ is the trivial group.

OOpss a) was wrong..........

from $a^{2n}=e$ and $a^{2n+2}=e$ we obtain $ord(a)\mid 2$. So $a=e$ or $a$ has order 2.

For both cases we have $x^{n+3}=x^{n+1}$. So $x^2=e$, and it is well known that a group with this property is abelian.


function
algebra
functional equation
real analysis
real analysis unsolved

all analytic $ f: \mathbb{R}\to\mathbb{R}$ such that $ 3f(x)\minus{}2f(f(x))\equal{}x$ .....

.... is there anything but $ f(x)\equal{}x$ ??

[hide]
Maybe $ f(x)\equal{}\frac {\minus{}1}{3}x$ also statisfies the condition ?
[/hide]
The most important question is : How can we be sure that they are the only solution for this problem ? :)

Suppose $ f : \mathbb{R} \to \mathbb{R}$ is continuous, satisfying the functional equation $ 3f(x) \minus{} 2f(f(x)) \equal{} x$.

Put $ g_0(x) \equal{} f(x) \minus{} x$ and $ g_{n\plus{}1}(x) \equal{} g_n(f(x))$. Then we claim that $ g_{n}(x) \equal{}2^{\minus{}n} g_0(x)$. When $ n \equal{} 1$, it is clear from the given functional equation, and the remaining case immediately follows.

This estimation shows that $ f^n(x)$ is a Cauchy sequence on any compact set $ K \subset \mathbb{R}$. So $ f^n(x)$ converges to a continuous function $ \tilde{f}$, which satisfies

$ 1. \ \tilde{f}(x) \equal{} \tilde{f}(f(x)) \equal{} f(\tilde{f}(x)) \equal{} \tilde{f}(\tilde{f}(x))$

$ 2. \ \tilde{f}(x) \minus{} x \equal{} \sum_{k\equal{}0}^{\infty} g_k(x) \equal{} 2 (f(x) \minus{} x) \quad \Longrightarrow \tilde{f}(x) \minus{} f(x) \equal{} f(x) \minus{} x$.

Now put $ S \equal{} \{ x \, | \, f(x) \equal{} x \}$. Then from the condition above, we find that $ x \in S$ if and only if $ x \in \tilde{f}(\mathbb{R})$, if and only if $ \tilde{f}(x) \equal{} x$. Then $ S \equal{} \tilde{f}(\mathbb{R})$ is a closed connected set.

If $ S$ consists of one element $ a$, then we have $ f(x) \equal{} (a\plus{}x)/2$, which really is a solution to the equation.

Otherwise, put $ a \equal{} \inf S$ and $ b \equal{} \sup S$. If $ a$ is finite, then continuity of $ \tilde{f}$ shows that we must have $ \tilde{f}(x) \equal{} a$ for $ x < a$. In this case, we again have $ f(x) \equal{} (a\plus{}x)/2$ for $ x < a$. Similarly, if $ b$ is finite, then $ f(x) \equal{} (b\plus{}x)/2$ for $ x > b$.

Among these, only analytic solutions are $ f(x) \equal{} x$ and $ f(x) \equal{} x/2$.

[quote="sos440"]Among these, only analytic solutions are $ f(x) \equal{} x$ and $ f(x) \equal{} x/2$.[/quote]I think your reasoning also leads to the solutions $ \frac{x}{2}\plus{}c$ for each $ c\in \mathbb{R}$.

[quote="JoeBlow"]I think your reasoning also leads to the solutions $ \frac {x}{2} \plus{} c$ for each $ c\in \mathbb{R}$.[/quote]

Uh, I often make ridiculous mistakes... :blush: ...... You're right. Those are also solutions.


This is a problem from the National Sprint Round (1993-94) that's kind of bothering me:

Find the smallest possible value of x+y such that (1/x)+(1/y)=2/15 and x>y and x is not a multiple of y.

Btw, I heard you could do some weird factoring trick to do this problem. Does anyone know how to factor this thing?

P.S. Try to not post something along the lines: "I guessed and checked until I got <insert answer here>". And I want [b]solutions[/b], not just answers.

[quote="Monkey"]Find the smallest possible value of x+y such that (1/x)+(1/y)=2/15 and x>y and x is not a multiple of y.

Btw, I heard you could do some weird factoring trick to do this problem. Does anyone know how to factor this thing?[/quote]

This question (with slightly different wording) is in another active thread.  However, I will give an example of how to apply Simon's Favorite Factoring Trick:

\begin{eqnarray*}
\frac{1}{x}+\frac{1}{y}&=&\frac{2}{15} \\
15y+15x&=&2xy \\
0&=&2xy-15x-15y \\
0&=&xy-7.5x-7.5y \\
0&=&(x-7.5)(y-7.5)-56.25 \\
0&=&(2x-15)(2y-15)-225 \\
225&=&(2x-15)(2y-15)
\end{eqnarray*}

Now, we obtain every pair of factors of 225.  Each such ordered pair yields a solution to the equation.

\begin{eqnarray*}
225=1\times 225\Longrightarrow& (2x-15)=1,\quad(2y-15)=225& \\
225=3\times 75\Longrightarrow& (2x-15)=3,\quad(2y-15)=75& \\
225=5\times 45\Longrightarrow& (2x-15)=5,\quad(2y-15)=45& \\
225=9\times 25\Longrightarrow& (2x-15)=9,\quad(2y-15)=25& \\
225=15\times 15\Longrightarrow& (2x-15)=15,\quad(2y-15)=15& \Longrightarrow x=15,y=15 \\
225=25\times 9\Longrightarrow& (2x-15)=25,\quad(2y-15)=9& \Longrightarrow x=20,y=12 \\
225=45\times 5\Longrightarrow& (2x-15)=45,\quad(2y-15)=5& \Longrightarrow x=30,y=10 \\
225=75\times 3\Longrightarrow& (2x-15)=75,\quad(2y-15)=3& \Longrightarrow x=45,y=9 \\
225=225\times 1\Longrightarrow& (2x-15)=225,\quad(2y-15)=1& \Longrightarrow x=120,y=8
\end{eqnarray*}

The above equations lead to all 9 distinct positive integer solutions to the problem.  Given $x>y,$ there are 4 distinct positive integer solutions to be considered.

[Depending on the problem, you might also have to consider negative factors.  (For example, $225=-9\times-25,$ leads to the solution $x=3,y=-5$).]

[quote="rcv"]
Now, we obtain every pair of factors of 225.  Each such ordered pair yields a solution to the equation.

\begin{eqnarray*}
225=1\times 225\Longrightarrow& (2x-15)=1,\quad(2y-15)=225& \\
225=3\times 75\Longrightarrow& (2x-15)=3,\quad(2y-15)=75& \\
225=5\times 45\Longrightarrow& (2x-15)=5,\quad(2y-15)=45& \\
225=9\times 25\Longrightarrow& (2x-15)=9,\quad(2y-15)=25& \\
225=15\times 15\Longrightarrow& (2x-15)=15,\quad(2y-15)=15& \Longrightarrow x=15,y=15 \\
225=25\times 9\Longrightarrow& (2x-15)=25,\quad(2y-15)=9& \Longrightarrow x=20,y=12 \\
225=45\times 5\Longrightarrow& (2x-15)=45,\quad(2y-15)=5& \Longrightarrow x=30,y=10 \\
225=75\times 3\Longrightarrow& (2x-15)=75,\quad(2y-15)=3& \Longrightarrow x=45,y=9 \\
225=225\times 1\Longrightarrow& (2x-15)=225,\quad(2y-15)=1& \Longrightarrow x=120,y=8
\end{eqnarray*}

The above equations lead to all 9 distinct positive integer solutions to the problem.  Given $x>y,$ there are 4 distinct positive integer solutions to be considered.
[/quote]
To find the number of factors of $225$, or $5^2 \times 3^2$, you can just increase each exponent by one and multiply the resulting numbers. $3 \times 3 = 9$. That's a little shortcut if you didn't know it already.

Hasn't this problem been posted already, or am I not thinking?


Bob Bluster, the KNEWS meteorologist, determined that the mathematical odds of $ \emph{no rain}$ tomorrow are 11:9. What would a mathematics student determine as the percent chance there $ \emph{will be rain}$ tomorrow?

There will be 11 times no rain for every 9 parts rain, so 9/20=45%


$ 32471517417924$  is supposed to be a perfect square, but one of the digits is written incorrectly. Can you identify which digit is changed and what is the correct number?

may i ask if you can use a calculator on this?
provided you can, you could write a program and the number would be found in a matter of seconds

That's not the point of the problem.  This problem is doable without a calculator.

[hide="The two easiest things to try..."] are evaluating this number $ \bmod 11$ and $ \bmod 9$.  What are the corresponding quadratic residues? [/hide]

There are lots of quadratic residues. If you use the quadratic residues in mod 9 and in mod 11, and use them to create a list of the adjustments you can make on a given digit, you get a fairly length list. And then you have to do that for every digit.

By the way, the answer is to turn the 7th digit from the left from a $ 1$ to a $ 5$.


Greets.

I saw a proble the other day under the title of problem of the Week on the opening page and aI cannot now find the thread. The problem was this: A function f:[0,1] ->R which is increasing satisfies
(i) f(0)=0  (ii) f(x/3)=f(x)/2 (iii) f(1-x)=1-f(x). Find f(18/1991).

Does anyone know where this problem ended up?

already posted    http://www.mathlinks.ro/viewtopic.php?t=146169
 :cool:


induction
combinatorics solved
combinatorics
Recurrence

u(2002) = 1  :D

It's not too difficult to prove by induction that u(n) = 1 if the number of 1 in the binary expansion of n is odd and 0 otherwise.

. Now 2002 = 11111010010 so u(n) = 1

. (2^p-1)^2 = 111...11100...00001 with (p-1) '1' and p '0' so u((2^p-1)^2) = 1 if n odd and 0 if n even.

It is easy to prove un equals (the number of '1' in the binary notation of n) mod 2.

So u_{(2n-1)2}=u_{2n+1(2n-1-1)+1}=u_{11...100...01}= n mod 2.

[quote="orl"]The sequence {u_n} with n being a positive integer is given by the recurrence

(1)  u_{0} = 0
(2)  U_{2n} = u_{n}
(3)  u_{2n+1} = 1 - u_{n}

a.) Determine u_{2002} and
b.) and u_{m} with m = (2^p-1)^2 and p a natural number ![/quote]

See also  Concours Gnral 1990, exercice 1

http://www.mathkang.org/fractal/cgidx.htm


complex analysis
complex analysis unsolved

How can we prove that in the complex plane closure of a set A is the union of the set itself and its boundary? In real case , we can go through by using the definitions of closure, accumulation points and boundary, but i don't know what to do in complex plane.
In general how can we prove things in complex plane, which have common points with the proofs in real plane?

The statement "closure = set + boundary" is true in any topological space.

Let $S$ be the set.
The closure is the set of those points $P$ that contain a point of $S$ in every neighbourhood of $P$.
The boundary is the set of those points $P$ that contain a point of $S$ and a point not from $S$ in any neighbourhood.
By this, the closure contains the set and it's boundary by definition. The rest is to show that not more is contained: If $P$ contains a point of $S$ in any neighbourhood and is not from $S$, then also a point not from $S$, namely $P$ itself, is in every neighbourhood, thus $P$ is in the boundary.

For the general question: for example by generalising what they have in common, here to be a topological space, introduced by the metric.


algebra
polynomial
calculus
integration
derivative
real analysis
real analysis unsolved

How can I check the orthogonality of the Legendre polynomials of odd order for [0,1] so that

the integral from 0 to 1 of P[size=75]n[/size](x)P[size=75]m[/size](x)dx = [(delta)nm]/(2n+1)

If your definition for the Legendre polynomials is based on derivatives, try integrating by parts repeatedly, differentiating the one of smaller degree until it's zero.

One comment: I usually see the Legendre polynomials defined on $ [\minus{}1,1],$ rather than $ [0,1].$ Once you have them, you can rescale them to fit any interval $ [a,b]$ but the rescaling is in there somewhere.


I noticed that after rating a post, when I go back to the post the rating is no longer there. Is there a problem?

I believe there is a limit as to how many posts you can rate at a time (for normal users).

I don't rate many posts though so unless the limit is extremely low (0?) I'm quite sure I haven't hit it.

The rating shows up publicly after at least $ m$ people rate a post where $ m$ is some number strictly greater than $ 1$ whose exact value only Valentin knows. So, when you rate the post alone, it doesn't show as rated to anybody else or even to you when you come back to it later.

Does a singly rated post still affect rating, though?

Yes, it does. And that makes it quite a problem to try to find posts that others rated.


my first-look guess is that B wins iff $n=2^k,k$ odd.

well he does, but the answer is much more than that!

If $N$ is odd $A$ wins. He first writes $1$, an odd number. If he writes an odd number $n$, both $n+1, 2n$ are even, so the number he gets is even and thus can make the +1 move, writing another odd number. Thus $B$ only writes even numbers and never $N$.

Let $N=d_1d_2...d_k$ in binary, and suppose $N$ is even. Let $a_i=d_1d_2...d_{k-i+1}+1$. Partition the set ${1, 2, ..., N}$ into $S_1={N, N-1, ..., a_2}, S_2={a_2-1, ..., a_3}$, and so on. A move $n \rightarrow 2n$ always goes to the following subset. Now it is clear that if a player is the first to write a number in $S_1$, doing it by doubling the previous number, he wins (because he writes the even numbers from then on). If $X$ is the first to write a number in $S_2$, $Y$ will then jump to $S_1$ by a $n \rightarrow 2n$ move and win. So the first to write a number in $S_2$ loses. We have $S_2={d_1....d_{k-1}, ..., d_1...d_{k-2}+1}$. Clearly $d_1...d_{k-2}$ will be written, unless a player commits suicide, because the only way to skip it is to play a $n \rightarrow 2n$ move and that is losing. So for even $N$ the player who writes $d_1...d_{k-2}$ wins.

Then the winner for the $d_1...d_k$ game is $A$ if $d_k=1$, and it is the same as for the $d_1...d_{k-2}$ game if $d_k=0$. If among $d_k, d_{k-2}, d_{k-4}$ and so on there's a $1$, the winner is $A$. If not, and if $k$ is even, the winner is the same as for $d_1d_2$, which is $A$ if $d_2=1$, and $B$ if $d_2=0$, by inspection. If $k$ is odd, the winner is either $A$ or the same as for $d_1d_2d_3$, which is always $A$ by inspection.

We conclude that $B$ wins iff $N$ is the sum of distinct odd powers of 2.

The solution set  is  equal  to  the  set  of all  base  4 numbers  consisting  of  only 2's  and  0's

Proof:
If N is  odd, A wins

It  is easy to  see  that  he  who can always write k, or  forces  his opponent  to  be  the  first to  write a number >k  writes 4k and 4k+2(if  N is  one  of  these). Let  this  mean that this person controls k.   (statement  1)

As  per question, A controls 4,6
Also  A controls  all odd  numbers
B controls 2

statement 1  implies  that  he  who  controls  k  also  controls  4k  and  4k+2

so B controls  numbers  2,8,10,32........
we  will attempt  to construct  the  set  of  all numbers  controlled  by  B

The first element is 2

Working in base  4:
if abc..n(the number in  base 4) belongs  to  the  set , so  does (abc..n0) and  (abc..n2)
so  the  set  can  be  infinitely  extended  by  adding  2 or 0 to the  right

also A controls all numbers not  in this set:
from 3..7  A  gets 12 to 30
from this  he  gets all numbers uptil  122  execpt  those  in  B's winning  set.
because B does not control k ,so  A controls k(as he can force B not  to write k)
so  A  also controls  4k  and  4k+2 (statement 1)

this completes the solution(ans at top of post)

PS:this answer is obviously same  as Severius' solution which can be  seen simply by converting base  4  numbers to sum  form

i think  u  will agree that  this  answer  is  simpler  to  derive  and explain

Rahul Singh

Let $g(N)$ denote the player, who wins the game for the number $N$.

It is easy to see that $g(2k+1)=A$, as player A can win by executing only $n+1$-moves. Then B can only write even numbers and can therefore never write $N$.

Lemma. $g(N)=g\left(\left[\frac{N}{4}\right]\right)$ for $N$ even, where $[x]$ denotes the largest integer not greater than $x$.

Player $g\left(\left[\frac{N}{4}\right]\right)$ wins the game for $N$ in the following way: As long as his opponent does not write a number greater than $\left[\frac{N}{4}\right]$, he plays according to his strategy for $\left[\frac{N}{4}\right]$, so the first player having to write a number $n$ greater than $\left[\frac{N}{4}\right]$ must be his opponent. Then $\frac{N}{4}<n\le \frac{N}{2}$. Then he writes $2n$ with $\frac{N}{2}<2n\le N$. From now on, only $n+1$-moves are allowed, and as $N$ is even, Player $g\left(\left[\frac{N}{4}\right]\right)$ wins.

Given a number $N$, we can now repeatedly apply our lemma. Eventually we will either get $g(N)=g(2k+1)=A$ or $g(N)=g(2)=B$.

Now let $N=\sum_{i=0}^n a_i \cdot 2^i$ with $a_i\in\{0,1\}$. Let $j$ be the smallest index such that $a_{2j}=1$. After applying our lemma $j$ times, we will get $g(N)=g\left(\sum_{i=2j}^n a_i\cdot 2^{i-2j}\right)=g(2k+1)=A$.

If on the other hand $a_{2j}=0\quad\forall j$ and $N=\sum_{i=0}^n a_i \cdot 2^{2i+1}$ we get $g(N)=g(2)=B$ after applying our lemma $n$ times.

Hence, B wins the game iff $N$ can be written as the sum of distinct odd powers of 2, i.e. $N=\sum_{i=0}^n a_i \cdot 2^{2i+1}$.$\square$

In collaboration with [b]mathdebam[/b].

[hide]
Unless otherwise specified, by numbers, we shall mean natural numbers and all variables will denote natural numbers.

Let such a game with upper limit $n$ be called a $n$-game. Let's call all numbers $n$ for which $B$ has a winning strategy in a $n$-game [i]friendly[/i] and all other numbers [i]unfriendly[/i].

[b]Claim 1:[/b] All odd numbers are unfriendly.
[b]Proof:[/b] For $N= 2k+1,$ $A$ starts by choosing an odd number. At the subsequent moves, $B$ can either increment it by 1 or double it, so $B$ shall write an even number. Then, $A$ shall again increment the number making it odd. If $A$ follows this strategy, $B$ is forced to write all even numbers, while $A$ writes the odd numbers, so $A$ must be the one who writes $2k+1.$ $\blacksquare$

[b]Claim 2:[/b] The numbers $4n$ and $4n+2$ are friendly iff so is $n.$
[b]Proof:[/b] Suppose $n$ is friendly. By claim 1, $n$ must be even. Unless one of the chosen numbers exceeds $n,$ $B$ follows his strategy for a $n$-game. Let $j$ be the first number written which is greater than $n.$ Obviously $j<2n.$ Note that it must be $A$ who writes $j,$ since as long as the numbers are less than $n,$ $B$ can use his winning strategy for a $n$ game. After $A$ writes $j,$ $B$ doubles it so $2n +1< 2j <  4n.$ The only moves allowed now are incrementing the numbers by 1 (since $2 \times 2j > 4n+2 > 4n$). Since $(4n-2)j$ and $(4n+2)-2j$ are both even, $B$ wins. Note that we didn't use any special property of $A$ moving first in our proof, so similar arguments show that $4n+2$ and $4n$ are unfriendly iff so is $n.$ $\blacksquare$

Using these claims, an easy induction on the number of digits in binary base shows that $N$ is friendly iff it is even and there are no 1's in the even placed positions in the binary expansion of $n.$ [/hide]

I had a rather interesting incident today with this problem; hence I feel obliged to post my solution (which is essentially the same as that already in the thread) and narrate the incident :P

[quote=IMO ShortList 2004 C5] $A$ and $B$ play a game, given an integer $N$, $A$ writes down $1$ first, then every player sees the last number written and if it is $n$ then in his turn he writes $n+1$ or $2n$, but his number cannot be bigger than $N$. The player who writes $N$ wins. For which values of $N$ does $B$ win?

[i]Proposed by A. Slinko & S. Marshall, New Zealand[/i][/quote]

Answer: $B$ wins if and only if $N$ is a sum of several odd powers of $2$.

Firstly, note that for all odd $N$, $A$ can ensure a win just by adding $1$ all the time since his current number always stays odd whilst $B$'s stays even.

[b]Claim:[/b] For even $N$, a player has a winning strategy if and only if they have one for $n=\left \lfloor \frac{N}{4} \right \rfloor$.

(Proof) The key idea is that the player who lands up on an even number $k$ with $2k>N$ wins the game, since thereafter all moves made are simply addition by one.

Suppose the other player has a winning strategy for $n$, then they reach $n$ unless the protagonist reaches an even number in $(n, 2n)$; in which case they double the current number to win. Otherwise, regardless of what the protagonist does they simply double at the next turn and win thereafter by the initial observation. $\blacksquare$

From the previous analysis, and the fact that $B$ wins for $N=2$ we see that she wins only for the prescribed set of values of $N$. $\blacksquare$

[hide=The incident] I believed after case bashing till $N=7$ and neglecting $N=2$ as a trivial case, that $A$ always wins. Then I proceeded to give an inductive proof for the validity of that assertion; it turned out that the logic was exactly the same as in the correct solution. However, when I tried $N=8$, just for fun, the argument fell apart. It then occurred that $N=2$ is an issue when $n=2$ so actually there's a whole family of numbers for which $B$ can win.

Had I known the actual answer, I may not have been able to come up with an argument, so not knowing the answer helped solve this problem.

Disclaimer: Don't repeat such incidents frequently :P [/hide]

[b]ANSWER:[/b] $B$ wins if and only if $N$ can be expressed as the sum of distinct odd powers of $2$.

[b]SOLUTION:[/b] Call a natural number $N$ [i]good[/i] if $B$ wins, and [i]bad[/i] otherwise. Call this trait of a number to be [i]good[/i] or [i]bad[/i] as its [i]character[/i]. We make a series of claims before the final result.

[size=150]Claim 1[/size] If $N$ is an odd integer, then it is [i]bad[/i].

[b]PROOF:[/b] Suppose that at some point of time during the game, when $N$ is an odd integer, $B$ writes down the integer $n$. Then we claim that $A$ can win by writing $n+1$ at all such times. To see that this is true, just notice that, whenever $A$ writes an odd integer, $B$ writes an even integer on the board in the next move. But, as $A$ starts from an odd integer only, we get that $B$ must always write an even integer, and so $B$ can never terminate on an odd integer. Thus, we get that all odd integers are [i]bad[/i]. $\Box$

[size=150]Claim 2[/size] $N$ and $4^kN$ have the same [i]character[/i] $\forall k \in \mathbb{N}$.

[b]PROOF:[/b] We proceed by induction. Suppose that $N$ is [i]bad[/i]. We'll show that $4N$ is also [i]bad[/i], i.e. $A$ can always reach $4N$. To show this, we'll play God in the game :P. Initially, we'll make $A$ play with the same strategy that he/she would have used to reach $N$, till $B$ doesn't write a number greater than $N$. But, as soon as $B$ writes a number of the form $N+C$, where $1 \leq C \leq N-2$, $A$ will write the number $2(N+C)$ on the board in his next move. As $2(2N+2C)>4N$, $B$ will be forced to write the number $(2N+2C+1)$, then $A$ will be forced to write the number $(2N+2C+2)$, and so on. This shows that $A$ will be the one to reach $4N=2N+2N$, and so $4N$ is [i]bad[/i]. By a similar argument, one can show that if $N$ is [i]good[/i], then so is $4N$.

Let's turn towards the inductive hypothesis, i.e. we suppose that our claim is true for some $k \in \mathbb{N}$. Then by the above argument, we get that $4^{k+1}N$ has the same [i]character[/i] as $4^kN$, which in turn has the same [i]character[/i] as $N$ (by the inductive hypothesis). Thus, we are done with the induction, and so our claim is proved. $\Box$

[size=150]Claim 3[/size] $N$ and $4N+2$ have the same [i]character[/i].

[b]PROOF:[/b] This easily follows by a similar argument as done while proving the base case in Claim 2. $\Box$

[b]CONCLUSION:[/b] Note that $N=2$ is [i]good[/i]. By Claim 2, we get that $N=2 \cdot 4^k=2^{2k+1}$ is also [i]good[/i], where $k \in \mathbb{N}$, i.e. all odd powers of $2$ are [i]good[/i]. But, by Claim 3, this gives that $2^{2k+1}+2$ is also [i]good[/i]. Again, By Claim 2, $2^{2k+2l+1}+2^{2l+1}$ is also [i]good[/i], where $l \in \mathbb{N}$. Continuing in a similar fashion, we get that the sum of distinct odd powers of $2$ is good. All we need to show now is that no other value of $N$ works. To see this, assume to the contrary (duh!) that some other value of $N$ is also [i]good[/i]. Name this value as $M$. By Claim 1, $M$ must be even, i.e. $M=4m_1$ or $M=4m_1+2$. But then, by Claim 2 and Claim 3, we get that $m_1$ is also [i]good[/i]. Again, we must have $m_1=4m_2$ or $m_1=4m_2+2$, and once again, $m_2$ must also be [i]good[/i]. As $M$ can not be expressed as the sum of distinct odd powers of $2$, it's easy to see that $m_1$ also can not be expressed as the sum of distinct odd powers of $2$. Continuing in a similar fashion, we get a decreasing sequence of even positive integers, which can never reach an odd power of $2$, and more importantly which can never reach $2$. But, by the method of infinite descent, we know that this is never possible for finite $M$. Thus, no such $M$ exists. $\blacksquare$

EDIT: $333^{rd}$ post on AOPS, and that too a combi. I call that an achievement :P

I claim that $B$ will win iff $N$ is the sum of distinct odd powers of 2. First, note that if $N$ is odd, $A$ can always force $B$ to pick an even number. Hence, $A$ has the winning strategy. Next, if $N=4k+2$, the first person to pick a number, $i$, between $k+1$ and $2k+1$ will lose, since the next person can choose $2i$. No further doubling can occur, since the number is larger than $N/2$, so every move afterward will be a +1, resulting in the person who picked $i$ to lose. If the previous person, say $A$, picked $i<k+1$, then the largest number $B$ can write is $2i<2k+1$. So, as there is no way to "skip" this interval, the optimal strategy will be to reach $k$. Hence, the person who has a winning strategy for $k$ also has a winning strategy for $4k+2$.

The same logic can be applied to show that if a person has a winning strategy for $k$ iff he has a winning strategy for $4k$. Now, we use strong induction on $N$ to show that $B$ will only win in the claimed case. Of course, this is true for $N\le 2$. Now, suppose the claim is proven for all numbers smaller than $N$. If $N\equiv 1\pmod 2$, we have already stipulated that $A$ will win. This follows our claim, since $1$ is an even power of 2. If $N\equiv 0\pmod 4$, $B$ will win iff $B$ wins $N/4$. Multiplying by $4$ increases all the exponents by $2$, so their parities and distinctness are preserved, as desired. Finally, if $N\equiv 2\pmod 4$, $B$ wins iff $B$ wins $(N-2)/4=k$. Similar to before, $4k+2$ is a sum of odd powers of 2 iff $k$ was. Hence, our induction is complete.

Solution from [i]Twitch Solves ISL[/i]:

Call this game the $N$-game (as we will induct on $N$). The answer is that Bob wins the $N$-game are exactly those that, when expressed in binary, have no $1$'s in the $2^0$, $2^2$, $2^4$, \dots positions.
[b]Setup.[/b] Define the [i]$N$-table[/i] as follows. It has $N$ entries indexed by $\{1, \dots, N\}$. [list] 	[*]The $n$th entry is [b]losing[/b] if and only if a player who 	sees this number on their turn wins; otherwise, it is [b]winning[/b]. 	Hence by definition the last entry is always $L$ 	(because a player who is faced with $N$ has just lost!). 	[*]Equivalently, here is a recursive description. 	We say $N$ is losing. 	Then, a given $n$ is winning if either $n+1$ or $2n$ is losing 	(ignoring $2n$ if $n > N/2$); else, it is winning. 	[*]Bob wins the $N$-game if and only if $1$ is $W$. [/list] The tables are shown below for $N=12$, respectively. \[ 	\begin{array}{cccccccccccccc} 		1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 		L & W & L & W & W & W & W & L & W & L & W & L \\ \hline 		1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 		L & W & L & W & L & W & L & W & L & W & L & W & L \\ \hline 		1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 		L & W & L & W & W & W & W & L & W & L & W & L & W & L 	\end{array} \]
[b]Proof.[/b] We start with the following claim.
[b][color=red]Claim:[/color][/b]  	If $N$ is odd, then Alice wins the $N$-game.
[i]Proof.[/i]  	Alice can force Bob to stay on odd numbers. $\blacksquare$
We now address the case where $N$ is even.
[b][color=red]Claim:[/color][/b]  	Suppose $N \equiv 2 \pmod 4$ and $N > 2$. 	Then Bob wins the $N$-game 	if and only if he wins the $(N-2)$-game.
[i]Proof.[/i]  	In the $N$-table, we have $N$ is losing, 	$N-1$ is winning, $N-2$ is losing, and so on; 	until $N/2+1$ is losing. 	Thus $N/2$ is winning. 	 	Now note that we may delete $N$ and $N-1$ (the last two columns) 	from the table without affecting any other entries; 	indeed $N/2$ was winning anyways as $N/2+1$ is losing. 	Thus the $N$-table is 	the $(N-2)$-table with two extra columns at the end. $\blacksquare$

[b][color=red]Claim:[/color][/b]  	Suppose $N \equiv 0 \pmod 4$ and $N > 4$. 	Then Bob wins the $N$-game 	if and only if he wins the $N/4$-game.
[i]Proof.[/i]  	In the $N$-table, we have $N$ is losing, 	$N-1$ is winning, $N-2$ is losing, and so on; 	until $N/2+1$ is winning. 	Now from this it follows $N/2$, $N/2-1$, \dots, $N/4+1$ 	are all winning.
Since this entire range of numbers is winning 	and thus don't affect any later numbers, 	we wind up finding the first $N/4$ numbers 	are just a copy of the $(N/4)$-table. $\blacksquare$
These three claims imply the answer directly by induction.

Long and repetitive, but the idea is simple.

For positive integers $N_1,N_2,$ write $N_1\sim N_2$ if the player with a winning strategy when $N=N_1$ also has a winning strategy when $N=N_2.$\\\\ Say a number $n$ is $\emph{sharp}$ if $2n>N.$ Note that if a player plays a sharp number, then all later turns must increase the number by exactly one. As a result, if a player writes a sharp number with the same parity as $N,$ then they win, and if a player writes a sharp number with opposite parity as $N,$ then they lose. \\\\$\textbf{Claim: }$ If $N\equiv 0\pmod{4},$ then $N\sim\frac{N}{4}.$\\\\ $\emph{Proof: }$ Suppose a player writes $\frac{N}{4}$ on turn $t.$ \begin{itemize}\item If $\frac{N}{4}+1$ is written on turn $t+1,$ then the player can write $\frac{N}{2}+2$ on turn $t+2$\item If $\frac{N}{2}$ is written on turn $t+1,$ then the player can write $N$ on turn $t+2$\end{itemize} In either case, the player who writes $\frac{N}{4}$ wins, so it suffices to show there must always be such a player.\\\\ Assume no player writes $\frac{N}{4}.$ Then, some player must have written some even number in the interval $[\frac{N}{4}+1,\frac{N}{2}-2].$ But then the next player can double to reach a sharp even number and thus win, contradiction. $\blacksquare$\\\\ $\textbf{Claim: }$ If $N\equiv 1\pmod{4},$ then $N\sim\frac{N+1}{2}.$\\\\ $\emph{Proof: }$ Since $\frac{N+1}{2}$ is a sharp odd number, it suffices to show that $\frac{N+1}{2}$ will always be written.\\\\ Suppose no player writes $\frac{N+1}{2}.$ Then, some player must write an even number in the interval $[\frac{N+3}{2},N-1].$ But each number in this interval is sharp, so the player will lose, contradiction. $\blacksquare$\\\\ $\textbf{Claim: }$ If $N\equiv 3\pmod{4},$ then $N\sim\frac{N-1}{2}$\\\\ $\emph{Proof: }$ If a player writes $\frac{N-1}{2},$ then the other player must write a sharp even number on the next turn, so they will lose. Hence, it suffices to show that $\frac{N-1}{2}$ will always be written.\\\\ Assume no player writes $\frac{N-1}{2}.$ Then, some player must write an even number in the interval $[\frac{N+1}{2},N-3].$ But every number in this interval is sharp, so the player will lose, contradiction. $\blacksquare$\\\\ $\textbf{Claim: }$ If $N\equiv 2\pmod{4},$ then $N\sim\frac{N-2}{4}$\\\\ $\emph{Proof: }$ Suppose a player writes $\frac{N-2}{4}$ on turn $t.$ \begin{itemize}\item If $\frac{N+2}{4}$ is written on turn $t+1,$ then the player can write $\frac{N+2}{2}$ on turn $t+2$\item If $\frac{N-2}{2}$ is written on turn $t+1,$ then the player can write $N-2$ on turn $t+2$\end{itemize} In either case, the player can write a sharp even number and thus win, so it suffices to show there must always be such a player.\\\\ Assume no player writes $\frac{N-2}{4}.$ Then, some player must write an even number in the interval $[\frac{N+2}{4},\frac{N-2}{2}].$ But then, the next player can double to reach a sharp even number and hence win, contradiction. $\blacksquare$\\\\ These claims are enough to imply that the answer is all $N$ with no ones in even positions when expressed in binary.

Nice Problem! :o
[b]Solution.[/b] Define two sets, [i]good[/i] and [i]bad[/i] respectively as $$G := \left\{\left\lceil \frac{N-1}{2} \right\rceil +1, \ldots, N \right\}~\text{and}~V:=\left\{\left\lceil \frac{\left\lceil \frac{N-1}{2} \right\rceil}{2} \right\rceil, \ldots, \left\lceil \frac{N-1}{2} \right\rceil \right\}$$We will abbreviate them as $G$ and $V$ respectively as shown above. Interpret the chosen numbers lying on the number line extended till $N$. Note that the biggest element of $V$ is consecutive to that of least element of $G$. It's worth noticing that one player must pick a number from $V,$ in particular both players cannot "skip" $V$. Now we have the following claim.
[color=#f00][b]Claim.[/b][/color] If $N$ is even and if any player $P \in \{A,B\}$ lands up in $V$ before other player does does, then $P$ will lose eventually.
[i]Proof.[/i] Note that if $A$ lands up in $V$ before $B$ does, then $B$ must make the next move. But observe that $2V \subset G$. So $B$ can either "jump" from $V \to G$ or stays in $V$. If $B$ jumps then it will land on some $2k \in G$ but since $N$ is even, and $2g > N$ for every $g \in G,$ therefore $A,B$ must make the $+1$ move, then the parity of numbers chosen by $A$ is always odd, which leads $B$ to win. Since both players plays optimally. If one player jumps to $V$ then other player jumps to $G$ and wins eventually, which is what we desired. $\square$

Consequently, neither $A$ nor $B$ would want to land up in $V$ before other player does $~(\clubsuit)$. If one does, then he will lose. This is at central of the rest of the solution.
Call a number $N, P$ [i]true[/i] if player $P$ could always win that number, where $P \in \{A,B\}$.

Now since $A$ started with $1$ then $B$ must pick $2$. Now we deal with the cases when $N$ is odd or even seperately.
[list]
[*]If $N$ is odd, we present the follwing winning strategy for $A$. If at any time $A$ faces $2k$ chosen by $B$. Then simply pick $2k+1$. Now $B$ can either pick $2k+2$ or $2(2k+1)$ which are both even, we conclude that parity of the numbers chosen by $B$ remains the same as even since $B$ started with $2$. But since $N$ is odd, $B$ cannot pick $N$. We conclude $A$ wins the game. $\square$
[*] If $N$ is even, we claim that if $x$ is $P$ true implies $4x+2$ is $P$ true. Let $N=4k+2$ then the good and bad sets are $$G=\{2k+2, \ldots, 4k+2\}~\text{and}~V=\{k+1, \ldots, 2k+1\}$$Consider the set $\mathcal{K}=\{1,\ldots, k\}$. By $(\clubsuit)$ we have, [i]no[/i] player will jump from $\mathcal{K'}=\{\lceil \tfrac{k}{2}\rceil+1, \ldots, k\}$ to $V$. But this is same as if we are playing game on $\mathcal{K}$ set. Now if a player $P\in \{A,B\}$ manages to reach $k,$ which is same as saying $k$ is $P$ true, then the other player must pick number from set $V$ which will lead other player (not the $P$ player) to lose. Therefore, $4k+2$ is $P$ true as desired. $\square$
Similar setting yields $4x$ is $P$ true if $x$ is $P$ true.

 Also it's easy to verify that $1,3,4,5,6,7,9$ are $A$ true numbers and $2,8$ are $B$ true numbers. Define $$\mathcal{A}=\{x \mid x\in \mathcal{A} \implies 4x+2,4x \in \mathcal{A}, ~\text{given}~1,3,4,5,6,7,9 \in \mathcal{A} \}~\text{and}~\mathcal{B}=\{x \mid x \in \mathcal{B} \implies 4x+2,4x \in \mathcal{B},~\text{given}~2,8 \in \mathcal{B}\}$$We claim that $\mathcal{A}\cup\mathcal{B}\equiv 2\mathbb{Z}$ and $\mathcal{A} \cap \mathcal{B} \equiv \emptyset$. Assume at some moment, $\{1,2,\ldots, 4k\}$ are occupied by either $A$ or $B$. Then $k$ is $P$ true for some $P$ implying $4k+2$ is also $P$ true, and thus occupied. If at some moment $\{1,2,\ldots,4k+2\}$ is occupied, then $k+1$ is $P$ true, implying $4k+4$ is $P$ true for some player $P$. We conclude by induction that $\mathcal{A} \cup \mathcal{B} \equiv 2\mathbb{Z}$. Now assume if possible $4m+2=4n+2$ where $4m+2\in \mathcal{A}$ and $4n+2\in \mathcal{B},$ now this implies $m=n,$ and so on, implying that one of $a \in \{1,3,4,5,6,7,9\}$ is same as one of $b \in \{2,8\},$ which is a contradiction, we conclude that $\mathcal{A} \cap \mathcal{B}\equiv\emptyset$. Now $\mathcal{A},\mathcal{B}$ consists of numbers for which $A,B$ have a winning strategy. To characterize $\mathcal{B}$ we claim that $\mathcal{B}$ is nothing but the sum of [b]distinct odd powers[/b] of $2$. We see that, working backwards from any such sum boils down to the given $\{2,8\}\subset \mathcal{B}$. Also combing terms with each other yields sum of distinct odd powers of $2$ as desired.
[/list]
This finishes the problem. $\blacksquare$
[hide=Remarks]I wonder if there exist any generalization, sort of like replacing the $2n$ and $n+1$ condition. :P[/hide]

Let a number be weird if it can be written as the sum of distinct odd powers of 2. We claim that $B$ wins if and only if $N$ is weird.

[b]Claim 1:[/b]If $N\geq 4$ is even, and a player can guarantee getting $\lfloor \frac{N}{4} \rfloor$, then they can also guarantee getting $N$.
[b]Proof: [/b] Let's say $P_1$ gets $\lfloor \frac{N}{4} \rfloor$.
If $P_2$ doubles, then $P_1$ doubles too and gets $4\cdot \lfloor \frac{N}{4} \rfloor$. At which point if this is not equal to $N$, $P_2,P_1$ will exchange a round of $+1$s and $P_1$ will win.
If $P_2$ adds one, then $P_1$ doubles to $2\cdot \lfloor \frac{N}{4} \rfloor+2$. At this point, $2(2\cdot \lfloor\frac{N}{4}\rfloor+2)> N$. Thus, the only course of action is for both players to add one repeatedly, but since $P_1$ will always be the one writing down evens, $P_1$ wins. $\square$.

[b]Claim 2: [/b]If $N$ is odd, then $A$ wins
[b]Proof: [/b] If $A$ repeatedly does the add one operation, then $B$ will always receive an odd number which he will have to turn into an even which will never be equal to $N$.$\square$.

To finish, note that all odd $N$ aren't weird and $A$ wins. If $N$ is weird, then $\lfloor \frac{N}{4}\rfloor$ is weird too, so $B$ wins $N$. If $N$ isn't weird, then $\lfloor\frac{N}{4}\rfloor$ isn't weird, so $A$ wins. The base cases are easy to show (Alice wins $1,3$ and $B$ wins $2$), and so we are done with this strong induction. $\blacksquare$.

There are a lot of this i want to tell while i solved this problem lol.
So when i saw this problem, i really wanted to solve it, hence i remembered something that my teacher told about this kind of problems, i should play the game first. And here is when [b]Rama1728[/b] comes!, so i told him "wanna play a game?" ,and then he said "what game?" ,then i had to explain the rules of this thing lol and after a lot of talking i decided to start (Rama was player A and i was player B), we started with the number $N=69$ in which Rama won (later i realiced why this happens which is my first claim). Then we did the game with $N=32$ in which i lost becuase i'm dumb lol (now knowing how to always win at that number). Then when trying with $N=8$ i always won and then tried some other numbers. Later we realiced that if $N$ was odd then Rama would always win and no much time later they disconnected (rip).
From here progress is mine and this is how i solved a [b]C5[/b] (a victory for me becuase i suck at combo lol)
[b][color=#f00]Claim 1:[/color][/b] If $N$ is odd then $A$ wins always.
[b][color=#f00]Proof:[/color][/b] The winning strategy for $A$ is just always writting an odd number which is posible as after $A$ puts $1$, $B$ nesesarily puts $2$ and here is when this strategy comes, so every time $A$ writtes an odd number $k$ then $B$ writes $k+1$ or $2k$ but both are even, and after doing that $A$ just needs to add $1$ to any of these options to write an odd number so $A$ will always win becuase $B$ will never write an odd number and $N$ is an odd number.

Hence from here we will be working with $N$ even as we want $B$ to win.
[b][color=#f00]Claim 2:[/color][/b] If $B$ can win for $\left \lfloor \frac{N}{4} \right \rfloor$ then he can win for $N$
[b][color=#f00]Proof:[/color][/b] Realice that $A$ is smart enough to realice that if he puts a number $k$ between the range $\left \lfloor \frac{N}{4} \right \rfloor < k \le \frac{N}{2}$ then $B$ wins becuase $B$ puts $2k$ and then clearly this becomes an adding $1$ game in which $B$ will always win becuase $N$ is even. So $A$ will do all the possible to let $B$ write such $k$, but remember that $B$ has an strategy to reach $\left \lfloor \frac{N}{4} \right \rfloor$ meaning that this thing is even. Now if $A$ puts a number less than $\frac{\left \lfloor \frac{N}{4} \right \rfloor}{2}$ then $B$ can multiply it by $2$ and then $A$ will try to use the adding $1$ game in which they will obviously fail as $B$ can always write even numbers. And if $A$ somehow writes a number greater than $\frac{\left \lfloor \frac{N}{4} \right \rfloor}{2}$ then $B$ does the adding $1$ game, which destroys $A$ strategy as if he multiplies by $2$ then its self-kill and if $A$ follows the adding $1$ game then $B$ always reaches $\left \lfloor \frac{N}{4} \right \rfloor$ becuase its even.
[b][color=#f00]Finishing the problem:[/color][/b] So lets use [b]Claim 1[/b] and [b]Claim 2[/b].
Very easy to verify that [b]Claim 2[/b] is the only way to win for $B$ when $N$ is even. Also note that if for a even number $N$ it holds that $\left \lfloor \frac{N}{4} \right \rfloor$ is even then $N=8a, 8a+2$ for some positive integer $a$. And now here is where the cycle begins..., basicaly we need to find more about $a$ which holds that $\left \lfloor \frac{a}{2} \right \rfloor$ is even. And now here is the funniest part. For any posititve integer $m$ that satisfies that $\left \lfloor \frac{m}{2} \right \rfloor$ is even then its very easy to see that $m=4m_1, 4m_1+1$ and since from $a$ and the future definitions of $a$ holds the same thing we have a cycle where $N$ ends by being expressed in this way:
$$N=\sum_{j=0}^{k} a_j \cdot 2^{2j+1} \; \text{where} \; a_n \in [0,1] \; \text{for every non-negative integer} \; n$$
And from this we got our answer to the problem.
[b]Answer:[/b] $B$ wins if $N$ is the sum of odd powers of $2$.
Thus we are done  :blush:

Claim: A wins for all odds.

Proof: every turn, A can write down an odd by playing +1, where anything from B writes down an even.

Claim: the player who wins n also wins 4n, 4n+2.

Proof: assume WLOG it's A. Then, suppose that A reaches n; then, regardless if B writes down n+1 or 2n, A can win with x2.

Now, if B plays some n<k<2n, then A can also won by writting down an even 2n+1<2k<4n.

Now, combining the above 2 claims alongside the fact that B wins 2, it's obvious that B wins iff n's binary representation has 0's in every even position, counting from the right.

This took an embarrassingly long time.

The answer is $\boxed{N = \text{the sum of distinct odd powers of }2}$.  First, notice that Bob cannot win any odd $N$, since Alice can keep adding $1$ to Bob's answer and Bob must keep writing even numbers.  The key claim is the following:
[color=#42bee7][b]Claim: [/b][/color]Bob wins $N$ iff he wins $\left\lfloor\frac N4\right\rfloor$.
[color=#42bee7][b]Proof: [/b][/color]If any player ever plays a number in the range $\left(\frac N2, N\right]$ with the same parity as $N$, they win, since the remaining moves must all be $+1$s, and the original player will play all of the remaining $N$-parity numbers until they reach $N$ ($\spadesuit$).

Assume FTSOC Bob does not win $N$ but wins $\left\lfloor\frac N4\right\rfloor$, which must be even.  Then Alice must play a number in $\left(\left\lfloor\frac N4\right\rfloor, \frac N2\right]$, and Bob can then double and win by $\spadesuit$, a contradiction.

Now FTSOC assume Bob wins some even $N$ but Bob does not win $\left\lfloor\frac N4\right\rfloor$.  Then Alice wins $\left\lfloor\frac N4\right\rfloor$.  Bob must play a number in $\left(\left\lfloor\frac N4\right\rfloor, \frac N2\right]$, and then Alice may double and win by $\spadesuit$.  This is a contradiction, and therefore the original assumption must be false, and the claim is proved.

Obviously Bob wins $N = 2$, and through some trivial induction, we arrive at the answer and finish.

We claim that $B$ can win if and only if $N$ can be presented as a sum of distinct odd powers of $2$. Obviously, the only case when $B$ wins for $N<4$ is $N=2,$ so two following claims are sufficient.

[b]Claim 1.[/b] For every odd $N$ player $A$ can force a win.
[i]Proof.[/i] The strategy for $A$ is to increase last written number by $1$ on each move. Thus $B$ always writes an even number, and since the game is clearly finite, $A$ wins $\Box$

[b]Claim 2.[/b] For even $N=n\geq 4$ player has a winning strategy iff he has it for $N=\left\lfloor \frac n4\right \rfloor .$
[i]Proof.[/i] Note that the only if part follows from the if part by indirect argument.
Assume the player $X$ has a winning strategy for $n=\left \lfloor \frac n4\right \rfloor ;$ thus in case $N=n$ this player can force his opponent to write the first-ever number from interval $\left( \left \lfloor \frac n4\right \rfloor  ;\frac n2\right]$. After that let player double the number, and so he writes the even number from interval $\left( \frac n2;n\right]$. Henceforth both players must increase number by $1$ on each move, so by parity argument $X$ must win $\Box$

If $N$ is odd, then if $A$ only does $+1$ moves, then the parity must change after each of $A$'s and $B$'s moves, so $B$ always plays on an even number and thus cannot win.

If $N$ is even, then let $N_1=\lfloor \tfrac{N}{2}\rfloor$, $N_2=\lfloor \tfrac{N}{4}\rfloor$, and $N_3=\lfloor \tfrac{N}{8}\rfloor$. If a player writes a number in $(N_2,N_1]$ then the opponent can double it for a value in $(N_1,N]$. Thus, from there the only available move is $+1$, so the one who writes a number with the same parity as $N$ wins. That player is the opponent, since they just doubled it.

If a player reaches $N_2$, then the opponent has no choice but write a number in $(N_2,N_1]$ no matter what they do, so they win. If the number is in $(N_3,N_2]$ then doubling it will make them lose, so the only logical move is $+1$. Thus, the person who wins is the same as the person who wins $N_2$.

Write $N$ in base $4$. $A$ wins if and only if some digit is odd.

First C5 ever, maybe this is a lot easier than a C5.

 We claim that Bob wins if and only if $N$ when written in the form
$$a_02^0 + a_12^1 + a_22^2 + \dots$$
for $a_i\in \{0,1\}$ does not have $a_i=0$ for all even indices $i$. First we exclude odd $N$.\\
Notice that if Alice always adds 1 to the last written number, Bob can only write down even numbers (Alice starts with 1 and Bob 2). This means he cannot ever write $N$ which allows Alice to win.\\
Now, we deal with even $N$, via induction. It is easy to see that Bob wins $N=2$ and Alice wins $N=4$ since Bob must play 2 on his first turn. $N=6$ too can be won by Alice by doing the following moves $$1 \longrightarrow 2 \longrightarrow 4 \longrightarrow 5 \longrightarrow$$
(Here Bob has no choices at all).\\
Now, say we know which $N$ Bob can win for $N \leq 2^{2k+1}$ for some $k \geq 1$.
Let a number $a$ be called [i]winning[/i] if a player who gets his turn with the last number $a$ written can win. Else, let it be called[i] loosing[/i] (here the player is forced to lose).\\
Now, let $N=4k$ for some $k\geq 2$. Then, clearly $4k-1$ is winning. This in turn means that $4k-2$ is losing (since it is too large to do the $2n$ move), likewise all odd are winning and all even losing upto $2k+1$, and then $2k$ becomes winning since that player can simply do the $2n$ move. Then, all numbers $2k-1,2k-2,\cdots,k+2$ are winning since that player simply can do the $2n$ move and force the next player to a losing position. Now, $k+1$ is also winning due to the same reason but $k$ is losing since both options $k+1$ and $2k$ are in fact winning. Then, note that $k-1$ is winning and so on. Here, $k-2,k-4 \cdots, \lfloor{\frac{k}{2}}\rfloor$ will be losing since even though it is possible to do the $2n$ move all the positions obtained through them are winning positions. So, since $k$ is also losing, it can be seen that from $k-1$ onwards to the right, the winning and losing positions are exactly the same as in the $N=k$ case. To summarize,
    \begin{tabular}{c|c c c c c c c c c c c}
         W& $4k-1$ & $4k-3$ & $\cdots$ & $2k+3$ & $2k+1$ & $2k$ &$\cdots$ & $k+2$ & $k+1$ & $k-1$ & $\cdots$ \\
         \hline
         L & $4k-2$ & $4k-4$ & $\cdots$ & $2k+2$ & & & &  $\cdots$ & $k$ &  & $\cdots$
    \end{tabular}

Thus, if $k$ is winning it has to be a sum of odd powers of two (when written as a sum of distinct powers of 2) and thus so must be $N=4k$ (since multiplying by four adds 2 to each index which preserves their parity). Now, to deal with $N=4k+2$, here too we can map the above table keeping track of when it is possible to force the next player into a losing position to obtain,

    \begin{tabular}{c|c c c c c c c c c c c}
         W& $4k+1$ & $4k-1$ & $\cdots$ & $2k+3$ & $2k+1$ & $2k$ &$\cdots$ & $k+2$ & $k+1$ & $k-1$ & $\cdots$ \\
         \hline
         L & $4k$ & $4k-2$ & $\cdots$ & $2k+2$ & & & &  $\cdots$ & $k$ &  & $\cdots$
    \end{tabular}

Thus, it is only possible for Bob to win $N=4k+2$ if he can win $N=k$. Bob can win $k$ only if it can be written as a sum of odd powers to 2 by our induction hypothesis, and thus he can win $N=4k+2$ only if it can be written as a sum of odd powers of 2 (multiplying by 4 does not change the parity of the index of larger powers and $+2$ adds a power of $2^1$ to the end which is also an odd power). And, the induction is complete.\\
Thus, it is clear that by the Principle of Mathematical Induction, Bob can win if and only if $N$ can be written as a sum of odd powers of 2 (in the above mentioned form).

We claim that N=sum of distinct odd powers of 2 work. Obviously odd N A wins (A keeps on adding 1), and B wins 2. Then, suppose WLOG player A would normally win N; we claim that A would also win 4N and 4N+2. Indeed, note that if A wins by getting B to get to N/2, then A goes to N, and no matter if B doubles or adds 1, A doubles, and A will henceforth win both of those due to the condition. If A wins by getting B to get to k>N/2 with opposite parity than N, if B adds 1 keep adding 1 as A up to N (if A finishes at N, then the problem is evident again); eventually when B doubles to a number N<i<2N, A can double to 2N<j<4N being even, and since B can't do anything but add 1, A will finish at the same parity even. We're now ``home-free": Since B wins 2, our original claimed answer is evident. $\blacksquare$

[b]Remark.[/b]Note that the claim is ``sharp", because worst case is when A only wins 4n and 4n+2, which is also when B doubles from N and A doubles, so you couldn't claim a 4n-2 win guarantee, which serves as a sanity check that this is probably the strongest answer we can get.

also extremely misplaced for C5; I've seen the one about N coins, you can reduce by at most half of the coins, last person to take coins loses; this is similar, so ``A problem changes from challenging to trivial if a similar one was solved in training."

$B$ can win (assuming that they move after $A$ writes down $1$) if and only if, when $N$ is written in binary, all of its even-indexed digits (units digit, $4$'s digit, etc.) are $0$.

First suppose that $N$ is odd. Then player $A$ always adds one to their number. It's easy to prove by induction that $B$ always writes down an even number, and $A$ always writes down an odd number, so $A$ clearly ends up winning.

Now suppose that $N$ is even. Then any even number in $(N/2,N]$ is losing (i.e. the player that receives an even number in this range at the start of their turn loses), since both sides can only add $1$. Thus any number in $(N/4,N/2]$ is winning, since the player can just multiply by $2$ to give the other player an even number in $(N/2,N]$.

I now claim that the game for $N$ is equivalent to the game for $\lfloor N/4 \rfloor$. Observe that in general we can restate the game as having no restrictions on the size of the number written, but having whatever player first writes a number more than $N$ lose. Then, the player who exceeds $\lfloor N/4\rfloor$ first (in a game for $N$) gives their opponent a number in $(N/4, N/2]$, which is winning for the opponent, so the two players will essentially play a game for $\lfloor N/4\rfloor$ that has the same outcome as the game for $N$.

It is then straightforward to extract the advertised solution set from the fact that $N$ odd are losing and $N$ even are winning iff $\lfloor N/4\rfloor$ is. $\blacksquare$

We claim that $N$ wins iff $N$ can be written as the sum of distinct powers of $2$, all of which have odd exponent.

Let $N$ be winning if $B$ wins for a given $N$. Notice that if someone places a number greater than $\frac N2$, they win iff the parity of that number is the same as the parity of $N$ as the moves after that placement must be $+1$.

Claim: If $N=4k + 1$ or $N = 4k + 3$ for some positive integer $k$, then $N$ wins iff $2k + 1$ wins.
Proof: Notice that if someone skips past $2k+1$ (as in they make the number go from under $2k + 1$ to over $2k + 1$), then they reach an even number greater than $\frac N2$, so they lose. Hence we can assume no player makes a move to skip past $2k+ 1$ as that would be their least optimal move. If someone hits $2k + 1$, then they win as the other person is forced to make the number even. Now, the game is played so that the number can't exceed $2k + 1$ and whoever hits $2k + 1$ wins, hence $N$ wins iff $2k + 1$ wins. $\square$

Now to see that all odds lose, we can induct this with base case $1, 3$ obvious. Notice that for each odd number $N$, (using the claim) that $N$ loses if something less than $N$ loses. But everything less than $N$ loses by the inductive hypothesis, so $N$ must also lose.

Claim: If $N$ is even, then $N$ wins iff $ \left \lfloor  \frac N4 \right \rfloor $ wins.
Proof: Let $ \left \lfloor  \frac N4 \right \rfloor=k$. Notice that if a player places some number, say $m$, in the interval $(k,2k]$, then notice that they lose as the other person can play $2m$, which is even and over $\frac N2$. Hence if someone skips past $k$, since they can't hit anything over $2k$, they lose. Therefore, we can assume no one skips past $k$, as it would be their less optimal move. If someone actually hits $k$, they win as the other person must place in $(k,2k]$. Hence the game is now played so that the number can't exceed $k$ and whoever hits $k$ wins, so $N$ wins iff $k$ wins. $\square$

Using the facts that $2$ wins but $1, 3, 4$ lose, the conditions ($N$ odds losing and $N$ even winning iff $ \left \lfloor \frac N4  \right \rfloor$ wins) uniquely determine which $N$ win. It suffices to prove that the conditions given by the claims hold with our claimed solution in the beginning. The condition of all odds losing clearly holds true. Now, we need to show that if $N \in \{4k, 4k + 2\}$ that $N$ wins iff $k$ wins. Let $k = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_t}$ for some $t$ and distinct positive integers $a_1, a_2, \ldots, a_t$. Note that $4k = 2^{a_1 + 2} + 2^{a_2 + 2} + \cdots + 2^{a_t + 2}$ and $4k + 2 = 2^{a_1 + 2} + 2^{a_2 + 2} + \cdots + 2^{a_t + 2} + 2^1$. Since $a_1, a_2, \ldots, a_t$ are all odd iff $a_1 + 2, a_2 + 2 , \ldots, a_t + 2$ and $a_1 + 2, a_2 + 2 , \ldots, a_t + 2,1$ are all odd, we get that $4k, 4k + 2$ win iff $k$ wins, as desired.


Given $ f$ which are defined for all $ x,y\geq 0$
(1): $ f(0,y)\equal{}y\plus{}1$
(2): $ f(x\plus{}1,0)\equal{}f(x,1)$
(3): $ f(x\plus{}1,y\plus{}1)\equal{}f[x,f(x\plus{}1,y)]$
Find the greatest $ k\in N$ which satisfies $ 2^k$ divides $ f(4,2010)\minus{}f(3,2010)$

We can prove by induction the followings :
$ f(1,y) \equal{} 2 \plus{} y$
$ f(2,y) \equal{} 3 \plus{} 2y$
$ f(3,y) \equal{} 10 \plus{} 3y$
$ f(4,y) \equal{} 39 \plus{} 10y$
Therefore :
$ f(4 \minus{} 2010) \minus{} f(3,2010) \equal{} 2^5\times3\times17\times37$
And then, the greatest k is 5.

I think you should check your results again.
In fact, $ f(3,y)\neq 10\plus{}3y$ so $ k\equal{}5$ is not the solution !!!!!

You're right.
We have $ f(3,y) \equal{} 11 \times 2^y \minus{} 3$.
And the expression of $ f(4,y)$ would be very ugly.

[quote="mathboy2710"]Given $ f$ which are defined for all $ x,y\geq 0$
(1): $ f(0,y) \equal{} y \plus{} 1$
(2): $ f(x \plus{} 1,0) \equal{} f(x,1)$
(3): $ f(x \plus{} 1,y \plus{} 1) \equal{} f[x,f(x \plus{} 1,y)]$
Find the greatest $ k\in N$ which satisfies $ 2^k$ divides $ f(4,2010) \minus{} f(3,2010)$[/quote]

We have

$ f(1,n)\equal{}f(0,n\plus{}1)\equal{}n\plus{}2$

$ f(2,n)\equal{}f(1,2n\plus{}1)\equal{}2n\plus{}3$

$ f(3,n)\equal{}f \left(2,2^{n\plus{}2}\minus{}3\right )\equal{}2^{n\plus{}3}\minus{}3$

$ f(4,n)\equal{}\underbrace{2^{2^{...2}}}_{n\plus{}3}\minus{}3$

$ f(4,2010)\minus{}f(3,2010)\equal{}\underbrace{2^{2^{...2}}}_{2013} \minus{} 2^{2013}$

Hence the result is $ k\equal{}2013$


geometry
3D geometry
sphere
tetrahedron
ratio

Three mutually tangent spheres of radius 1 rest on a horizontal plane. A sphere of radius 2 rests on them. What is the distance from the plane to the top of the larger sphere?

$ \textbf{(A)}\; 3+\frac{\sqrt{30}}2\qquad
\textbf{(B)}\; 3+\frac{\sqrt{69}}3\qquad
\textbf{(C)}\; 3+\frac{\sqrt{123}}4\qquad
\textbf{(D)}\; \frac{52}9\qquad
\textbf{(E)}\; 3+2\sqrt{2} $

[hide]Connect the centers of the spheres. This will form a tetrahedron with three isosceles triangles as the lateral faces (3-3-2) and an equilateral triangle as the base (with side length equal to 2). The total distance is the length from the the top of the sphere to the center (radius 2) plus the height of the tetrahedron (we need to find) plus the height from the base of tetrahedron to the horizontal plane (radius 1).

Form the right triangle with the following as sides:

1) the height $h$ of the tetrahedron

2) the length $x$ of the segment from the center of equilateral triangle in the base to one of the vertices (or centers of unit spheres)

3) the lateral edge of length $s=3$

To find $x$, use the median property that the centroid cuts the median in 1:2 ratio so that the length is $x=\frac{2\sqrt3}3$

Pythagorean thrm yields $h^{2}=s^{2}-x^{2}=\frac{23}3$

The distance is $3+\frac{\sqrt{69}}3$[/hide]
EDIT: This problem is already posted a few days ago by [url=http://www.mathlinks.ro/Forum/profile.php?mode=viewprofile&u=8591]4everwise[/url] in [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=71754]Intermediate Topics[/url]


Let quadrilateral $ ABCD$. $ M,N,P,Q\in AB,BC,CD,DA$ such that $ MN,PQ,AC$ converge at $ X$.$ MQ.NP,BD$ converge at $ Y$. Let $ T,U$ such that $ (ACXT)\equal{}(BDYU)\equal{}\minus{}1$ . Prove that $ MP,NQ,TU$ are concurrent

[quote="Algadin"]Let quadrilateral $ ABCD$. $ M,N,P,Q\in AB,BC,CD,DA$ such that $ MN,PQ,AC$ converge at $ X$.$ MQ.NP,BD$ converge at $ Y$. Let $ T,U$ such that $ (ACXT) \equal{} (BDYU) \equal{} \minus{} 1$ . Prove that $ MP,NQ,TU$ are concurrent[/quote]
Solution:
Suppose $ MP$ intersects $ NQ$ at $ Z$. We will prove that $ T,U,Z$ are collinear. Let $ XZ\cap MQ \equal{} E$ and $ XZ\cap NP \equal{} F$, then obviously
$ (MQ,EY) \equal{} \minus{} 1$. Consider pencil $ A(MQ,EY)$ and its intersection with line $ BD$,it follows that $ A,E,U$ are collinear,Similarly $ C,F,U$ are collinear,too.Now let $ UZ\cap AC \equal{} T'$.But as we know $ (XZ,EF) \equal{} \minus{} 1$,hence it follows that $ T \equal{} T'$(it is enough to consider pencil $ U(XZ,EF)$ and its intersection with $ AC$).
$ \blacksquare$


http://ndp.jct.ac.il/tutorials/Discrete/node83.html

i don't understand how cantor's diagonal argument works.

i understand that all reals are printed on different lines.
and after that if a decimal is 0 then the $b_{i}=0$.
and if it is not 0 then $b_{i}=1$.
what is the ideea cantor's argument works around ?
because it is said that the list is not complete somewhere ?
i say.."so what,N cannot be listed also because it is infinite,does
that make N uncountable?NO".

What does listing of a set $S$ mean in this context? It means setting up a bijection from $\mathbb N$ to $S$ (the existence of $\mathbb N$ is an axiom, if I remember correctly).

Now, suppose that we can list the reals. Cantor's diagonal argument tells us that we can find a number which isn't in the list (because it differs from each of the numbers at some position). But that contradicts our assumption. So the assumption was wrong in the first place.

The same idea can be used to prove that $|S| < \left| \mathcal P (S) \right|$ ($\mathcal P (S)$ is the power set of $S$).

like what numbers or what kind of numbers are not listed ?


limit
logarithms
calculus
calculus computations

\[ \begin{gathered}
  {\text{Limits as: 1}}^{ \pm \infty }  \hfill \\
  {\text{How I can demostrate (or proof) that if: }} \hfill \\
   \hfill \\
  \mathop {\lim }\limits_{x \to a} g\left( x \right) \equal{} \infty  \hfill \\
  \mathop {\lim }\limits_{x \to a} f\left( x \right) \equal{} 1 \hfill \\
  {\text{then: }} \hfill \\
  \mathop {\lim }\limits_{x \to a} f\left( x \right)^{g\left( x \right)}  \equal{} e^{\mathop {\lim }\limits_{x \to a} g\left( x \right)\left( {f\left( x \right) \minus{} 1} \right)}  \hfill \\
  {\text{?}} \hfill \\
  {\text{Thanks}} \hfill \\
\end{gathered}
\]

thats my first  time posting here. If I commit any mistake let me know pls
thank u again.

if $ f>0$ then use :

$ f^g\equal{}e^{gln(f)}$

and $ ln(f)$ is approximately $ f\minus{}1$ when $ x \to a$

Consider the logarithm: $ \ln(f(x)^{g(x)}) \equal{} g(x)\ln(f(x)) \equal{} g(x)(f(x) \minus{} 1)\frac {\ln f(x)}{f(x) \minus{} 1}$. The fraction has limit $ 1$.

mmm I can't get it...
if would be validate for a proof?

 my question is how I could proof this if I didn't any ways to follow it.

greets

could u post all the proof?
because I beginning with this and I dont know too much about it.

thanks 4ur time.

The above mess is the result of vaxk posting the same question in two places and me merging the resulting topics. To vazk: that is not acceptable behavior on this site. Please post your question only once, in one place.

Ok sorry...

I could use this on limit of a sequence? ...
How I can prove this on it?

I mean, something like that:
\[ \begin{gathered}
  \mathop {\lim }\limits_{n \to \infty } \left( {\frac{{n \plus{} 3}}
{{n \plus{} 2}}} \right)^{n \plus{} 1}  \hfill \\
  \mathop {\lim }\limits_{n \to \infty } \left( {n \plus{} 1} \right)\left( {\frac{{n \plus{} 3}}
{{n \plus{} 2}} \minus{} 1} \right) \equal{} \mathop {\lim }\limits_{n \to \infty } \frac{{n \plus{} 1}}
{{n \plus{} 2}} \equal{} 1 \hfill \\
  {\text{Then: }} \hfill \\
  \mathop {\lim }\limits_{n \to \infty } \left( {\frac{{n \plus{} 3}}
{{n \plus{} 2}}} \right)^{n \plus{} 1}  \equal{} e \hfill \\
\end{gathered}
\]

thanks


A circle has a radius of 10 centimeters and a chord of the circle is 16 centimeters long. How many centimeters is the midpoint of the chord from the center of the circle?


linear algebra
matrix
linear algebra unsolved

Let $A\in\mathcal l M_n(\mathcal l Q)$ such that $\det(A+\sqrt[n]{2}I_n)=0$. Prove that $\det(A-I_n)=\det(A)+(\det(A+I_n))^n$.

Denote $P(x)=det(A-xI_n)$. Then as $P \in \mathbb{Q}[x]$ and $P(-(2)^{\frac{1}{n}})=0$, $P(x)=(-1)^nx^n+a_0$, and $a_0=-2$. Now what you need is to verify the identity $P(1)=P(0)+(P(-1))^n$


Let $ p,q$ be positive integers. Prove that there exist positive integers $ n$ and $ x_1<x_2<\dots<x_n$ such that
$ \frac pq\equal{}\frac1{x_1}\plus{}\frac1{x_1}\plus{}\cdots\plus{}\frac1{x_n}$


Find all tuples $ (a,b,c,d)$ of real numbers, such that the product of three numbers plus the fourth number gives for every possible choice the same value.

When there is a zero in $ (a,b,c,d)$ , say $ d$, then $ a\equal{}b\equal{}c\equal{}abc$ , so in this case solutions are $ (0,0,0,0)$, $ (1,1,1,0)$  or  $ (\minus{}1,\minus{}1,\minus{}1,0)$.
When there is no zero in $ (a,b,c,d)$ , let abcd=k, then we have $ \frac{k}{d}\plus{}d\equal{}\frac{k}{c}\plus{}c\equal{} \dots \equal{} m$ , where m is a real numbers .So values of $ a, b, c, d$ can only be the roots of $ x^2\minus{}mx\plus{}k\equal{}0$, say $ x_1, x_2$
So WLOG , assume that
Case 1:$ 3$ of them , say $ a,b,c\equal{}x_1$ are equal.Then $ {x_1}^3\plus{}x_2\equal{}x_2 {x_1}^2 \plus{} x_1$,
$ (x_1\minus{}x_2)({x_1}^2\minus{}1)\equal{}0$, so either all of them are equal or $ a\equal{}b\equal{}c\equal{}1$  or  $ \minus{}1$ are the solutions.
Case 2:$ a\equal{}b\equal{}x_1$  ,  $ c\equal{}d\equal{}x_2$ .Then $ {x_1}^2 x_2 \plus{} x_2\equal{} {x_2}^2 x_1 \plus{} x_1$  ,
$ (x_1 x_2 \minus{} 1)(x_1\minus{}x_2)\equal{}0$, $ a\equal{}b\equal{}k$ , $ c\equal{}d\equal{} \frac{1}{k}$ are the solutions.


USAMTS
geometry
geometric transformation
rotation

Please do not discuss the Round 2 problems or solutions until the official solutions are posted on the USAMTS website and are announced here.  This will occur later this week.

[quote="FantasyLover"]When does the round 2 score come out?[/quote]Probably the week of Dec 22-26.

[quote="gauss1181"]When will the problems for Round 3 be up?[/quote]Hopefully the week of Dec 1-5.

The Round 2 Solutions are now posted on the USAMTS website, and you may now discuss the Round 2 problems and solutions.

Round 3 problems will be posted during the week of Dec 1-5, and the Round 3 deadline is Jan 12.

Ok, the solution clarifies that there are 444 possible final positions, but I believe that some of them are counted for several times.

For instance, taking the example from the problem then rotating it 4 times, each time for 90 degrees, we have 4 final positions but they are the same in the view of Joe or Sarah! (Who knows where they were sitting and how they were looking at the game field?)

I solved this problem when I supposed I were Joe (The problem did not state that I cannot be Joe right?). So the number of possible final positions should be different.

Is my argument reasonable?

[quote="Yongyi781"]I think they will give you full credit if you solved it assuming that rotations were indistinguishable. (Assuming it is completely correct.)[/quote]

What if I did that and missed a case? do I still get like 1 or 2?

When I read your first sentence I thought you're going to say that they'd take off more for missing the harder case. Maybe I'm stupid, but I would do that if I were the grader (especially when someone does the harder case and misses the easier case I'd take off as little as possible).

[quote="Yongyi781"]I think that if you missed a case such as the diagonal case, then they would take off 2 points (since it's not that hard to see!).

If you missed the case when Joe can win before Sarah, that is much more subtle and they might only take off 1.[/quote]

Wow I'd still get a three for missing the diagonal?

Lol I missed the straight when its not on the edge.  :wallbash_red:  :wallbash:


inequalities logarithms function calculus derivative algebra domain

Prove that:
sqrt (b/b+8) + sqrt (c/c+8) >= 2 * sqrt (sqrt (bc) / sqrt(bc) +8).
for b>=0,c>=0.

vinoth_90_2004's problem:
Let $b,c \geq 0$, prove that:
${\sqrt{\frac{b}{b+8}}+\sqrt{\frac{c}{c+8}}\geq 2\sqrt{\frac{\sqrt{bc}}{\sqrt{bc}+8}}}$
   :D

Let $x = \frac{b}{b+8}$ and same for $y$.  Obviously $x,y \in [0,1)$.

Then it remains to show

$\sqrt{x} + \sqrt{y} \geq 2\sqrt{\frac{\sqrt{\frac{xy}{(1-x)(1-y)}}}{\sqrt{\frac{xy}{(1-x)(1-y)}} + 1}} = 2\sqrt{\frac{1}{1 + \frac{1}{\sqrt{\frac{xy}{(1-x)(1-y)}}}}}$

$\Leftrightarrow \frac{\sqrt{x} + \sqrt{y}}{2} \geq \sqrt{\frac{1}{1 + \frac{\sqrt{(1-x)(1-y)}}{\sqrt{xy}}}}$

$\Leftrightarrow \Bigg(\sqrt{ \sqrt{xy} + \sqrt{(1-x)(1-y)}} \Bigg) \Bigg(\sqrt{x} + \sqrt{y} \Bigg) \geq 2\sqrt{\sqrt{xy}}$

$\Leftrightarrow \Bigg( \sqrt{xy} + \sqrt{(1-x)(1-y)} \Bigg) \Bigg(\sqrt{x} + \sqrt{y} \Bigg) \Bigg(\sqrt{x} + \sqrt{y} \Bigg) \geq 4\sqrt{xy}$

notice we havent used any ineqs yet, only algebraic moving around.  obviously it isn't true.

[quote="Singular"]obviously it isn't true.[/quote]
This conclusion does not seem really obvious to me : take $x=\frac{1}{4}$, $y=0$ and the last two inequalities will hold true...

May I propose another point of view. First, suppose $b,c>0$. We define $\beta=\log b$, $\gamma=\log y$, and introduce the function

$f(t)=\sqrt{\frac{e^t}{e^t+8}}$ for $t\in\mathbb{R}$.

Then, [b]vinoth_90_2004[/b]'s inequality reads

$f(\beta) + f(\gamma)\geq 2f\left(\frac{\beta+\gamma}{2}\right)$

which looks like Jensen's inequality. This leads us to check whether or not $f$ is convex. Now, its second derivative

$f''(t)=4e^{-t}(1+8e^{-t})^{-3/2}\cdot\frac{4e^{-t}-1}{8e^{-t}+1}$

does change sign. We have $f''(t)\geq 0$ only for $e^{-t}\geq\frac{1}{4}$, that is, $\beta,\gamma\leq\log 4$. Therefore, [b]vinoth_90_2004[/b]'s inequality holds true for $0<b,c\leq 4$. In case one of the variables (or both of them) vanishes, the inequality can be checked directly. In conclusion, we are certain that it is true for

$0\leq b,c\leq 4$.

[quote="Christian Hirsch"]I don't think this inequality ist true  :huh: . Take [tex]b=1[/tex] and [tex]c\to\infty[/tex][/quote]

Monique, I think this message is true so the initial ineq is false?
As this ineq comes from vinoth's attempt of imo 01 q2, it has to be true for all positive b,c. Now we can see this is false.

[quote="siuhochung"]I think this message is true so the initial ineq is false?[/quote]
I agree with you and Christian Hirsch that this inequality is false, if it is to be considered for all $b,c>0$. What I simply wanted to prove is that it is true, however, if both $b,c$ are $\leq 4$ (I didn't know about the IMO background).

[quote="Monique"][quote="Singular"]obviously it isn't true.[/quote][/quote]
This conclusion does not seem really obvious to me : take $x=\frac{1}{4}$, $y=0$ and the last two inequalities will hold true...

When I say "obviously isn't true", I mean obviously isnt true _for all x and y in the specified domain_.

Obviously, its true if x=y.  That doesn't matter though.


induction
inequalities
algebra solved
algebra

[quote="Socc"]$\forall x,a_1,...,a_n>0$ prove that:
$\frac{1}{a_1+x}+\frac{a_1}{(a_1+x)(a_2+x)}+...+\frac{a_1a_2...a_{n-1}}{(a_1+x)(a_2+x)...(a_n+x)}< \frac{1}{x}$[/quote]

By induction on $n$ :
if $n=1$ then the result is true,
if it is true for $n-1$, then $A = \frac{1}{(a_2+x)}+...+\frac{a_2...a_{n-1}}{(a_2+x)...(a_n+x)}
<\frac{1}{x}$

but the expression of the left member of the inequality is given by
$B=\frac{1}{a_1+x} + \frac{a_1}{(a_1+x)} * A$
or $A<\frac{1}{x}$ thus $B< \frac{1}{a_1 + x} (1+\frac{a_1}{x}) <\frac{1}{x}$

Fabrice

Socc!
Please, read Problem Naming http://www.mathlinks.ro/viewtopic.php?p=140098
And name problems properly next time!

Regards,
Myth

BTW, Fabrice's solution is correct ;)

[quote="Socc"][quote="fmathurin"]By induction on $n$ :
if $n=1$ then the result is true,
if it is true for $n-1$, then $A = \frac{1}{(a_2+x)}+...+\frac{a_2...a_{n-1}}{(a_2+x)...(a_n+x)}
<\frac{1}{x}$[/quote]
Hmmm... I don't think you are right because we only have
$\frac{1}{(a_1+x)}+...+\frac{a_1...a_{n-1}}{(a_2+x)...(a_n+x)}
<\frac{1}{x}$
and $a_1,a_2,...,a_n$ had no arrangement[/quote]

You should read more carefully the elements which are on top
of the fractions in my induction.

Fabrice


Let $ G$ be a finite group. For arbitrary sets $ U, V, W \subset G$, denote by $ N_{UVW}$ the number of triples $ (x, y, z) \in U \times V \times W$ for which $ xyz$ is the unity .
Suppose that $ G$ is partitioned into three sets $ A, B$ and $ C$ (i.e. sets $ A, B, C$ are pairwise disjoint and $ G = A \cup B \cup C$). Prove that $ N_{ABC}= N_{CBA}.$

Not sure if this is correct  :(

Assume $ N_{ABC}=k$

for $ 1 \leq i,j \leq k$ we have  $ x_{i}(y_{i}z_{i}x_{j}y_{j}) z_{j}= (x_{i}y_{i}z_{i}) (x_{j}y_{j}z_{j}) = 1 \cdot 1 = 1$

so by minimality of $ k$ we have that $ (y_{i}z_{i}x_{j}y_{j}) \in \{y_{1},...,y_{k}\}$ Fix $ i$. then we can find a good $ j$ such that

$ (y_{i}z_{i}x_{j}y_{j})=y_{i}$

which gives us

$ z_{i}x_{j}y_{j}= 1$

so we transformed something of the form ABC to something of the form CAB. Similarly we can transform something from the form CAB to something of the form BCA, hence $ N_{ABC}=N_{BCA}=N_{CAB}$

Probably wrong  :blush:

edit: oopz, read it wrong :s

maybe if we can show that  $ 3 N_{ABC}= N_{ABC}+N_{CAB}+N_{BCA}= N_{CBA}+N_{ACB}+N_{BAC}= 3 N_{CBA}$ we have something

but it was a stupid idea from the start, excuses  :blush:

An induction based argument seems to work.

[i]Step 1.[/i] We analyze the case $ |C|=1$.
Suppose that $ A = \left\{ a_{1}, \ldots, a_{p}\right\}, \, B = \left\{ b_{1}, \ldots, b_{q}\right\}, C = \left\{ c \right\}$. Define $ A^\prime = A \cup \left\{ b_{q}\right\}, \, B^\prime = B \setminus \left\{ b_{q}\right\}$. I want to prove that
\[ N_{ABC}-N_{A^\prime B^\prime C}= N_{CBA}-N_{C B^\prime A^\prime}. \]
In the left, we subtract the no of pairs such that $ a_{k}b_{q}c = e$ and add the no of pairs such that $ b_{q}b_{k}c = e$. In the right, we subtract the no of pairs such that $ c b_{q}a_{k}= e$ and add the no of pairs such that $ c b_{k}b_{q}= e$. Those are equal iff the no of elements $ x$ from $ \left\{ a_{1}, \ldots, a_{p}, b_{1}, \ldots, b_{q-1}\right\}$ that verify $ x = b_{q}^{-1}c^{-1}$ is equal to those that verify $ x = c^{-1}b_{q}^{-1}$. If one of $ b_{q}^{-1}c^{-1}, \, c^{-1}b_{q}^{-1}$ is equal to $ b_{q}$ or $ c$, then $ b_{q}^{-1}$ and $ c^{-1}$ commute. This implies what we wanted.
So we have reduced $ |B|$ by one. We can go all the way down to $ |B| = 0$ and then the claim is trivial.

[i]Step 2.[/i] Suppose that $ |A| = p, |B| = n, |C| = m$.
Consider $ B^\prime = B \cup \left\{ c_{m}\right\}, \, C^\prime = C \setminus \left\{ c_{m}\right\}$. We prove again that
\[ N_{ABC}-N_{A B^\prime C^\prime}= N_{CBA}-N_{C^\prime B^\prime A}. \]
This is equivalent to proving our problem for $ D = A, \, E = B \cup C^\prime, \, F = \left\{ c_{m}\right\}$, so it follows from [i]Step 1[/i].
Again, we can go all the way down to $ |B| = 0$, and that's it.

I'm not guaranteeing it's correct, but I hope it is.

First see that for arbitrary subsets $ X, Y, Z$ of $ G$ we have:
i) $ N_{XYZ}\equal{}N_{YZX}\equal{}N_{ZXY}$ because $ xyz \equal{} e \Leftrightarrow yzx\equal{}e \Leftrightarrow zxy\equal{}e$
ii) $ N_{XYA}\plus{}N_{XYB}\plus{}N_{XYC} \equal{} |X\parallel{}Y|$ because for every pair $ (x,y)$ $ \epsilon$ $ (X,Y)$ exist exactly one solution $ z$ for $ xyz\equal{}e$ and it must be in exactly one of the sets $ A,B,C$. For the same reason: $ N_{XAY}\plus{}N_{XBY}\plus{}N_{XCY} \equal{} |X\parallel{}Y|$

With ii) we get:

$ N_{ABA}\plus{}N_{ABB}\plus{}N_{ABC} \equal{} |A\parallel{}B|$
$ N_{AAC}\plus{}N_{ABC}\plus{}N_{ACC} \equal{} |A\parallel{}C|$
$ N_{ABC}\plus{}N_{BBC}\plus{}N_{CBC} \equal{} |B\parallel{}C|$

And then:

$ 3N_{ABC}\plus{}N_{ABA}\plus{}N_{ABB}\plus{}N_{AAC}\plus{}N_{ACC}\plus{}N_{BBC}\plus{} N_{CBC} \equal{} |A\parallel{}B| \plus{} |A\parallel{}C| \plus{} |B\parallel{}C|$

Analogously:

$ 3N_{CBA}\plus{}N_{CBC}\plus{}N_{CBB}\plus{}N_{CCA}\plus{}N_{CAA}\plus{}N_{BBA}\plus{} N_{ABA} \equal{} |C\parallel{}B| \plus{} |C\parallel{}A| \plus{} |B\parallel{}A|$

With this equality, using i) and the fact tha all quantities above are finite cause $ G$ is finite we conclude that $ N_{ABC}\equal{}N_{CBA}$


[hide]
a) $\frac{n(n+1)}{2}$ (It was on the AOPS sidebar)
b) I forgot but its like a $3$ term formula
c) $(\frac{n(n+1)}{2})^{2}$ (It was on the AOPS sidebar)
d) Even: $n^{2}+n$ and Odd: $n^{2}$
[/hide]

hope this helped

Edit:
How do you make parentheses bigger on Latex?

[quote="MissSmartyPants"]Hey guys can you please help me?
I am really confused about the formulae to find the SUM of the...
a)First 'n' natural numbers
b)Squares of the first 'n' natural numbers
c)Cubes of the first 'n' natural numbers
d)First 'n' even/odd natural numbers
I checked out a number of text books but they are all really complicated and have different formulae except for a).... :lol:
Thanx!![/quote]

[hide="answer"]
the answer for a) is always going to be in this equation:

n(x+z)/2, where x=first term of the series, z=last term of the series

for example, a) would be:

1+2+3+4+5...+n = n(1+n)/2 because the first term is 1 and the last term is n.

b) is a bit different

it's in this format:

Sum = n(n+1)(2n+1)/6

c) is just squaring the equation for a)

d) i forgot the equation...=/

[/hide]


$ \Gamma$ is an ellipse with it's center $ O$, $ F$ is one focus point. $ CD$ is its prolate axis,
$ l$ is a line passes through $ F$ meets $ \Gamma$ at $ A$ and $ B$
Please find the minimum of $ \angle AOB$

The minimum angle does hapen when line AB is perpendicular to CD


Determine all natural $ n$ for which there exists natural $ m$ divisible by all natural numbers from 1 to $ n$ but not divisible by any of the numbers $ n \plus{} 1$, $ n \plus{} 2$, $ n \plus{} 3$.

If $ n+1 \neq p^k$ for prime $ p$, then
We can find two coprime factors of $ n+1$ , say $ a,b>1$ so that $ ab=n+1$ and ${ a,b \in \{1,2,...,n}$
This gives that $ n+1|lcm(1,2,...,n)$, contradiction.

Similarly for $ n \ge 3$, both $ n+2,n+3$ must be of the form $ p^k$

Case 1: $ n=1,2,3$, it's easy to check $ n=1,2$ are all solutions.
Case 2: $ n>3$ and $ n+1$ is even, then $ n+1=2^k$, $ 2^k<n+3<2^{k+1}$, so no solution in this case.
Case 3: $ n>3$ and $ n+2=2^k$ is even, then we have $ k>2$, if $ k$ is even, then $ n+1=x^2-1=(x+1)(x-1)=p^y$, impossible. So $ k$ is odd $ \Rightarrow n+3=2^k+1=0(mod 3) \Rightarrow n+3=3^m$, by similarly reason $ m$ cannot be even. $ \Rightarrow 2^k=n+2=3^m-1=(-1)^m-1=2(mod 4)$, which give $ k=1$, so there are no solution in this case.

So $ n=1,2$ are the only solutions.

Unfortunately I don't know why $ 2^k < n\plus{}3 < 2^{k\plus{}1}$ implies there is no solution...  :blush:

What about $ n\equal{}6$.
This problem was proposed on Bulgarian Sprint Mathematical Competition years ago.

[quote="stephencheng"]If $ n + 1 \neq p^k$ for prime $ p$, then
We can find two coprime factors of $ n + 1$ , say $ a,b > 1$ so that $ ab = n + 1$ and ${ a,b \in \{1,2,...,n}$
This gives that $ n + 1|lcm(1,2,...,n)$, contradiction.

Similarly for $ n \ge 3$, both $ n + 2,n + 3$ must be of the form $ p^k$

Case 1: $ n = 1,2,3$, it's easy to check $ n = 1,2$ are all solutions.
Case 2: $ n > 3$ and $ n + 1$ is even, then $ n + 1 = 2^k$, $ 2^k < n + 3 < 2^{k + 1}$, so no solution in this case.
Case 3: $ n > 3$ and $ n + 2 = 2^k$ is even, then we have $ k > 2$, if $ k$ is even, then $ n + 1 = x^2 - 1 = (x + 1)(x - 1) = p^y$, impossible. So $ k$ is odd $ \Rightarrow n + 3 = 2^k + 1 = 0(mod 3) \Rightarrow n + 3 = 3^m$, [/quote]

From $ k>2$, $ n+2=2^k$ and $ n+3=3^m$ then $ 3^m-2^k=1$ with only solution for $ m=2$, $ k=3$,
and thus $ n=6$ and $ m=30$

[quote="micf"]Unfortunately I don't know why $ 2^k < n + 3 < 2^{k + 1}$ implies there is no solution...  :blush:[/quote]

Notice that $ n+3$ is even but not a power of $ 2$ then it is not of the form $ p^k$

I think, only solution is n=1,2
n=6 , m=30 is not possible, because 30 is not divisible by 4.

Well, what about n=6, m=60? 60 is divisible by 4, but not by 8. So n=6 IS a solution.