limit
calculus
algebra
polynomial
function
derivative
real analysis

Without using series expansion of $ e^x$ and binomial expansion of $ \sqrt{1\plus{}x^2}$ evaluate the limit :
$ \lim_{x\to 0}\frac{e^x\minus{}x\minus{}\sqrt{1\plus{}x^2}}{x^3}$
Also,you cannot use the L'Hospital rule.

What is the point of excluding all of the truly useful tools? I mean, if you let me use my preferred tools, I can do this problem in my head, without writing anything down: the answer is $ \frac16.$ And if I can do that in my head, I would tend to think that I'm doing it the "right" way.

Well, I guess you [i]could[/i] do this particular problem without any calculus, but it'd be tedious, and like Kent Merryfield said it seems rather pointless.  Here's an outline, with the component proofs omitted:
(1) Prove that $ e^x \equal{} \lim_{n \to \infty}\left(1 \plus{} \frac {1}{n}\right)^{nx} \equal{} \lim_{n\to \infty}\left(1 \plus{} \frac {x}{n}\right)^n$
(2) By expanding, prove that the $ k$th coefficient of the polynomial $ \left(1 \plus{} \frac {x}{n}\right)^n$ approaches $ \frac {1}{k!}$ as $ n\to \infty$.
(3) Use (1) and (2) to conclude that $ 1 \plus{} x \plus{} \frac {x^2}{2} \plus{} \frac {x^3}{6}\leq e^x \leq 1 \plus{} x \plus{} \frac {x^2}{2} \plus{} \frac {x^3}{6} \plus{} cx^4$ for some constant $ c$.
(4) Prove that, for $ |x| < 1$, $ 1 \plus{} \frac {x^2}{2} \minus{} \frac {x^4}{8}\leq \sqrt {1 \plus{} x^2} \leq 1 \plus{} \frac {x^2}{2}$ (just square both sides).
(5) Use (3) and (4) to conclude that, if $ L$ is the original limit, then
\[ L\leq \lim_{x \to 0}\frac {\left(1 \plus{} x \plus{} \frac {x^2}{2} \plus{} \frac {x^3}{6} \plus{} cx^4\right) \minus{} x \minus{} \left(1 \plus{} \frac {x^2}{2} \minus{} \frac {x^4}{8}\right)}{x^3} \\
 \\
L\geq \lim_{x\to 0}\frac {\left(1 \plus{} x \plus{} \frac {x^2}{2} \plus{} \frac {x^3}{6}\right) \minus{} x \minus{} \left(1 \plus{} \frac {x^2}{2}\right)}{x^3}
\]
(6) Note that both limits in (5) are of rational functions and hence easy to evaluate.  Conclude by the squeeze theorem that $ L \equal{} \frac {1}{6}$.

(2) seems like the only part that could be difficult.  Note that in (2),(3) we're effectively just computing the series for $ e^x$, and in (4) we're proving a very special case of the binomial theorem.  I think just about any way you choose to prove this, whether you use calculus or not, will more or less boil down to using intuition from calculus.

In other words, you're building the Taylor polynomials anyway, just building them using arguments other than the derivatives. (Which is really your point anyway.) When I said I could do this in my head, of course I was using Taylor polynomials.

[quote="Kent Merryfield"]What is the point of excluding all of the truly useful tools?[/quote]
I know this can be annoying, but it's really interesting (of course hard) to find a solution without those tools.

I don't like takin' the derivative up and bottom, may be Taylor is one of the most useful tools to tackle limits like this one, but, it's nice to see alternate ways.

For example, one can compute $ \lim_{x\to0}\frac {e^x \minus{} x \minus{} 1}{x^2}$ without L'Hôpital's Rule or Taylor expansions. (I've tried to compute the original limit in the same fashion when calculating this last limit, but it didn't work, may be, we can see a solution without those tools.)

[quote="pankajsinha"]Without using series expansion of $ e^x$ and binomial expansion of $ \sqrt {1 \plus{} x^2}$ evaluate the limit :
$ \lim_{x\to 0}\frac {e^x \minus{} x \minus{} \sqrt {1 \plus{} x^2}}{x^3}$
Also,you cannot use the L'Hospital rule.[/quote]I can do it with [i]Mathematica[/i]. That's allowed, isn't it?

Here's a potential simplification -- maybe it will allow [b]Healker[/b] to use the method he mentioned for that simpler limit.

The limit does not change if you replace $ x$ with $ \minus{} x$.

$ L \equal{} \lim_{x\to 0}\frac {e^x \minus{} x \minus{} \sqrt {1 \plus{} x^2}}{x^3}$
$ L \equal{} \lim_{x\to 0}\frac { \minus{} e^{ \minus{} x} \minus{} x \plus{} \sqrt {1 \plus{} x^2}}{x^3}$

Averaging, $ L \equal{} \lim_{x\to 0}\frac {e^x \minus{} e^{ \minus{} x} \minus{} 2 x}{2 x^3}$

Thanks Healker and TZF, starting from where you left off,I think I have finally got it

Putting $ x\equal{}3t$

$ L \equal{} \lim_{t\to 0}\frac {e^{3t} \minus{} e^{ \minus{} 3t} \minus{} 6 t }{54 t^3}$

$ 54L \equal{} \lim_{t\to 0}\frac {(e^{t} \minus{} 1)^3 \plus{} (3e^{2t} \minus{} 3e^{t} \plus{} 1) \minus{} (e^{ \minus{} t} \minus{} 1)^3 \minus{} 3e^{ \minus{} 2t} \plus{} 3e^{ \minus{} t} \minus{} 1 \minus{} 6 t }{ t^3}$

$ 54L \equal{} \lim_{t\to 0}(\frac {e^t \minus{} 1}{t})^3 \plus{} (\frac {e^{ \minus{} t} \minus{} 1}{ \minus{} t})^3 \plus{} \frac {3e^{2t} \minus{} 3e^{ \minus{} 2t} \minus{} 3e^{t} \plus{} 3e^{ \minus{} t} \minus{} 6t}{t^3}$

$ 54L \equal{} \lim_{t\to 0}(\frac {e^t \minus{} 1}{t})^3 \plus{} (\frac {e^{ \minus{} t} \minus{} 1}{ \minus{} t})^3 \plus{} 48\frac {e^{2t} \minus{} e^{ \minus{} 2t} \minus{} 4t}{2(2t)^3} \minus{} 6\frac {e^t \minus{} e^{ \minus{} t} \minus{} 2t}{2(t)^3}$

$ 54L \equal{} 1 \plus{} 1 \plus{} 48L \minus{} 6L \equal{} 2 \plus{} 42L$

$ 12L \equal{} 2$

$ L \equal{} \frac {1}{6}$

How did you get that $ \lim_{t\to 0}\left(\frac {e^t \minus{} 1}{t}\right)^3 \equal{} 1$?  For that matter, how did you deduce a priori that the limit $ L$ exists to begin with?  One way or another these things require making a local approximation of exponentials near $ 0$, so to make your argument valid still requires deriving the first three terms of the Taylor polynomial for $ e^x$ and making estimates on the error.

[quote="JoeBlow"]How did you get that $ \lim_{t\to 0}\left(\frac {e^t \minus{} 1}{t}\right)^3 \equal{} 1$? [/quote]

$ \boxed{\lim_{h\rightarrow 0} \frac{e^h\minus{}1}{h}\equal{}1}$ is a definition by which we can find $ \frac{d}{dx}e^x\equal{}e^x$.


The function $ f$ satisfies \[f(x) \plus{} f(2x \plus{} y) \plus{} 5xy \equal{} f(3x \minus{} y) \plus{} 2x^2 \plus{} 1\] for all real numbers $ x$, $ y$. Determine the value of $ f(10)$.

[hide="Solution"]
If $ y \equal{} x/2$,
\[ f(x) \plus{} f(5x/2)\plus{}5x(x/2)\equal{}f(5x/2)\plus{}2x^2\plus{}1 \Longrightarrow f(x) \equal{} \frac{\minus{}x^2}{2}\plus{}1\]
Thus $ f(10) \equal{} \frac{\minus{}100}{2} \plus{} 1 \equal{} \minus{}49$.
[/hide]

[quote="worthawholebean"]([b]4[/b]) The function $ f$ satisfies

$ f(x) \plus{} f(2x \plus{} y) \plus{} 5xy \equal{} f(3x \minus{} y) \plus{} 2x^2 \plus{} 1$

for all real numbers $ x$, $ y$. Determine the value of $ f(10)$.[/quote]

[hide]
we want to cancel out values as much as possible to eliminate f(x) terms
so let's say x=3x-y
so f(x)=f(3x-y)
that means y=2x
we need that last 2x+y term to be 10
so we can see what f(10) is
so we end up with
$ f(2.5)\plus{}f(10)\plus{}5*2.5*5\equal{}f(2.5)\plus{}2*2.5*2.5\plus{}1$
$ f(10)\equal{}\minus{}49$
[/hide]

Here is another one:
Plug in $ x\equal{}10, y\equal{}5$ and you get
$ f(10)\plus{}f(20\plus{}5)\plus{}5*10*5\equal{}f(30\minus{}5)\plus{}10*10*2\plus{}1$
$ f(10)\plus{}250\equal{}201$
$ f(10)\equal{}\minus{}49$

Quick question -- In a solution like one given by azjps, how do you gaurantee that is the only solution?  Is there any way to check or prove this?

The idea is, if the equation is valid for all (x,y), it is valid for all (x,x/2), and therefore, [u]such a function[/u] must equal -x^2/2 + 1.

So he's shown that [i]if[/i] an equation satisfies the given functional relationship, [i]then[/i] it must satisfy f(x) = -x^2/2+1

Clearly, there is only one function that satisfies that. The question is, now does the converse hold?

So then you plug in f(x) = -x^2/2+1 into the relationship and find that it holds.

Don't do it so difficiultly that the question is quiet easy
make the equaion which are
2x + y=10
3x − y=10
combine them together to get
x=4
y=2
so take the values into the equation to get f(4)+f(10)+40=f(10)+32+1
because the function is availible for all real x and y
then we get f(4)=-7
so the function is f(x)=-(7/4)x
take x=10 into it toget the value f(10)=-(35/2)


A sequence of natural numbers $(a_{n})$ satisfies $a_{a_{n}}+a_{n}= 2n$ for all $n \in N$.
Prove that $a_{n}= n$.

Let $a_{n}=f(n)$, then it is equavalent to $f(n)+f(f(n))=2n$.
It is easy to show if
$f(x)+f^{(2)}(x)+...+f^{(n)}(x)=nx$ (were $f^{(k+1)}(x)=f(f^{(k)}(x))$ ) then f(x)=x if $f: R_{+}\to R_{+}$ or $f: N\to N$.

[hide]

We use a proof by induction.  For the base case, we see that  $a_{a_{1}}+a_{1}=2$.  Since both terms are natural numbers, they must both equal 1, so $a_{1}=1$.

Now, assume that $a_{n}=n$ for all $n=1, 2, \ldots , k-1$.  We will show that $a_{k}=k$.  First, assume that $a_{k}=k-p$, where $p \in N$.  Then $a_{a_{k}}=a_{k-p}=2k-(k-p)=k+p$.  But since $k-p<k$, by assumption $a_{k-p}=k-p$.  So we cannot have $a_{k}<k$.

Next, say $a_{k}=k+r$, where $r \in N$.  Then $a_{a_{k}}=a_{k+r}=2k-(k+r)=k-r$.  From here we get $a_{a_{k+r}}=a_{k-r}=2k-(k-r)=k+r$.  As above, since $k-r<k$, by assumption $a_{k-r}=k-r$.  So we cannot have $a_{k}>k$.

Since we cannot have $a_{k}<k$ and we cannot have $a_{k}>k$, we must have $a_{k}=k$.  This completes the inductive step and the assertion is proved.

   [/hide]


quadratics
MATHCOUNTS
algebra
quadratic formula

can somebody tell me the answer to this question please
solve for x:
3x2 - 7x +4= 0
the 2 after the first x means squared. i have heard of the quadratic formula, but im not sure how to do this problem. thanks for your help

I don't know if this is Mathcounts level, but here goes.
Factor out the equation: (3x-4)(x-1)=0.
You then get 3x-4=0 or x-1=0. Then just solve. x=3/4 or x=1.
I think a moderator should bump this forum to the Basics...

thanks, and as for the level of this question, i think that it is mathcounts level because mathcounts is a middle school competition, and i learned it in algebra I in 7th, which was in middle school.

But mathcounts goes beyond Middle School concepts not in that you have to know more, but you have to apply more. Factoring and the quadrartic are two elements that are considered "basics" to a middle schooler.

I know this have nothing to do with the question led14pa2 just asked, but for countdown, do you have to be able to factor stuff really fast? I'm just wondering because state is in 2 days....  :(  :)  :(  :)

YES!!! Mainly square roots and number factoring. Example:
Calculate:
(20+7)^2-(20-7)^2
Something like this pops up every year. The kids who can factor fast buzz in within a second or two. Maybe this is harder than one that would pop up on a countdown, but it's so much faster if you factor for example.
Also recall the chapter radical factoring question. B/c I was able to factor fast, I solved one of the most difficult problems in 5 seconds. Factoring is your FRIEND!!!

Wait, what problem was it? I don't remember... but anyways, how can you fast those problems within a few seconds, like the example you gave...

Well, in that problem's case, you have 27^2-13^2. That factors into (27+13)(27-13), which is 40*14. You can now mentally solve, giving you the answer of 560.

As I said earlier, this is probably a bit harder than the problems they give, which usually end up having 20* something...

whoa, scary.... anyways, good luck at state!  :D

I think a problem like this was on the 2005 school countdown round. the question asked for 5012 - 4992, and the answer would be
(501 + 499) (501 - 499) which gives you 2000.


What do you think the USAMO qualifying index score will be this year?

I'm thinking 220-225?

Below a 230 would be nice. That would mean I have an ok chance at qualifying again.

It will be n-1.5 where n is my USAMO index score.

I'm guessing 210-215. 220-225 seems quite high, given that last year's was 217, there are more USAMO qualifiers this year, and the AMC was harder, or at the very least not easier. But it will depend more on the AIME than the AMC.

Just watch the AIME be incredibly difficult... or incredibly easy. To throw off all our predictions.

I'd rather have it be incredibly difficult. I have a history of doing MUCH better on incredibly difficult things than incredibly easy things.

I think most USAMO indices are 215-222. 230 pretty much guaruntees that you get in. The USAMO expansion will artificially deflate it a few points, so I'd say 210 - 218 would be around where it'll be.

The USAMO index will be n+.5 where n is my index.

210-215. Max. I dont think it will get any higher than that. Last year with expansion was like 217.. and later 212.5 or something like that. So then... yeah it'll go down a little more with this expansion.


function
integration
search
real analysis
real analysis unsolved

Find all continous functions $ f: R->R$ knowing that $ \forall x \in R$ and $ \forall n \in N^{*}$we have the relation:
              $ n^{2} \int_{x}^{x+\frac{1}{n}}\ f(t)dt=nf(x)+{\frac{1}{2}}$.

Please mention the source next time. :) (Anyway, don't forget to search in the "Resources" section.)

http://www.mathlinks.ro/viewtopic.php?t=76824


function
integration
trigonometry
symmetry
calculus
calculus computations

Hello.  I am confused about something my professor said.  We were finding the inverse Fourier transform of $e^{-\omega^{2}t}$.  This should be, under the way we defined the transform,
\[\frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-\omega^{2}t}e^{-i\omega t}d\omega , \]
which may be rewritten in the form,
\[\frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-\omega^{2}t}\textrm{cos}(\omega t)d\omega-\frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-\omega^{2}t}i\ \textrm{sin}(\omega t)d\omega . \]
Now here comes the part I don't understand.  He said that because sin is an odd function, the R.H.S. disappears.  And the L.H.S. is simply double the value when integrated from 0 to $\infty$.  I understand how this works in most cases, but I feel like this does not work due to the asymmetry of $e^{-\omega^{2}t}$.  Can someone explain?  Thank you very much.

[quote="pyrexyn"]Hello.  I am confused about something my professor said.  We were finding the inverse Fourier transform of $e^{-\omega^{2}t}$.  This should be, under the way we defined the transform,
\[\frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-\omega^{2}t}e^{-i\omega t}d\omega , \]
which may be rewritten in the form,
\[\frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-\omega^{2}t}\textrm{cos}(\omega t)-\frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-\omega^{2}t}i\ \textrm{sin}(\omega t) . \]
Now here comes the part I don't understand.  He said that because sin is an odd function, the R.H.S. disappears.  And the L.H.S. is simply double the value when integrated from 0 to $\infty$.  I understand how this works in most cases, but I feel like this does not work due to the asymmetry of $e^{-\omega^{2}t}$.  Can someone explain?  Thank you very much.[/quote]

[b]Theorem:[/b] The product of two even functions is an even function.

[b]Answer to Question:[/b] $\cos (\omega )$ is even because,
$\cos (\omega ) = \cos (-\omega)$
And $e^{-\omega^{2}}=e^{-(-\omega)^{2}}$
So,
$\cos (\omega) e^{-\omega^{2}}$ is even.

Don't forget the $d$(whatever) in your integrals. The symmetry works in the variable that actually matters.

Thank you!  For some reason, I had imagined the graph of $e^{-\omega^{2}t}$ as one similar to the asymmetric graph of a standard exponential function.  Stupid mistakes...


induction
number theory unsolved
number theory

Let $p$ be a prime number, $n$ a nonnegative integer, $a_i$ is the coefficient of $p^i$ in expansion of $n$ in the base $p$, k is the highest power of $p$ that is less than or equal to $n$ and $2r-1$ is the largest odd number less than or equal to $k$. Show that the rightmost nonzero digit of $n!$ written in base $p$ is

\[ (-1)^{a_1+a_3+\cdots+a_{2r-1}}\cdot a_0!\cdot a_1!\cdot \dots \cdot a_k!\mod{p}.  \]

Define $r(n)$ as the rightmost nonzero digit of $n!$ in base $p$ and $l(n): = (-1)^{a_1+a_3+a_5+...+a_{2r-1}} a_0 ! a_1 ! ... a_k !$ (note that I changed the exponent of $(-1)$ since otherwise it seems wrong).
So we want to prove $r(n)=l(n)$.

It's clearly true for $p=2$, so assume $p$ to be odd, or equivalently, $p-1$ to be even.
By induction:
It's clearly true for $n=1$.

So now let $n=a_0+a_1 p + ... + a_k p^k$ and $p^s$ be the highest power of $p$ dividing $n+1$, so $s$ carry over will occure when adding $1$.
Note that $p-1$ occurs $s$ times at the end of $n$, so after adding $1$, the $s$ factors $(p-1)! \equiv -1 \mod p$ in $l(n)$ will get $0!=1$ in $l(n+1)$. Thus there are $s$ changes of sign.
When $s$ is even, the $(-1)$-factors from the $(p-1)!$ kill each other and the exponent of $(-1)$ changes by a multiple of $p-1$, so by an even number and so the sign of the whole term remains the same.
Similary, when $s$ is odd, the sign changes in the faculties and in the exponent since $a_s$ grows by one, so again the sign is preserved.
So we conclude $l(n+1) = (a_s+1) l(n) \equiv (a_s+1)r(n) \equiv r(n+1) \mod p$ and are done.

Yes. You are right when saying that exponent of $(-1)$ is $a_1+a_3+\cdots+ a_{2r-1}$. Nice solution!

I've got a question.... how can this result can be generalised when $p$ is not a prime number...for example when everything is written in decimal system

[quote="jastrzab"]when everything is written in decimal system[/quote]
I don't know the general case but in decimal system we have $rnzd((5n)!)=rnzd(2^nn!)$ where rnzd denotes the rightmost nonzero digit. Using this and congruences it is pretty easy to calculate the rightmost nonzero digit of $n!$ in decimal system.

Yes thank you very much....:) but are we able to do this having information only about digits of $n$ in decimal representation??

I have seen this problem only in the case where base is $10$. $10=2\cdot 5$ so if we are working in base $pq,p\not =q, p,q\in\mathbb{P}$ it might be true that $rnzd ((pn)!)=rnzd(q^nn!)$, but that is only a conjecture of mine. I have seen the problem only in one book of mine and I just gave all information I know about the problem.


Well, I've never seen a Science Olympiad topic so I decided to post one.

Anyways, our team went to nats last year but didn't place very well...

We came 9th this year in MI... our best is 6th

Middle or High school...we did REALLY bad. but I placed 9th in Write it do it. This was my first year....

Middle School...
This is my first year too; I came 2nd in Metric Mastery (I was a team by myself it, so it was unfair for me), 8th in ballon race (alone again), and 3rd in Science Crime Busters (actually had a partner this time)

In 7th and 8th grade, I attended Kealing Middle School and was on the SciO team both years. In 7th grade, my team placed 2nd in Texas and got to compete in Nationals at Illinois. In 8th grade, my team got 1st in Texas and 30th at Nationals in Indiana. My high school (LBJ/LASA) got 1st at the state competition in 2007/last school year, but I didn't participate in SciO last school year.
State Medals (8th grade):
2nd Don't Bug Me (33rd at Nats)
2nd Amphibians and Reptiles (a Texas-only event)
5th Dynamic Planet (glaciers) (38th at Nats)
2nd Mission Possible (don't remember what I got for this event at Nats)


given triangle ABC, AD is height, K is tangent point of segment BC and circle inscribed into triangle ABC. M is the middle point of segment AD. line KM intersects circle inscribed into triangle ABC at point N. Prove that circle inscribed into triangle ABC is tangent at point N to the circumscribed circle of triangle BCN.

 :o

a shortlist problem:

http://www.mathlinks.ro/viewtopic.php?p=118682#p118682


Of a polynomial f(x) = \sum ni=0  aixi  with integral coefficients ai about the primes p1 p2 we know: f((p1)2 ) = -56 and f((p2) 2 ) = 56. Determine all solutions p1 and p2.


How many numbers are in the following list:

\[ \minus{}4, \minus{}1, 2, 5,\ldots, 32\]

If we add 4 to every term in the sequence, we still have the same number of terms, so let's do that:

We now have: 0, 3, 6, 9, ... , 36

(Notice, there are still the same number of terms)

Now, if we divide each term by 3, we will still have the same number of terms (No two terms are the same, so if we divide them all by one constant, we'll get a set of numbers that are likewise all different numbers, which prevents us from undercounting all of the terms), so let us divide by 3:

We now have: 0, 1, 2, 3, 4, 5, ... , 12

See? Now it is so much easier to count the number of terms in the sequence! We can simply see that the answer to the question is 13.

After a while, this becomes very easy to do in your head, making problems like this a breeze.

Oh, and if I'm just confusing you, watch Richard R's videos:
http://www.artofproblemsolving.com/Resources/video.php?video_id=31
http://www.artofproblemsolving.com/Resources/video.php?video_id=33

Hope you learned something!

[i][b][u]ANSWER[/u][/b][/i]: 13

[hide="My solution"] We see that they're going from $-4$ to $-1$, $2$, and they're going up my $3$ each time, and all I did was count up 3 each time to get to $32$
$-4=1$
$-1=2$
$2=3$
$5=4$
 $8=5$
$11=6$
$14=7$
$17=8$
$20=9$
$23=10$
$26=11$
$29=12$
$32=13$

The reason I am going up 3 each time is because as we see from $-4 to -1$ is $3$ I am also putting the numbers labeled 1-13 to know how many numbers they're in the sequence, just to keep track, and it can be confusing for some people. So, I will just get to the answer which is $\boxed{13}$ Hope this post helped some! [/hide]


Let $ a_{n\plus{}1}\equal{}\frac{k\plus{}a_{n}}{1\minus{}a_{n}}$, where $ k>0$.
We know, that $ a_{14}\equal{}a_{1}$. What could be the value of $ k$?

EDIT: this is a problem from here: http://www.nxbgd.com.vn/toanhoctuoitre/?p=7&id=6&ReportID=289&ph=25

T9/362

has $ 13$ instead of $ 14$...

[quote="Yuriy Solovyov"]Let $ a_{n \plus{} 1} \equal{} \frac {k \plus{} a_{n}}{1 \minus{} a_{n}}$, where $ k > 0$.
We know, that $ a_{14} \equal{} a_{1}$. What could be the value of $ k$?[/quote]
Consider sequence
$ p_1\equal{}a_1,q_1\equal{}1$
$ p_{n\plus{}1}\equal{}kq_n\plus{}p_n$
$ q_{n\plus{}1}\equal{}q_n\minus{}p_n$
Then we have:
$ a_n\equal{}\frac{p_n}{q_n}$ and use this to find out general of this sequence then it quite easy.

There exist solution using trigonometry.... try to find it  :)


Let $ a,$ $ b,$ $ c$ be positive real numbers. Prove that
$ \sqrt{\frac{a^2\plus{}\left(\frac{a\plus{}b}{2}\right)^2\plus{}\left(\frac{a\plus{}b\plus{}c}{3}\right)^2}{3}} \le \frac{a\plus{}\sqrt{\frac{a^2\plus{}b^2}{2}}\plus{}\sqrt{\frac{a^2\plus{}b^2\plus{}c^2}{3}}}{3}.$

[quote="can_hang2007"]Let $ a,$ $ b,$ $ c$ be positive real numbers. Prove that
$ \sqrt {\frac {a^2 \plus{} \left(\frac {a \plus{} b}{2}\right)^2 \plus{} \left(\frac {a \plus{} b \plus{} c}{3}\right)^2}{3}} \le \frac {a \plus{} \sqrt {\frac {a^2 \plus{} b^2}{2}} \plus{} \sqrt {\frac {a^2 \plus{} b^2 \plus{} c^2}{3}}}{3}.$[/quote]

Very Very nice my Friend.... Happy New Year  :)

Notice that $ f(x_1,\cdots,x_n ) \equal{} \sqrt {\frac {\sum x_i^2}{n}}$  is a convex function. (Checking definition directly by using Cauchy)

Consider $ n \equal{} 6$. By Jensen,
$ f(a,a,a,a,a,a) \plus{} f(a,a,a,a,a,a) \plus{} f(a,a,a,b,b,b) \plus{} f(a,a,b,a,b,b) \plus{} f(a,a,b,b,c,c) \plus{} f(a,a,b,b,c,c) \ge 6 f\left(a,a,\frac {a \plus{} b}{2},\frac {a \plus{} b}{2},\frac {a \plus{} b \plus{} c}{3},\frac {a \plus{} b \plus{} c}{3}\right)$
So,
$ \frac {f(a,a,a,a,a,a) \plus{} f(a,a,a,b,b,b) \plus{} f(a,a,b,b,c,c)}{3}$
$ \ge f\left(a,a,\frac {a \plus{} b}{2},\frac {a \plus{} b}{2},\frac {a \plus{} b \plus{} c}{3},\frac {a \plus{} b \plus{} c}{3}\right)$
which is what we want.

[quote="leviethai"]Solution

We have a well-known Lemma:

$ \sqrt {{x^2} \plus{} {y^2} \plus{} {z^2}} \plus{} \sqrt {{m^2} \plus{} {n^2} \plus{} {p^2}} \ge \sqrt {{{\left( {x \plus{} m} \right)}^2} \plus{} {{\left( {y \plus{} n} \right)}^2} \plus{} {{\left( {z \plus{} p} \right)}^2}}$
 $ x,y,z,m,n,p \in R$

$ \Leftrightarrow {x^2} \plus{} {y^2} \plus{} {z^2} \plus{} {m^2} \plus{} {n^2} \plus{} {p^2} \plus{} 2\sqrt {\left( {{x^2} \plus{} {y^2} \plus{} {z^2}} \right)\left( {{m^2} \plus{} {n^2} \plus{} {p^2}} \right)}$

$ \ge {x^2} \plus{} {y^2} \plus{} {z^2} \plus{} {m^2} \plus{} {n^2} \plus{} {p^2} \plus{} 2\left( {xm \plus{} yn \plus{} zp} \right)$

$ \Leftrightarrow \sqrt {\left( {{x^2} \plus{} {y^2} \plus{} {z^2}} \right)\left( {{m^2} \plus{} {n^2} \plus{} {p^2}} \right)} \ge \left( {xm \plus{} yn \plus{} zp} \right)$

(According to Cauchy Schwartz inequality, the inequality is true)

From the Lemma, it is easy to prove that:

$ \sum\limits_{i \equal{} 1}^6 {\sqrt {a_i^2 \plus{} b_i^2 \plus{} c_i^2} } \ge \sqrt {{{\left( {\sum\limits_{i \equal{} 1}^6 {{a_i}} } \right)}^2} \plus{} {{\left( {\sum\limits_{i \equal{} 1}^6 {{b_i}} } \right)}^2} \plus{} {{\left( {\sum\limits_{i \equal{} 1}^6 {{c_i}} } \right)}^2}}$
 $ {a_i},{b_i},{c_i} \in R$

From above inequality, we have,

$ \sqrt {{a^2} \plus{} {{\left( {\dfrac{{a \plus{} b}}{2}} \right)}^2} \plus{} {{\left( {\dfrac{{a \plus{} b \plus{} c}}{3}} \right)}^2}}$

$ \equal{} \sqrt {{{\left( {\dfrac{a}{6} \plus{} \dfrac{a}{6} \plus{} \dfrac{a}{6} \plus{} \dfrac{a}{6} \plus{} \dfrac{a}{6} \plus{} \dfrac{a}{6}} \right)}^2} \plus{} {{\left( {\dfrac{a}{6} \plus{} \dfrac{a}{6} \plus{} \dfrac{a}{6} \plus{} \dfrac{b}{6} \plus{} \dfrac{b}{6} \plus{} \dfrac{b}{6}} \right)}^2} \plus{} {{\left( {\dfrac{a}{6} \plus{} \dfrac{a}{6} \plus{} \dfrac{b}{6} \plus{} \dfrac{b}{6} \plus{} \dfrac{c}{6} \plus{} \dfrac{c}{6}} \right)}^2}}$

$ \le 2\sqrt {{{\left( {\dfrac{a}{6}} \right)}^2} \plus{} {{\left( {\dfrac{a}{6}} \right)}^2} \plus{} {{\left( {\dfrac{a}{6}} \right)}^2}} \plus{} \sqrt {{{\left( {\dfrac{a}{6}} \right)}^2} \plus{} {{\left( {\dfrac{a}{6}} \right)}^2} \plus{} {{\left( {\dfrac{b}{6}} \right)}^2}}$

$ \plus{} \sqrt {{{\left( {\dfrac{a}{6}} \right)}^2} \plus{} {{\left( {\dfrac{b}{6}} \right)}^2} \plus{} {{\left( {\dfrac{b}{6}} \right)}^2}} \plus{} 2\sqrt {{{\left( {\dfrac{a}{6}} \right)}^2} \plus{} {{\left( {\dfrac{b}{6}} \right)}^2} \plus{} {{\left( {\dfrac{c}{6}} \right)}^2}}$

$ \Rightarrow \sqrt {{a^2} \plus{} {{\left( {\dfrac{{a \plus{} b}}{2}} \right)}^2} \plus{} {{\left( {\dfrac{{a \plus{} b \plus{} c}}{3}} \right)}^2}}$

$ \le \dfrac{a}{{\sqrt 3 }} \plus{} \sqrt {\dfrac{{2{a^2} \plus{} {b^2}}}{{36}}} \plus{} \sqrt {\dfrac{{2{b^2} \plus{} {a^2}}}{{36}}} \plus{} \dfrac{{\sqrt {{a^2} \plus{} {b^2} \plus{} {c^2}} }}{3}$

$ \Rightarrow \sqrt {3\left[ {{a^2} \plus{} {{\left( {\dfrac{{a \plus{} b}}{2}} \right)}^2} \plus{} {{\left( {\dfrac{{a \plus{} b \plus{} c}}{3}} \right)}^2}} \right]}$

$ \le a \plus{} \dfrac{{\sqrt {3\left( {2{a^2} \plus{} {b^2}} \right)} \plus{} \sqrt {3\left( {2{b^2} \plus{} {a^2}} \right)} }}{6} \plus{} \sqrt {\dfrac{{{a^2} \plus{} {b^2} \plus{} {c^2}}}{3}}$

Therefore, it is enough to check that,

$ a \plus{} \dfrac{{\sqrt {3\left( {2{a^2} \plus{} {b^2}} \right)} \plus{} \sqrt {3\left( {2{b^2} \plus{} {a^2}} \right)} }}{6} \plus{} \sqrt {\dfrac{{{a^2} \plus{} {b^2} \plus{} {c^2}}}{3}}$
$ \le a \plus{} \sqrt {\dfrac{{{a^2} \plus{} {b^2}}}{2}} \plus{} \sqrt {\dfrac{{{a^2} \plus{} {b^2} \plus{} {c^2}}}{3}}$

$ \Leftrightarrow \dfrac{{\sqrt {3\left( {2{a^2} \plus{} {b^2}} \right)} \plus{} \sqrt {3\left( {2{b^2} \plus{} {a^2}} \right)} }}{6} \le \sqrt {\dfrac{{{a^2} \plus{} {b^2}}}{2}}$

$ \Leftrightarrow \sqrt {2{a^2} \plus{} {b^2}} \plus{} \sqrt {2{b^2} \plus{} {a^2}} \le \sqrt {6\left( {{a^2} \plus{} {b^2}} \right)}$

$ \Leftrightarrow 3\left( {{a^2} \plus{} {b^2}} \right) \plus{} 2\sqrt {\left( {2{a^2} \plus{} {b^2}} \right)\left( {2{b^2} \plus{} {a^2}} \right)} \le 6\left( {{a^2} \plus{} {b^2}} \right)$

$ \Leftrightarrow 2\sqrt {\left( {2{a^2} \plus{} {b^2}} \right)\left( {2{b^2} \plus{} {a^2}} \right)} \le 3\left( {{a^2} \plus{} {b^2}} \right)$

$ \Leftrightarrow 4\left( {2{a^2} \plus{} {b^2}} \right)\left( {2{b^2} \plus{} {a^2}} \right) \le 9{\left( {{a^2} \plus{} {b^2}} \right)^2}$

$ \Leftrightarrow 8\left( {{a^4} \plus{} {b^4}} \right) \plus{} 20{a^2}{b^2} \le 9\left( {{a^4} \plus{} {b^4}} \right) \plus{} 18{a^2}{b^2}$

$ \Leftrightarrow 0 \le {\left( {{a^2} \minus{} {b^2}} \right)^2}$ (which is true)

Equality holds if and only if $ a \equal{} b \equal{} c$.

P/S: HAPPY NEW YEAR EVERYONE[/quote]
My proof also used Minkowsky's Inequality, just like yours. However, can you prove that:

Let $ a_1,$ $ a_2,$ $ \ldots,$ $ a_n$ be positive real numbers. Setting
$ A_k \equal{}\frac{a_1\plus{}a_2\plus{}\cdots \plus{}a_k}{k}$
and
$ S_k \equal{}\sqrt{\frac{a^2_1\plus{}a^2_2\plus{}\cdots \plus{}a^2_k}{k}}$
for $ k\equal{}1,$ $ 2,$ $ \ldots,$ $ n.$ Prove that
$ \sqrt{\frac{A^2_1\plus{}A^2_2\plus{}\cdots \plus{}A^2_n}{n}} \le \frac{S_1\plus{}S_2\plus{}\cdots \plus{}S_n}{n}.$


The results are out .
India has two golds,2 silver and 1 honorable mention. :thumbup:  :coolspeak:
[url=http://www.ipho2007.ir/Results/results.asp]Here[/url] are the final results.

Japan also has got 2 Gold, 2 silver and 1 bronze! :lol:
Asian people had good job.
Congraturations!

china is first,south korea second
so asia is the best :lol:


Im going to college for Finance this fall and I also plan to study economics and accounting outside of school for some independent study I want to get an early start on it and from what ive been hearing its all about math and I was wondering if anyone could tell me exactly what kind of math is used for those fields I've heard of financial mathematics and mathematical economics are these the only two I would need? Also if anyone knows of any books i should purchase that would be helpful.

Recently there have been several new books published on the mathematics of finance. Sometimes the book titles are directly related to the subject, such as Mathematics of Finance or Financial Mathematics. A good book for learning about the human side of financial modeling is My Life As a Quant by Emanuel Derman.


conics
analytic geometry
ellipse
calculus
calculus computations

can anyone please prove the following? i can't seem to think of any way on how to prove it.... :blush:

[img]http://img74.imageshack.us/img74/3338/untitledjk8.jpg[/img]

Denote the coordinate of any $ P$ is$ (x,y)$, so all the points $ (\frac{3}{2}x,y)$are on the original circle.

Hence,$ ( \frac{3}{2}x)^{2}+y^{2}=r^{2}\Rightarrow (\frac{9x^{2}}{4})+y^{2}=r^{2}$.This show that the locus we want is an ellipse!


graph theory
algorithm
combinatorics
game
IMO Shortlist

[color=#f00]For context, the following is the original wording found in the first post of this thread. ~dj

In a country there are $n>3$ cities. We can add a street between $2$ cities $A$ and $B$, iff there exist $2$ cities $X$ and $Y$ different from $A$ and $B$  such that there is no street between $A$ and $X$, $X$ and $Y$, and $Y$ and $B$. Find the biggest number of streets one can construct![/color]

I'll restate it, so that it's [b]exactly[/b] like in ISL 2004 ;).

We are given a complete graph on $n$ vertices, and the only allowed operation is to find a $4$-cycle, pick one of its edges, and delete it. The question is: what is the minimal number of edges we're left with? (the answer to the problem from the TST is then obtained from that one by subtracting it from $\frac{n(n-1)}2$)

I think the answer (to the reworded question) is $n$:

I'm sure constructing n example with $n$ edges is not a problem, so I'll focus on proving that it's the minimal value. First of all (even though we could skip this part and go straight to showing that the minimal number is $n$), it's obvious that an operation does not disconnect the graph, so the minimal number of edges left is $\ge n-1$. What we have to show is that it cannot be $n-1$, i.e. that we can't be left with a tree in the end.

Assuming that in the end we're left with a tree, there must be a moment when we destroy the last odd cycle. This can only be done if the edge we remove in the respective operation belongs to the cycle. A quick look through all the cases should show that getting rid of all the odd cycles like this is impossible (the cases being: the odd cycle our edge is on and the $4$-cycle necessary for the operation share precisely one edge, the one we remove, or $2$ edges, or $3$, and, when they share $2$ edges, the two edges could be adjacent or opposite in the $4$-cycle, so there are $4$ cases in total, all of them easy to check).

Is it Ok?

Or also noting tha if we end up with a tree it is bypartite, and recovering our graph would keep it bypartite Implying that ourm initial complete graph was bypartite too, contradiction!

nice.
another interesting problem would be to determine exactly which graphs can be reached from a complete graph in this way.
we know that bipartite graphs can't be reached, but i have the following question:
can all non-biparitite connected spanning subgraphs be reached?

Can anyone tell me if this is correct?

Claim: Every non-bipartite connected graph can be reached from a complete graph by the operation of deleting an edge of a 4-cycle.

Proof:
Suppose that there exists a non-bipartite and connected graph such that no edge addition creates a 4-cycle, call it $G$.
First lets prove $G$ contains a $K_3$.
Since $G$ is not bipartite consider the smallest odd cycle, say $v_1,...,v_{2k+1}$. If $k=1$ we are done so assume $k>1$. Then the edge $v_1 v_4$ does not exists since it would create a smaller odd cycle, so we can add an edge between these vertices but adding it would createa 4-cycle. Contradiction, so $k=1$, and we have the disired $K_3$.

Now lets prove $G$ can not contain a $K_3$.
Suppose $G$ contains a $K_3$ say $T$. Let $K$ be the largest complete graph containing $T$, (maybe $T=K$). $G$ can't be $K$ because we would not be able to perform the opperation of adding an edge. So there exist a vertex $x$ that is adjacent to some vertices of $K$ (since the graph is connected) but not to all (since $K$ is the largest complete graph containing $T$). Since $x$ has at least one neighbor in the complete graph $K$, adding any edge from $x$ to another vertex of $K$ creates a 4-cycle. Contradicton, so $G$ must contain a $K_3$

I'll go with the official wording.

[hide=" Solution"]
I claim that the answer is $n$. The base case $n=4$ is trivial. For the inductive step, assume, on the contrary, that there can be only $n$ edges remaining after performing such operations on a $n+1$ complete graph. Since there cannot be any less than $n$ edges remaining after operating on a $n$ complete graph, one of the vertices in the $n+1$ complete graph must have degree 0. This, however, is impossible, because after each operation, the degree of that vertex decreases by at most 1, and that vertex clearly cannot be a part of a cycle with length 4 when its degree is 1.

It is easy to show that $n$ can be achieved- the base case $n=4$ is again trivial. Suppose a construction exists for $n$ vertices. Now, consider a $n+1$ complete graph, consider a particular vertex $V$ and a particular edge $E$ passing through $V$. For all other edges $F$ passing through $V$, just consider a cycle with length 4 and which contains $E, F$, and delete $F$. At the end, only one edge $E$ passes through $V$. Thus, there are $n+1$ edges. [/hide]

[hide]An easy one,here is my first solution(I think it is more intuitive than the second one):Obviosly the connectivity doesn't change,so we must have at least $n-1$ edges.Now,to prove that $n$ is minimum we will prove that a connected graph with $n$ vertices cannot have a $4$ cycle and this is obvios if we consider a tree we se that for a $4$ cycle we need at least $n+1$ edge,so done(example is obvios).Second solution is same as above.[/hide]

Is not hard! I explain official wording

I prove there is always some odd cycle. At beginning is obvious. Now at any point, take smallest odd cycle $A_1A_2 \ldots A_m$ with odd $m$. Notice that no edges $A_kA_{\ell}$ exist if $k, \ell$ not consecutive. If cycle is destroyed, then assume we deleted $ A_1A_2$.

If the 4cycle we took was $A_1A_2XY$ with $X,Y \neq A_i$ then new odd cycle exists! $A_3 \ldots A_m XY$.

If the 4cycle we took was $ A_1A_2A_3X$, is easy to see $ X \neq A_i$ so a new odd cycle exists! By replacing $A_2$ with $X$.

And is obvious the 4cycle cannot be $A_1A_2A_iA_j$ because this means $i=3, j=m$ but $3,m$ are not consecutive in my cycle.

So there is always odd cycle!

Also notice that graph is always connected, since if we used edge $XY$ from 4cycle $XYZW$, then we can use $XWZY$ instead.

So graph is connected and has a cycle so it has at least $n$ edges!

Construction is inductive and very easy.

The answer is $\boxed{n}$!

I attempted this problem about an year ago and solved it, but at that time I didn't post a solution. So I'l do that now.
Experimenting with small value suggests that the answer is $n.$
[i]Lemma 1.[/i] The answer is no less than $n.$
[i]Proof.[/i] Of course, note that no vertex can become independent by such operations, and we cannot destroy the existence of a cycle so at any point in time we have at least $n$ edges.
[i]Lemma 2.[/i] This $n$ is indeed achievable.
[i]Proof.[/i] For $n=4$ we can easily show this: if the graph is $abcd$ then delete $\overline{ab},\overline{ac}.$ Now we use induction. Let this result be true for some $n.$ We shall prove it for $n+1.$ Let the vertices be $A_1,..,A_{n+1}.$ First delete the edges $A_{n+1}A_1,A_{n+1}A_2,...,A_{n-1}A_n.$ Now $A_{n+1}$ has only one neighbor so we can effectively ignore it. By the induction hypothesis we can delete edges so that finally $n$ edges other than $A_{n+1}A_n$ are present. Hence we finally have $n+1$ edges as claimed. By induction the lemma has been proved.

By the above lemmas, the answer is $n$ edges.

[quote=dgrozev][quote=AdithyaBhaskar]...
[i]Lemma 1.[/i] The answer is no less than $n.$
[i]Proof.[/i] Of course, note that no vertex can become independent by such operations, so at any point in time [color=#f00]we have at least $n$ edges, the number of edges in a tree[/color]...
[/quote]
The number of edges in a tree with $n$ vertices is $n-1$. :)[/quote]

Oh sorry seems I wrote stuff half-mindedly. Will edit soon.

[quote=Particle][hide="Different Proof"]Suppose $a(n)$ denotes the least number of edges after the described operation on an $n$ graph. Inductively I'll prove $a(n)=n$. For $n=4$, let $ABCD$ be a complete graph. Remove edges $AB$ and $AC$. The resulting graph will have no cycle. So $a(4)\leq 4$. Now we'll prove $a(4)=4$. In graph $ABCD$, there are three 4-cycles, namely, $ABCD,ACBD$ and $ADBC$. Each pair of them shares exactly two common edges. So eliminating an edge would remove two 4-cycles from the graph. But the third one will remain intact. So to end up with a graph with no 4-cycle, we must remove two edges. And after removing two edges, there will be no 4-cycle. Hence there will be $\binom 4 2 -2=4$ edges at the last.  So the base case is proved.

Let $v_1v_2...v_n$ be the complete $n$ graph. Firstly I'll show $a(n)\ge n$. Suppose this is not true. i.e. $a(n)\leq n-1$.
Note that $v_2...v_n$ was a complete $n-1$ graph. After eliminating an edge from every 4-cycle of it, there will be exactly $n-1$ edges left. (inductive hypothesis) So $a(n)\ge n-1$. and if $a(n)=n-1$, it means $v_1$ will have degree $0$ after the described operation. But that's impossible because to be in a cycle, a vertex must have degree of at least 2.(one edge to come, one to go) Hence when $v_1$ will have degree 1, it will no longer belong to a cycle, let alone a 4-cycle. So after the described operation on an $n$ graph, total number of edges  must have to be at least $n-1+1=n$. thus $a(n)\ge n$. Now we'll give an example to show $a(n)=n$ is possible. For $n=4$ we did this earlier. Now we recursively remove an edge from every 4-cycle of graph $v_1v_2...v_n$ like this: in sub-graph $v_2...v_n$, we do this exactly same as we did in the complete graph of $n-1$ vertexes. There will be $n-1$ edges remaining. And if $v_1$ is in a 4-cycle, we simply remove an edge associated with vertex $v_1$. Thus out of $n$ edges associated with $v_1$, $n-1$ will be removed. So after this operation only $n-1+1=n$ edges will be left in the graph $v_1...v_n$. So $a(n)=n$[/hide][/quote]

That was almost exactly my proof :D

edit: except my approach was to show [hide]$a(n)>a(n-1)$ and then conclude the same result[/hide]

First of all, we see that after each step, the graph remains connected. Therefore connectedness of the graph is an invariant.
Thus, #min. edges $\ge n-1$.
For #min. edges = n-1, we get a spanning tree.
We show that one cannot obtain a spanning at the end. To show this, we assume to the contrary that it's possible to get a spanning tree at the end. Thus, it must be possible to "reconstruct" $K_n$.
Before arriving at the contradiction, we give definitions.

For any vertex $A$, consider its adjacent vertex $P$. Now, consider $P$'s adjacent vertex's adjacent vertex (say $Q$)
Call the above operation $T$
We call a vertex $L$ an 'alternative vertex' of $A$ if $L$ is obtained after applying $T$ on $A$ finitely many times.
Define $S:=\{P\mid P~~\text{is an alternative vertex of } A\}\cup\{A\}$ as the 'alternative set containing A'
If $G$ is the spanning tree obtained at the end, then let $G=(V,E)$. Define $S':=E/S$
Clearly $S,S'$ are disjoint.
During reconstruction, we connect $A$ to any $P\in S$. Continuing this, we see that this $A$ is connected to every element of $S$ only.
But, $A$ cannot be connected to any vertex in $S'$. Thus, it is impossible to reconstruct $K_n$ and so it's not possible get a spanning tree at the end.

Now we show that #min. edges = $n$ is possible.
We first note that if $A$ was connected to any element in $S'$, it would be connected to all vertices in $S'$ due to our reconstruction (proof by induction).
Thus, if we had $n$ edges left at the end, we could use a "free edge" to join $A$ to an element in $S'$, and thus $A$ would be connected to all the other vertices and we are done. $\blacksquare$

(Small note: While defining $S$, we must not consider any "loops" i.e. selection of elements of $S$ must be done by applying $T$ in a fixed "direction")

Interestingly, the above reconstruction gives a possible generalization:
Replace 4-cycle by a t-cycle (t>4), and let $n\ge t$ then #min edges at end =$n+t-4$

[hide=Solution][quote=ISL 2004 C3]The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer ${n\ge 4}$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on $n$ vertices (where each pair of vertices are joined by an edge).

[i]Proposed by Norman Do, Australia[/i][/quote]
[b][color=#000]Solution:[/color][/b] Observe that after each operation, the graph remains connected. Moreover, we cannot have less than $n-1$ edges, 'coz that means we would make the graph disconnected. Suppose if $n-1$ edges is attainable. It clearly must be possible to reconstruct $K_n$ from the tree adding each edge to form $4-$cycle at each step.

Since, there are no cycles in a tree, the last cycle that we break is of length $4$. Consider the last odd cycle that we break. Clearly, it must have an edge common with a $4-$cycle. The common edge is the one that we delete to break the $4-$cycle, which also breaks the last odd cycle. But, notice that deleting the common edge between the last odd cycle and the cycle with length $4$ creates another cycle of odd length. This contradicts the fact of existence of last odd cycle. Therefore, having $n-1$ edges in the end is a contradiction!

Showing $n$ is achieved is fairly easy. Label the vertices $X_1,X_2, \ldots X_n$. Remove, edges from cycles $X_1X_2X_iX_j$, $X_1X_2X_nX_i$, $X_1X_2X_iX_n$ such that, only $X_1X_i$ and $X_2X_n$ is left $\qquad \blacksquare$ [/hide]

Nice problem! Here's my solution: The crux of the problem is the following claim:-

[b]CLAIM[/b] After each operation, the graph
[list]
[*] remains connected, and
[*] always has an odd cycle.
[/list]

[u][i]Proof of Claim[/i][/u] First we prove connectivity. FTSOC suppose after some operation the graph becomes disconnected. Then, before this move, the graph must be present in the form of two partitions $G_1$ and $G_2$, with exactly one edge $\{uv\}$ between these parts, where $u \in G_1$ and $v \in G_2$. But, in order to delete the edge $\{uv\}$, it must be part of a $4$-cycle. Since this $4$-cycle must return to $G_1$, so it requires atleast two edges between $G_1$ and $G_2$, a contradiction! So our graph remains connected.

For the second part, consider the operation when an edge from a $(2k+1)$-cycle $C_1$ is deleted. This edge must also be a part of some $4$-cycle $C_2$. But then $C_1 \cup (C_2-C_1)$ is another odd cycle. So the graph always has atleast one odd cycle.
----------

Return to the problem at hand. Our claim directly gives that the final graph must have at least $n$ vertices. Now, we show that $n$ is always achievable. Call a graph $G$ on $n$ vertices [i]good[/i] if it is of the following form-
[list]
[*] It consists of a triangle with vertices $a,b,c$.
$\text{ }$
[*] The remaining $\left \lfloor \frac{n-3}{2} \right \rfloor$ vertices, namely $u_1,u_2, \dots,u_{\left \lfloor \frac{n-3}{2} \right \rfloor}$ are joined to $a$.
$\text{ }$
[*] The remaining $\left \lceil \frac{n-3}{2} \right \rceil$ vertices, namely $v_1,v_2, \dots,v_{\left \lceil \frac{n-3}{2} \right \rceil}$ are joined to $b$.
[/list]

It's easy to see that such a graph has $n$ edges. We will show that, starting from $K_n$, we can always reach a good graph after finitely many operations. We proceed by induction on $n \geq 4$, with the result being easily seen to be true when $n=4$. Now suppose the result is true for some $n$. Consider $K_{n+1}$, and apply the inductive hypothesis to get to a graph consisting of a good graph $G$ on $n$ vertices, with all of the $n$ vertices joined to another vertex $w$. Then, we can delete $\{wu_i\}$ for all $1 \leq i \leq \left \lfloor \frac{n-3}{2} \right \rfloor$, since it is a part of the cycle $\{w,u_i,a,b\}$. By a similar argument, we can delete vertices of the form $\{wv_j\}$ for $1 \leq j \leq \left \lceil \frac{n-3}{2} \right \rceil$. Finally, delete $\{wb\}$ and $\{wc\}$, which we can do, as $wacb$ forms a $K_4$. Thus, we are left with $$(n+n)-\left(\left \lfloor \frac{n-3}{2} \right \rfloor+\left \lceil \frac{n-3}{2} \right \rceil+2 \right)=n+1$$
edges. Then it's easy to see that this is also a good graph on $n+1$ vertices, completing the inductive step. $\blacksquare$

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

The answer is $n$. As the case $n=4$ is easily done by hand, we will assume $n \ge 5$.
To show that at least $n$ edges always remain, note that [list] 	[*]The operation preserves connectedness of the graph; 	[*]The operation preserves the fact 	that the graph is [i]not[/i] bipartite. [/list] This implies the graph will always have $n$ edges leftover (since a connected graph always has at least $n-1$ edges, but with equality only when it is a tree, and trees are necessarily bipartite).
Conversely, for any $n \ge 5$ one can reach the graph consisting of a $K_5$ plus a path of length $n-5$ hanging off one vertex. Then one can prune the $K_5$ down to $C_5$ to achieve the desired construction.
[asy] 	draw(dir(0)--dir(72)--dir(144)--dir(216)--dir(288)--cycle, red); 	draw(dir(0)--dir(144)--dir(288)--dir(72)--dir(216)--cycle, lightblue); 	draw(dir(0)--2*dir(0), red); 	draw(2*dir(0)--3*dir(0), red); 	draw(3*dir(0)--4*dir(0), red); 	dotfactor *= 1.5; 	pen vtxpen = grey; 	dot(dir(0), vtxpen); 	dot(dir(72), vtxpen); 	dot(dir(144), vtxpen); 	dot(dir(216), vtxpen); 	dot(dir(288), vtxpen); 	dot(2*dir(0), vtxpen); 	dot(3*dir(0), vtxpen); 	dot(4*dir(0), vtxpen); [/asy]

[quote=oty]@v_Enhance can you kindly provide the link of the twitch stream ? thank you in advance[/quote]

The Twitch stream is [url]twitch.tv/vEnhance[/url]. You can find links to past broadcasts and schedule at [url]https://web.evanchen.cc/videos.html[/url].

The answer is $n$. We first prove the bound, then provide a construction. Let $G_n$ be the final graph.

[color=#00f][b]Claim:[/color][/b]  $G_n$ is connected.
[color=#00f][i]Proof:[/i][/color]  Suppose the graph disconnected at some point. The step just before that, there must have been two sets of vertices that were disjoint save for one edge. But it is impossible to delete this edge, since it cannot be a member of any cycle, contradiction. (Alternatively, simply note that the operation doesn't change the contentedness of the graph.)  $\blacksquare$

[color=#00f][b]Claim:[/color][/b]  $G_n$ is not a tree.
[color=#00f][i]Proof:[/i][/color]  Since we know $G_n$ is connected, it suffices to show that there is always an odd cycle. Simply note that the operation does not decrease the number of odd cycles; if an edge existed which was deleted and was part of an odd cycle, that odd cycle is now just a new odd cycle that is larger by 2 edges.  $\blacksquare$

The second claim proves that $|G_n| \not = n-1$, and since the graph is connected, we must have $|G_n|\ge n$, proving the bound.

Now we construct. For $n=4$, it is easy to see. The construction is inductive. Suppose we have constructed it for $n$, call the graph $G_n$. Start with $K_n$, and add a universal vertex $u$. Select two vertices $v_1,v_2$ in the $K_n$ which have some common neighbor $v_3$. Now, for any vertex $X\not = v_1,v_2$ in the $K_n$, consider the 4-cycle $uXv_1v_2$. Then delete edge $uX$. Repeat for all such $X$. So we only have $uv_1,uv_2$ coming out of $u$. Now, use the cycle $uv_1v_2v_3$ to delete $uv_2$. This leaves only the edge $uv_1$ from $u$. By induction we can end with $G_n$ having $n$ edges (WLOG it contains $v_1$). Hence we have added one edge, so we have made a valid $G_{n+1}$, completing the induction.

[hide=Remarks]The connected part reduces the number of edges to at least $n-1$. Then, to prove we cannot finish in $n-1$, we have to find some way to eliminate trees; the odd cycle is a logical way to do it. Construction was also a hard part. [/hide]

We claim the answer is $n$ and we proceed by induction. The proof for our base case $n=4$ can be done by hand.

Now we induct. The crucial observation is that each vertex must have at least one edge passing through it, and that if a vertex has degree one it can be ignored, and this is true since a vertex with degree one cannot be part of a cycle. Now consider $K_n,$ and note that if we are to only focus on $n$ of the $n+1$ points and delete as many edges as possible that it must have at least $n$ edges. But note that the last vertex cannot have degree $0$, so the number of edges is at least $n+1.$

Now we construct in an inductive manner as well. We have already proved this works for $n=4$ before. Note that $K_{n+1}$ is isomorphic to a regular $n+1$ gon-with all of its diagonals drawn, and call the points $P,P_1,P_2,\ldots,P_{n}.$ Now delete the edges from $P_3$ to $P_{n-1},$ noting that this is always legal as the cycle $PP_1P_2P_k$ exists for $3\leq k\leq n-1.$ Now erase $P_2$ as the cycle $PP_2P_3P_n$ exists, and now erase $P_n$ as the cycle $PP_1P_2P_n$ exists. Now we ignore $P$ and note that the $K_n$ graph $P_1P_2\ldots P_n$ has a construction of $n,$ so the total is $n+1$ as desired.

We claim the answer is $n$, which we will prove by induction. The base case of $n = 4$ is obvious.

Now, focus in on a vertex $v$. It's obvious that at the end, its degree will be at least $1$. By inductive hypothesis the other $n$ vertices have at least $n$ edges left, thus the best we can do is $n + 1$.

To construct, isolate vertex $v$ and then vertices $v_1, v_2, \cdots, v_n$. First consider cycle $vv_1v_2v_3v$; delete edge $vv_1$. Then, consider cycle $vv_2v_3v_4v$, and go down the line. Our final one is $vv_{n - 2}v_{n - 1}v_nv$; here, after deleting $vv_{n - 2}$, we can consider $vv_{n - 1}v_{n - 2}v_nv$ in order to kill the $vv_{n - 1}$ edge. Thus we are done.

The answer is $\boxed{n}.$\\\\ $\emph{Construction: }$ Let $v$ be a vertex of the graph $G$ at some point in time. Suppose that 1) $G-v$ is complete and 2) there exist two edges adjacent to $v$. Then, it is easy to see that we may remove one of the edges adjacent to $v.$\\\\ Starting with the complete graph and applying the above result repeatedly, we can remove all but one of the edges adjacent to any given vertex. Now we can obtain $n-1+1=n$ edges by induction.\\\\ $\emph{Proof: }$ Let $G'$ be the graph remaining when no further operations can be performed. Note that the operation preserves connectedness, so $G'$ is connected. Moreover, note that the operation preserves the property "has a cycle with length not equal to $4$, so $G'$ is not a tree. These conditions are enough to imply that $G'$ has at least $n$ edges.

My answer is $n$.
The key idea is to find the example, by induction we can get a path $v_1v_2\dots v_n$ such that $v_iv_{i+1}$ it's an edge and also $v_1v_3$ with this configuration we have $n$ edges. The inductive step is first separate $K_{n+1}$ in $K_{n+1} - v_{n+1}$ this is a complete graph and with the induction we get the path and the extra edge, but also $v_{n+1}v_i$ is an edge. We take in descending order the cycles $v_{n+1}v_iv_{i-1}v_{i-2}$ and eliminate $v_{n+1}v_i$ with $i= n,n-1,\dots,4$. With this algorithm we eliminate almost every edge, then we take the cycle  $v_1v_3v_2v_{n+1}$ and eliminate $v_1v_3$ after this we take the cycle $v_1v_2v_3v_{n+1}$ and we eliminate $v_2v_{n+1}$ this completes the induction.

To prove that this is the minimum, we can check that always the operation preserves connectedness of the graph and always exists an odd cycle this can be checked manually, so the graph it's connected but is not a tree this implies that the number of edges is at least $n$.

We claim the answer is $n$. We will consider the reverse of the operation: we are looking for graphs $G$ that can be transformed into $K_n$ by adding edges one at a time, each of which creates at least one new $4$-cycle.

For the construction, arbitrarily number the vertices $v_1, v_2, \dots, v_n$. Connect $v_1$ to all $n-1$ other vertices, and then connect $v_2$ to $v_3$. This graph has $n$ edges, and we claim it is possible to to reach $K_n$ using the reverse operation. Indeed, we can first add in $v_3v_4, v_4v_5, \dots , v_nv_2$ in that order. Then we can add in any edge $v_iv_j$ to create the $4$-cycle $v_1v_iv_jv_{j+1}v_1$ (where we define $v_{n+1} = v_2$).

For the bound, clearly $G$ must be connected, so it remains to show $G$ cannot be a tree. We claim bipartite graphs remain bipartite after reverse operations, which finishes the problem as trees are bipartite but complete graphs are not. Indeed, consider a bipartite graph $H$ with vertices $u$ and $v$ in the same vertex set. If connecting $u$ and $v$ created a $4$-cycle then there would be a path of length $3$ between $u$ and $v$, absurd so we are done.

Let $G_n$ be the graph formed in the end upon which no more operation can be performed. Firstly note that the operation does not disconnect $K_n$ hence $G_n$ is connected.
[hide=bound]
[b]Claim: [/b]$G_n$ always has an odd cycle.
[i]Proof: [/i]Assume not, consider the stage when there is [b]only one[/b] odd cycle (WLOG) $V_1 \to V_2 \to \cdots V_k \to V_1$ left, note that there isn't any edge between non adjacent vertices of this cycle because otherwise there would be atleast another odd cycle, so WLOG the operation needs to be performed on $V_1, V_2$ thus they would have been a part of another 4-cycle consisting of two other vertices and deleting the edge b/w $V_1,V_2$ would only create a longer odd cycle and not destroy the previous cycle which is a contradiction.
Since $G_n$ is a connected graph and it isn't a tree (because there is a cycle) so there are atleast $n$ edges in $G_n$.[/hide]
[hide=Construction]
Induct, for $n=4$ note that you can be left with a vertex, say, $V_1$ which is connected to all other vertices and two other vertices, say, $V_2,V_3$ such that $V_1V_2V_3$ is a triangle, now generalize this construction. For the $n^{\text{th}}$ case assume that the triangle $V_1V_2V_n$ exists and $V_1$ is connected to all other vertices (this graph clearly has $n$ edges). Now consider $K_{n+1}$, ignore the vertex $V_{n+1}$ and end up with a structure as in the $n^{\text{th}}$ case in the graph $K_{n+1} - \{V_{n+1}\}$.
Then consider the cycle $V_{n+1} \to V_i \to V_{i+1} \to V_1 \to V_{n+1}$ and delete the edge joining $V_i, V_{n+1}$ for $2 \le i \le n-1$ and in order to delete the edge joining $V_{n+1} , V_n$ consider the cycle $V_{n+1} \to V_1 \to V_2 \to V_n \to V_{n+1}$ clearly we have added only an extra edge joining $V_{n+1},V_1$ so $|G_{n+1}| = |G_n| + 1$ which completes the induction.

Very cool problem. In this solution, for vertices $v_1,v_2$, $v_1-v_2$ means that an edge exists between the two vertices

The answer is just $n$. We can verify this explicitly for $n=4$, and as a construction for arbitrary $n$, delete all but one edge connected to one vertex, and henceforth ignore that vertex, reducing the answer to that of $n-1$ vertices plus one edge, which works by induction.
Now it suffices to show that we can't end up with $n-1$ edges or less. Reverse the problem, so we start with some $k \leq n-1$ edges, and we are allowed to pick some 4 vertices $v_1-v_2-v_3-v_4$ and connect $v_1$ to $v_4$. Clearly this operation doesn't change the connectedness of the graph, so we must start with a connected graph, i.e. $k=n-1$. Then it doesn't contain an odd cycle, so it is bipartite. It is easy to check that adding an edge in the way described preserves the bipartiteness of the graph, as when connecting $v_a$ to $v_d$ with $v_a-v_b-v_c-v_d$, $v_a$ is in the opposite subgraph of $v_b$ is in the opposite subgraph of $v_c$ is in the opposite subgraph of $v_d$ :P
Then we would need the complete graph on $n$ vertices to be bipartite as well if $k=n-1$ worked, but this is absurd: contradiction. Therefore we must start with at least $n$ edges, done. $\blacksquare$

[hide=wrong]
...i.e. $k=n-1$, which is just a path, WLOG $v_1-v_2-\cdots-v_n$. The key claim is the following:

[b][color=#00f]Claim:[/color][/b] If we ever have $v_i-v_j$, then $i,j$ have different parity.
[color=#00f]Proof:[/color] Clearly this is true when we haven't done anything yet. Now suppose the claim holds, and we connect $v_a$ to $v_d$ since $v_a-v_b-v_c-v_d$. By hypothesis, $a$ is the opposite parity of $b$ is the opposite parity of $c$ is the opposite parity of $d$ (yes, I only wrote that because it's fun to say), so $a$ and $d$ have opposite parity, which preserves the truth of the claim.

To finish, note that the claim implies that we can't ever have $v_1-v_3$, so we cannot reach a complete graph: contradiction. As such it follows that we need at least $n$ edges, done. $\blacksquare$

[b]Remark:[/b] All the claim is really saying is that adding vertices preserves the bipartite-ness of the graph, but I'm bad at thinking of graphs this way (just because "bipartite" in my head gets visualized as the classic image of having two rows of vertices with edges between them) so the numbering/parity idea came more naturally for some reason

We claim the answer is $n$.

We claim that after any number of moves, any two vertices must have an even-length walk between them. Let $A$ and $B$ be two vertices with a walk between them of length $e$, with $e$ even. Suppose one of the edges in that walk is removed in a move. Then, it must be part of a $C_4$. So, in the walk, replace that edge with the other three edges of the $C_4$. Then, there is a walk between $A$ and $B$ of length $e+2$, which is still even. Every pair of vertices has an even length walk between them at the beginning, so they still will after any number of moves.

We claim that the lowest number of edges a graph on $n$ vertices with this property can have is $n$. Note that the graph must be connected. Assume towards a contradiction that it has fewer than $n$ edges. Since the graph is connected and has fewer than $n$ edges, it must be a tree. This is because a connected graph has at least $n-1$ edges, and if the graph has a cycle, you can remove an edge and it will still be connected, so a graph with a cycle has at least $n$ edges.

However, in a tree, two adjacent vertices do not have an even-length walk between them, a contradiction. Thus, the graph has at least $n$ edges.

We claim that there is a graph with $n$ edges that can be obtained from the complete graph after a sequence of moves. Rather than showing how to go from the complete graph to a graph on $n$ edges, we will start with a graph on $n$ edges and show that it is possible to get to the complete graph by adding edges between vertices with a length-3 path between them. This is equivalent, because by playing the moves in reverse, you can get from a complete graph to the graph with $n$ edges.

Lemma: If two vertices have an odd-length path between them, by doing reverse moves, it is possible to make them adjacent.
Proof: Assume $A$ and $B$ have a path $P$ between them of length $o$, where $o$ is odd. Assume $o>1$. Then, let $X$ be the vertex of $P$ such that the path between $A$ and $X$ on $P$ has length $3$. Construct edge $AX$ if it doesn't already exist. Then, the path with edge $AX$ and the part of $P$ between $X$ and $B$ (if such a part exists) has length $o-2$. So, by doing this process repeatedly, it is possible to make a path between $A$ and $B$ of length $1$.

Consider the case where $n$ is odd. Start with a $C_n$. Let $A$ and $B$ be two different vertices. Since $C_n$ has odd length, one of the paths between $A$ and $B$ has odd length. So, by the lemma, it is possible to make $A$ and $B$ adjacent through a sequence of reverse moves.

Consider the case where $n$ is even. Let the starting graph have a $C_{n-1}$ and an edge between one of the vertices in the $C_{n-1}$ the vertex not in it. Let $X$ be the vertex not in the $C_{n-1}$, and let $O$ be the vertex it is adjacent to. Using the logic from the $n$ odd case, it is possible to turn the cycle into a $K_{n-1}$. We claim it is also possible to make $X$ be adjacent to any other vertex. Let $A\neq O$ be on the $C_{n-1}$. Then, let $P$ be an even length path between $A$ and $O$. This is possible for any $A$ because the cycle has odd length. Then, the path from $X$ to $A$ including $OX$ and $P$ has odd length. So, by the lemma, it is possible to make $A$ and $X$ adjacent.

As previously mentioned, by playing these moves in reverse, you can go from the complete graph to a graph with $n$ edges. Therefore, $n$ edges is both optimal and achievable.

[b][color=#f00]Claim[/color][/b]: The graph must always be bipartite
[b]Pf[/b]: Consider the limiting edge. This can only be removed if there is another edge in the other component, contradiction. $\blacksquare$

This means that there are at least $n$ edges, as else we would have a bipartite spanning tree (the graph must be conected at all times).

The construction is straighforward, as we can trim a $K_{n+1}$ to a $K_n$ and a single vertex with degree $1$ and induct down for $n\geq 4$. The base case $n=4$ holds. $\square$

We will solve the problem for all $n\geq3$. We claim that there are at least $n$ edges in the resulting graph. After each operation, the graph is still connected, so the resulting graph must be connected. Now, we claim that it is not bipartite. Before the operation, there exists an odd cycle $A_1$, $A_2$, $\ldots$, $A_k$, $A_1$. If the operation removes the odd cycle, then the cycle of length $4$ must share an edge with this cycle. Assume without loss of generality it is $A_1$, $A_2$, $B$, $C$, $A_1$. Then, deleting $A_1A_2$ makes $A_2$, $A_3$, $\ldots$, $A_k$, $A_1$, $C$, $B$, $A_2$ an odd cycle, so it cannot be bipartite. Therefore, the resulting graph is connected and it is not a tree, so it must have at least $n$ edges.

Now, we will show that it is possible to get exactly $n$ edges. We will show this by induction on $n$.

Base Case: $n=3$
Then, there are three edges in the original graph.

Inductive Step:
Pick a vertex $A$, and let the other vertices be $A_1$, $A_2$, $\ldots$, $A_{n-1}$. Then, consider the cycle $A$, $A_i$, $A_2$, $A_1$, $A$. Delete edge $AA_i$ for $3\leq i\leq n-1$, then consider cycle $A$, $A_2$, $A_3$, $A_1$, $A$, and delete $AA_2$. By the inductive hypothesis, $A_1$, $A_2$, $\ldots$, $A_{n-1}$ can be turned into a graph with $n-1$ vertices. Therefore, since there is one edge adjacent to $A$, this means that that the resulting graph has exactly $n$ vertices.

Therefore, the least number of edges is $\boxed n$.

I had the solution written from a few months ago, but I realized I never posted it here! So here you go:

The answer is $n.$

We claim that the operation cannot leave the graph disconnected. When the graph first becomes disconnected, then draw in the last deleted edge $e.$ This is edge was between two points of the same connected component, then adding this edge the graph is still disconnected. Let its endpoints be $v,v'$ where $v,v'$ are from different connected components. Note that $v,v'$ are in a cycle, so there is a path from $v$ to $v'$ not containing $e.$ Thus, removing $e,$ there still exists a path from $v$ to $v',$ contradiction.

We claim that the operation cannot remove every odd cycle. Consider the time the graph first becomes bipartite. Then draw in the last deleted edge $e$ which must be within one component of the graph, between say $v,v'$. No other points of this component is connected, and similarly of the other component. Suppose $v,v',w,w'$ is a cycle, then $w,w'$ must be of the other component and connected... contradiction.

Now, from those two claims we have the final graph can't be disconnected and it can't be a tree. Thus, it has at least $n$ vertices. Thus, it remains to show that there is always a way to reduce this down to just $n$ vertices.

When $n=4$ obviously it works. Suppose it works for $n=k$ then we claim it works for $n=k+1.$ Then pick an arbitrary vertex and all the edges protruding from that vertex. Then, as long as there are at least one such vertex remaining, we can form a 4-cycle. Thus, we leave one such edge, and for the remaining $K_k$ we make it so only $k$ edges remain, and the conclusion follows.

The answer is $\boxed{n}$.

[b]Construction.[/b] This is by induction. For $n=4$, disconnect $AB$ because of $ABCD$ then $AC$ because of $ACBD$. For $n>4$, choose an arbitrary vertex $P$ and disconnect it from every vertex but one. Now use the inductive hypothesis on the graph besides $P$, and we will have $n-1+1=n$ edges. $\blacksquare$

[b]Impossibility.[/b] Note that these operations have to keep the graph connected, so it suffices to prove that the resulting graph is not a tree. Assume FTSOC that it is. Then we can color the vertices of the tree red or blue such that there are no same-colored connections(trees are bipartite). Now I claim that the last same-colored connection(this obviously must exist) should not have been possible to remove. This is because the $4$-cycle, say $ABCD$ with $A$ and $B$ red, must have had $C$ blue and $D$ red, contradiction because then $AD$ is also same-colored. $\blacksquare$

[hide=Solution]
The answer is $\boxed{n}$.

First, we will provide a construction. We will do this inductively. For $n = 4$, we can do the following. Label the vertices $1, 2, 3, 4$. Then, $1234$ is a $4$-cycle, so we can remove edge $14$ from the graph. $1243$ is a $4$-cycle in the reduced graph, so we can remove edge $34$ from the graph (you lost the game), and there are only $4$ edges remaining. Now, take some $n = r \geq 5$, and assume we can reduce $K_n$ to a graph on $n$ edges by this process for $n = r-1$. We will show that we can reduce $K_r$ to a graph on $r$ edges.

Label the vertices of $K_r$ as $1, 2, \cdots, r$. Then, $(r)(1)(2)(r-1)$ is a $4$-cycle, so we can remove the edge $(r)(r-1)$ from the graph. $(r)(1)(2)(r-2)$ is a $4$-cycle in the reduced graph, so we can remove the edge $(r)(r-2)$. Similarly, we can apply this logic for $(r)(1)(2)(r-3)$, $(r)(1)(2)(r-4)$, $\cdots$, $(r)(1)(2)(3)$, and by that point we have removed the edges from the vertex labeled $r$ to the vertices labeled $3, 4, \cdots, r-1$. Note that $(r)(1)(3)(2)$ is still a $4$-cycle in the reduced graph, so we can remove the edge $(r)(2)$. Thus, we have removed the edges from the vertex labeled $r$ to every other vertex besides the vertex labeled $1$. Now, this graph is just a $K_{r-1}$ plus an edge from the vertex labeled $r$ to the vertex labeled $1$. By the inductive hypothesis, we can repeatedly remove edges from $4$-cycles in the $K_{r-1}$ to get a graph with $r-1$ edges. Thus, after those iterations, the actual graph has $r$ edges because of the extra edge from the vertex labeled $r$ to the vertex labeled $1$, as desired, so we can reduce $K_r$ to a graph on $r$ edges, and our inductive hypothesis is complete.

Now, we will prove that for all $n\geq 4$, you cannot reduce $K_n$ to a graph with less than $n$ edges from this process. Note that the graph will always stay connected after each move, since if a graph $H$ is connected, then removing one edge from a $4$-cycle of $H$ will still keep it connected, since you can still get from one side of the removed edge to the other via the other side of the cycle. Thus, if $G$ is the resulting graph after all of the operations, then $G$ is connected. Thus, if $G'$ is a spanning tree of $G$, then the number of edges of $G$ is at least the number of edges of $G'$, i.e. $n-1$. Thus, we have that $G$ has at least $n-1$ edges.

It remains to show that $G$ cannot have $n-1$ edges. To do this, we will show that throughout this process, the graphs are all non-bipartite.

Let $A$ be a graph achieved in the midst of this process, and assume that $A$ has a $4$-cycle and that $A$ is non-bipartite. Then, we will show that the graph determined by removing an edge of the $4$-cycle from $A$ is still non-bipartite. Since $A$ is non-bipartite, it has an odd cycle $C$. If the removed edge is not an edge of $C$, then $C$ is still an odd cycle in the reduced graph, so the reduced graph is non-bipartite as well, as desired. Else, the removed edge is an edge of $C$. Then, let $c_1, c_2, \cdots, c_{2r+1}$ be the vertices of $C$, for some $r\geq 1$ and suppose the removed edge was $c_1c_{2r+1}$. Let $v$ and $w$ be the other edges of the $4$-cycle from which $c_1c_{2r+1}$ was removed, so that $c_1vwc_{2r+1}$ is a $4$-cycle. Then, note that $c_1vwc_{2r+1}c_{2r}c_{2r-1}\cdots c_2c_1$ is a walk of odd length (it has length $2r+3$) from $c_1$ back to itself. Now, if the reduced graph was bipartite, then there would be no walk of odd length of a vertex back to itself, since if we take a supposed $2$-coloring of the reduced graph, then on each edge in the walk, the walk goes from a vertex of one color to a vertex of another color on each edge, so after an odd number of edges, you must arrive at a vertex of a different color, and therefore you land at a different vertex. Thus, the reduced graph is non-bipartite, as desired.

Thus, it follows that $G$ is non-bipartite, since $K_n$ is non-bipartite ($K_n$ has at least one triangle), and if the reduction is $K_n \rightarrow G_k \rightarrow G_{k-1} \rightarrow \cdots \rightarrow G_1 \rightarrow G$, then by our lemma, since $K_n$ is non-bipartite, $G_k$ must be non-bipartite, so then $G_{k-1}$ must be non-bipartite, etc., so $G_1$ must be non-bipartite and so $G$ must be non-bipartite. Now, if $G$ had $n-1$ edges, then it would have the same number of edges as a spanning tree $G'$ of it, so we must have that $G$ is its own spanning tree, since $G'\subseteq G$ and they have the same number of edges. Thus, $G$ is a tree, so it is acyclic. This would mean that $G$ has no odd cycles, so $G$ would be bipartite. However, we just proved that $G$ was non-bipartite, a contradiction. Thus, $G$ has at least $n-1$ edges, and $G$ cannot have exactly $n-1$ edges, so $G$ must have at least $n$ edges, as desired.

Thus, we have shown that there exists such a $G$ with $|E(G)| = n$ and we proved that for all such $G$, $|E(G)| \geq n$, so we've proven that $n$ is indeed the desired minimum, so we're done. $\blacksquare$

Answer is $n$.

[color=#00f][b]Bound:[/b][/color] It suffices to show that this graph $G$ remains non-bipartite and connected, as all trees are bipartite.

To prove the first claim, note that the last edge removed to make $G$ bipartite cannot be part of an even-length cycle by definition, hence $G$ cannot be made bipartite. On the other hand, as every edge removed is part of a cycle, $G$ remains connected.

[color=#00f][b]Construction:[/b][/color] Label the vertices $v_1, v_2, \dots, v_n$. For $4 \leq i \leq n$, reverse-inductively remove all edges connecting $v_i$ to $v_j$ for $1 \leq j \leq i-2$ by considering 4-cycles formed in the complete graph $K_{i-1}$. This leaves the graph as a path connected to a triangle, which evidently has $n$ edges.

oo nice problem
[hide = solution]
We'll show that the answer for a $K_n$ is $n$. First observe that the graph is always connected and never become bipartite, since the original graph is not bipartite and $4$ is even. We are going to induct on $n$ to prove that we can reduce $K_n$ to a path of length $n-3$ and a triangle connected at a vertex:
[img]https://i.imgur.com/vpBs4nn.png[/img]
For $n = 4$, we simply continue removing an arbitrary edge while there are edges we can remove. We end up obtaining a triangle with a stray edge, proving the base case. Now for the inductive step. Suppose we've to show it for $K_{n+1}$. First label one of the vertices $n+1$ and consider the $K_n$ obtained after removing $n+1$. Using the inductive hypotheses on the $K_n$, we obtain the following graph:
[img]https://i.imgur.com/QwoftOh.png[/img]

Now for each $i = 1$ to $n-3$ (in that order) we delete the edge joining vertices $n+1$ and $i$ because this edge is part of the cycle $n+1 \to i \to i+1 \to i+2 \to n+1$. After these deletions, we have a path of length $n-3$ connected to a $K_4$ at the vertex $n-2$. Reducing the $K_4$ to a triangle with a stray edge at $n-2$, the induction is complete.
[/hide]

Let $G$ be our complete graph. It's obvious that if we apply the operation in $G$, then new graph is still connected. Now assume $G$ is bipartite and we apply operation on $G$ once. Let $H$ be out new graph and assume $H$ is bipartite. Let $(v_{1},v_{2},v_{3},v_{4})$ be a cycle that is chosen and assume we erased edge $(v_{1}, v_{2})$.
Let $P_{1}, P_{2}$ be independent sets of $H$. WLOG we can assume $v_{1}, v_{3} \in P_{1}$ and $v_{2}, v_{4} \in P_{2}$. Then $G = H \cup \{v_{1}v_{2}\}$ is bipartite too, a contradiction.

Therefore our graph is connected and not bipartite at any moment. Thus at the end it has at least $n$ edges. Now we're construct the order of operations. Let the vertices are $v_{1}, v_{2},\dots, v_{n}$. For $3 \leq i \leq j \leq n$, erase edge $\{v_{i}v_{j}\}$ from cycle $(v_{1}, v_{2}, v_{i}, v_{j})$. For $3 \leq i \leq n$, erase edge $\{v_{3}v_{i}\}$ from $(v_{1}, v_{2}, v_{3}, v_{i})$ and erase edge $\{v_{2}v_{i}\}$ from $(v_{1}, v_{2}, v_{i}, v_{3})$.
Therefore our graph has edges $\{v_{1}v_{2}, v_{1}v_{3},\dots, v_{1}v_{n}, v_{2}v_{3}\}$.

Consider reversing the process. Suppose you start with a graph G, and when there exists a path from a node X to a node Y of length 3, you complete the 4-length cycle by connecting X and Y. It can be shown by reversing the sequence of operations that this is equivalent to the original problem.
Now suppose you have a graph at the start which is disconnected. Whenever you try to connect vertices from two different connected components, there is no cycle, because to connect X and Y there must be at least some different path from X to Y already. So the connected components stay disconnected from each other, but at the end in the complete graph there is only one connected component, thus this is impossible.
Now I will prove that there must be a cycle in the original graph. In the complete graph at the end, there are at least 4 nodes, and since all vertices are connected to each other through edges, there exists three vertices forming a triangle. Without a cycle in the original graph, I will prove that it is impossible for such a triangle to form. Indeed, suppose we want to form the triangle ABC, and we already have the edges AB and AC, so we want the edge BC. For this to happen, we need a 3-length path from B to C, so we had to at some point have a 3-length path from B to C. Suppose that path is BXYC. So we have the 5-cycle ABXYC. If any of the edges in this cycle were created through the given process, completing a 4-cycle, then the other three edges in that 4-cycle must themselves have formed part of this big cycle at some point. Keep doing this until you go back to the starting graph, and it is deduced thusfore that there was always a cycle in the graph: this big cycle. So there must have been a cycle in the original graph.
Therefore since there is a cycle, the connected original graph cannot be a tree, so it has to have at least n edges. Indeed, there is a solution with n edges, which can be built up inductively. Here I go back to the problem statement, not the reverse process. Clearly for n=3, the triangle has 3 edges. Now assume that there is a solution for k vertices. If you consider a vertex A of a k+1 vertex graph, and at the start remove each edge from A leaving one behind, these moves are all legal because due to the fact that there is a path between any 2 vertices in the remaining graph, so clearly since n>3 there is a path of length 2 between any 2 vertices in the remaining graph so if we are removing the edge AX, and AY still exists, for any other C, AXCY is a valid 4-cycle which allows us to remove AX. So now there is only 1 edge coming from A. Now for the remaining graph it is possible to do it with k edges, so k+1 edges in total and the statement is proved by induction. The answer is there are at least n edges in the remaining cycle of the graph.


let $ n_{1}<n_{2}....<n_{2000}<10^{100}$ be positive intergers.prove that one can find two nonempty subsets A and B of {$ n_{1},n_{2}....n_{2000}$} such that lAl=lBl and the sum of elements of A is equal to the sum of elements of B,and the sum of squars of element of A is equal to the sum of squars of elements of B

[quote="drapt@"]let $ n_{1}< n_{2}.... < n_{2000}< 10^{100}$ be positive intergers.prove that one can find two nonempty subsets A and B of {$ n_{1},n_{2}....n_{2000}$} such that lAl=lBl and the sum of elements of A is equal to the sum of elements of B,and the sum of squars of element of A is equal to the sum of squars of elements of B[/quote]

$ A\equal{}B\equal{}\{n_{1}\}$  :wink:

So I supposed you are looking for $ A\neq B$ :lol:
Then consider the subsets containing exactly $ 1000$ elements. We have $ \frac{2000!}{1000!1000!}$ $ >\frac{\prod_{k\equal{}1}^{1000}2k\prod_{k\equal{}1}^{999}2k}{1000!1000!}$ $ \equal{}\frac{2^{1999}}{1000}$ such different subsets.

Since sums of squares are $ <1000*10^{200}$, we have at least $ \frac{2^{1999}}{10^{206}}>10^{393}$ distinct subsets with $ 1000$ elements whose sum of squares are identic.

And since sums of values are $ <1000*10^{100}$, we have, in these $ >10^{393}$ distinct subsets with $ 1000$ elements whose sum of squares are identic, at least $ \frac{10^{393}}{10^{103}}\equal{}10^{290}$ subsets having the same sum of values.

It remains to take two of them and to remove their intersection in order to find the required $ A$ and $ B$ .


By definition, $ r! \equal{} r(r \minus{} 1) \cdots 1$ and $ \binom{j}{k} \equal{} \frac {j!}{k!(j \minus{} k)!}$, where $ r,j,k$ are positive integers and $ k < j$. If $ \binom{n}{1}, \binom{n}{2}, \binom{n}{3}$ form an arithmetic progression with $ n > 3$, then $ n$ equals

$ \textbf{(A)}\ 5\qquad
\textbf{(B)}\ 7\qquad
\textbf{(C)}\ 9\qquad
\textbf{(D)}\ 11\qquad
\textbf{(E)}\ 12$

[hide]We can simplify each number in the sequence to

$n$, $\frac{n(n-1)}{2}$, $\frac{n(n-1)(n-2)}{6}$

Since this is an arithmatic sequence, $\frac{n(n-1)}{2}-n = \frac{n(n-1)(n-2)}{6}-\frac{n(n-1)}{2}$, and we can just solve for n from this equation to get $n=0$ or $n=2$ or $n=7$.  Since $n$ has to be greater than $3$, only $n=7$ works, so the answer is $b$[/hide]


Each two of $ n>2$ cities of the country are connected by one-way road, with the number of roads going into one specific town, as well as the number of roads going out of one specific town, should not be less than $ \lfloor \frac{n-2}{2}$.

Prove that
(a) it is possible to reach any town from any other towns using no more than three roads.
(b) it is possible to assign the roads in such a way that it is possible to reach any town from any other towns using no more than two roads.


limit
real analysis
calculus
calculus computations

Suppose $ f(x)\in C[0,\plus{}\infty)$ (it means that $ f(x)$ is continuous when $ x\geq0$), $ f(x)\geq 0$ such that for $ \forall x_1,x_2\geq0$, $ f(x_1\plus{}x_2)\leq f(x_1)\plus{}f(x_2)$.

Prove that:$ \lim_{x\to\plus{}\infty}{\frac{f(x)}{x}}\equal{}\inf_{x>0}{\frac{f(x)}{x}}$

In the proof of [b]Fekete lemma[/b] for sequences I don't understand the following step. Can someone clarify?
My question, in general, is the following:
If $a_n\ge 0$, then how is $\liminf_{n\to \infty}a_n=\inf_{i=1,2,\dots,k}\liminf_{j\to \infty}a_{jk+i}$ for all $k\ge 1$?
In the right hand side what are we essentially doing is that we divide the whole sequence into blocks of length $k$ and select one member from each block in order and find liminf and then we take the inf of these $k$ liminf's. Should this be equal to the actual liminf of the sequence?
I could only see that it's true for $k=1$.

Recall that $\liminf_{n\to\infty}a_{n}$ is the smallest subsequential limit of $a_n$. Thus each $\liminf$ on the right is $\ge \liminf_{n\to\infty}a_{n}$. On the other hand, take a subsequence of $a_n$ converging to $\liminf_{n\to\infty}a_{n}$. That subsequence must land in one of our blocks infinitely many times. That will give the other inequality.


Anyone familiar with the "international" language Esperanto? I found a book about it at the library and it seems so easy to pick up that I think I'll try to learn it. A surprisingly large number of people speak it!

The total worldwide number of speakers of Esperanto is less than the annual new number of speakers of English (or Mandarin) produced by children growing up in families that speak English (or Mandarin).

Here's more on Esperanto:

http://www.xibalba.demon.co.uk/jbr/ranto/

http://www.zompist.com/kitespo.html

http://www.christopherculver.com/en/writings/esperanto.php

http://www.rickharrison.com/language/bloated.html

http://www.steve.gb.com/rants/esperanto.html

http://www.homunculus.com/babel/aesperanto.html

[quote="ToBe"]What good is a language if only like a half a percent of the world speaks it? You can call english an international language too, just because its spoken internationally..[/quote]

Esperanto, unlike english, is extremely easy to master for anyone, not just speakers of latinate languages. The grammar resembles many oriental languages', actually. Furthermore, unlike English, Esperanto is not a national language; there are no native speakers (well, I shouldn't say none, but you get the idea). Thus, everyone is on an equal footing when speaking the language; it's at least a second language for all. It's an international language in that it allows people all over the world to communicate with each other without one party needing to "appease" the other by learning their native tongue.

Unfortunately, as good as a language is, its useless if 'internationally' you may not find a person who speaks it. You are better off finding another guy in a foreign country that speaks English, or whatever your native language is.

On the equal footing ---- so its better to have a language that everyone equally has trouble with?

no, in fact the idea is that it is so easy to learn that people won't have trouble with it at all.

they are on equal footing in that no one is conforming to anyone else; they are speaking a language that has equal meaning to both of them.

P.S. languages don't just go instantly from being between a few correspondents to hundreds of millions of speakers; it takes [i]time[/i]. In fact, by me studying Esperanto, I am helping the effort to spread the language.

so why spread a new language when the languages we have now are sufficient? Most people are bilingual anyway.

[quote="curl"]Esperanto, unlike english, is extremely easy to master for anyone, not just speakers of latinate languages.[/quote]

This is a demonstrably false statement, as backed up by the real-world observation that very few people succeed in learning Esperanto.

[quote="curl"]The grammar resembles many oriental languages', actually.[/quote]

Oh, really? Is there such a category as "oriental languages" in use among serious linguists? Regarding which oriental languages is this claim being made (asked the proficient speaker of Mandarin who has also learned some Hebrew, Cantonese, Taiwanese, Hakka, and Japanese)?

[quote="curl"]Furthermore, unlike English, Esperanto is not a national language; there are no native speakers (well, I shouldn't say none, but you get the idea). Thus, everyone is on an equal footing when speaking the language; it's at least a second language for all.[/quote]

It's an [i]advantage[/i] to have everyone spend long amounts of time learning a second language to communicate internationally when there are already languages with hundreds of millions of native speakers that are used daily as "interlanguges" in every country of the world? Why throw away truly international languages like English (hardly a "national" language when one considers that the great majority of its speakers live outside England) and force everyone to learn a language unfamiliar to almost everyone?

[quote="curl"]It's an international language in that it allows people all over the world to communicate with each other without one party needing to "appease" the other by learning their native tongue.[/quote]

Anyone who has observed the real-world behavior of people from various countries getting together knows that this is not a concern for most language learners. People use the languages they have in common to engage in conversation, without regard to which languages are whose native languages. I have seen French, Spanish, Korean, and German conversations in abundance while living in Taiwan, and the second-language speakers of those languages didn't feel bad about using each language with native speakers in the same conversation. I have seen a huge number of conversations among east Asian people in English (e.g., Koreans speaking to Taiwanese people, Japanese people speaking to people in Beijing, Philippine guest workers speaking to Thai guest workers, and so on) and nobody in those conversations proposes using any other language than the language they have in common. Indeed, I have seen many striking examples, both in person and on the Internet, of Chinese people of different language regions using English to communicate with one another, if some of them had little knowledge of Mandarin or lacked software for writing Chinese characters.

To sum up, the arguments found in a typical beginning Esperanto textbook about why someone should be interested in learning Esperanto are not based on empirical experience of language learners. They are like armchair arguments for communism that ignore the realities of history and human behavior.

chinese, *which my parents force me to learn* is hard enough for me :P

You should want to learn Chinese! It makes you who you are, so why not embrace it? Plus, it's a fun language, and no offense, but Chinese literature is so much cooler. Except for a few cases.

languages are hotly debated by scholars today..

oriental is not a language group..chinese would fall under the "sino-tibetian" group of languages.

esperanto, being latin-based, is a lot easier to learn for people that speak other Romance languages, such as Spanish, Portuguese, French, Catalan, etc., which all stem from latin.

AP human geography actually teaches some useful stuff...

[quote="curl"]they are speaking a language that has equal meaning to both of them.[/quote]
This is an important point: people have different understanding of english. Some more subtle point, may be not understood by a beginner in english, and can lead to confusion, "misinformation" during a dialog. (I know it's kind of precise, but you do not realize how often I saw this kind of misunderstanding during oral conversation). People have different prononciation, after all. I don't know if esperanto does handle, this ;)
Anyway, I think I'll try to learn it. (for the fun ;))

EDIT: And if Esperanto is a precise/conscise way of communication, then it does surpass english/french/russian/chineese/....

What's Esperanto? i.e. How does it work and how would you say "Math is good" in it?

http://www.lernu.net     <----- excellent esperanto resource  :)

All languages, natural or constructed, have ambiguities. And all languages are hard to pronounce for a majority of the world's inhabitants, because they all have different phonological systems and second-language learners always carry their native-language habits into learning the phonological system of a second language. What's hard about learning languages is not learning what's new about the new language, but rather forgetting what's habitual about the native language.


vector
complex numbers
linear algebra
linear algebra unsolved

Hi, everyone,

Having a problem with a vector space, wonder if anyone could help a bit. Thx.

$(1)$ Let $V$ be a vector space over $C$. Define another       scalar multiplication $*$ on $V: \alpha * x = Re(\alpha)x$,      $x \in V$, where $Re(\alpha)$ is the real part of $\alpha$
Is $V$ a vector space with respect original addition and
scalar multiplication $*$ ?

$(2)$ Same question as $(1)$, but now $*$ is defined by $\alpha *x =\overline{\alpha}x$, $\alpha \in C$, $x \in V$ and
$\overline{\alpha}$ is the complex conjugate of $\alpha$
So again Is $V$ a vector space with respect original addition and scalar multiplication $*$ ?

No and yes. Just go through the axioms of a vector space one by one to see if they are true or not in this case. One of the axioms is $\alpha*(\beta*x))=(\alpha\beta)*x$ - you should pay particular attention to it.

I think I know I shuold follow thr axiom, but I'm kinda didn't know how to start. Could you be kindly to state one or few? Thx.

It's hard to prove that something is a vector space if you don't know what a vector space is. The definition of a vector space can be found on [url=http://en.wikipedia.org/wiki/Vector_space]Wikipedia[/url] -- it includes a total of 8 axioms, but only 4 of them involve scalar multiplication.

Hi,
Yup, I did go through 8 axioms. However, when you were saying about the one axiom of mutlipication. Do you mean that I have to provide another $beta$ ? And how would you show if it's over $C$? Thx for helping.


False because when you use binomial theorem, the $\sqrt5$ will have odd powers sometimes and they never subtract off.

[quote="José"]True or false???

$(\frac{1+\sqrt{5}}{2})^{32} \mathbb \in {N}$[/quote]

[hide]Square it to get $(3+\sqrt5)/2$.

Square it again and you will still have a $sqrt5$ term.

Keep doing it etc.

Does my logic follow? Or am I wrong in thinking this way?[/hide]

False. Calculator approximates it to a natural number though.

[quote="José"]Exactly..... that's why I put it.... is there any $k$ for that ${\phi}^k$ is an integrer???[/quote]

0.

It's probably a pretty good idea to look at linear recurrences here.

In particular, choose $x_0$ and $x_1$ such that the solution to the recurrence $x_{n+1}=x_n+x_{n-1}$ is
\[ x_n=\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n  \]
Each $x_n$ is an integer.  What can you tell me about $x_{32}$?

This is very sophisticated for a Getting Started problem, but I would be happy to walk you guys through it if you're interested.

Yes, maybe it will be interested..... can anoyone answer blahblahblah's question??? (about $x_{32}$)

My post also answers the question 'is $\phi^k$, $k\geq 1$, ever an integer?'

[quote="jli"][quote="José"]True or false???

$(\frac{1+\sqrt{5}}{2})^{32} \mathbb \in {N}$[/quote]

no.

pull out the 1/2 and you have $1+\sqrt{5}$ to the power of whatever.  using the binomial theroem, there will always be the rt 5[/quote]

yep that's how I thought of it, it'll always end up as $x + y\sqrt{5}$

[quote="Ignite168"]$(\frac{1+\sqrt{5}}{2})^{32}\approx4870846.9999997946968976853425802$.[/quote]

See how near is that number to an integrer... that's why I posted the problem.... a nice one!


Question #29 from 2004 Chapter Sprint, I have seen a lot of questions like this one before and I don't know how to solve these type of questions. Thanks.

Camy made a list of every possible distinct five-digit positive even integer that can be formed using each of the digits 1,3,4,5 and 9 exactly once in each integer. What is the sum of the integers in Camy's list?

Sorry, I misread the problem.  I did not see even

In order to turn this post into a productive one

[hide="solution"]
Ok so we need to find the sum of all even 5-digit numbers that are even using the digits 1,3,4,5,9
In order for it to be even, the ones digit must be 4.

so all of the numbers must be in the form _ _ _ _ 4
now take the sum of the digits of the remaining number and you get 18. now isolate a digit by itself so we can see how many ways any of these four digits will become. This is basically 3! or 6. So we need to multiply the sum by the number of rearrangments : 18*6= 108.

Note that the number of the 4's will be 4! * 4 so 96.
Starting like normal addition with the 96 first, our answer will be 1,199,976
[/hide]

Last digit obviously has to be 4. So you only have 4!=24 number of integers.
All 24 numbers have ones digit of 4 so the sum for ones digit is 24*4 = 96. we will carry 9.
1+3+5+9 = 18. We would have 6 of each for 10`s,100`s, 1000`s and 10,000`s
Tens column we would have 6 of each 18. So 18*6+9 = 117. We would carry 11.
Hundreds will be 18*6+11 = 119 (Hundreds digit will be 9, carry 11)
Thousands will be 18*6+11=119 (Thousands digit will be 9 carry 11)
Ten Thousand would be 18*6+11=119 ( write 9 carry 11)

So the sum would be = 1,199,976


Polynomials P(x) and Q(x) have got more than one (or only one) real roots and for every real x satisfies:

P(1+ x + (Q(x))^2)= Q(1 + x + (P(x))^2)

prove that P(x)=Q(x) for every real x.

 :coolspeak:

Klaas, excuse me, where did you find Belarus 1996 problems? :?:

I found it in book "Problems from MO from over the world". Publishing house - Tutor.

No one has solved it?  :(

Has been solved here before. Not sure where.
$ P(x)^2\minus{}Q(x)^2$ changes sign when taken on roots of $ P(x)$ and $ Q(x)$.
So by the intermediate value theorem $ P(x)^2\minus{}Q(x)^2$ has some real root $ \lambda$.
But then for $ \mu\equal{}1\plus{}\lambda\plus{}P(\lambda)^2\equal{}1\plus{}\lambda\plus{}Q(\lambda)^2$ we get $ P(\mu)\equal{}Q(\mu)$.
Now if $ P(x)\not \equiv Q(x)$ take $ \mu\in\mathbb{R}$ maximal with $ P(\mu)\equal{}Q(\mu)$.
But then for $ \tau \equal{}1\plus{}\mu\plus{}P(\mu)^2\equal{}1\plus{}\mu\plus{}Q(\mu)^2>\mu$ we get also $ P(\tau)\equal{}Q(\tau)$. Contradiction


function
induction
number theory unsolved
number theory

Find all the fundtion $ f: N\minus{}\minus{}>N$ such that :
$ f(f(n))\plus{}f(n\plus{}1)\equal{}n\plus{}2$

Oh No one can Solve it or it is very easy or it is Mistake  :wink:

We shall show there doesn't exist a function satisfying the f.eq.
If $ f(a)\equal{}f(b)$ then $ f(f(a))\plus{}f(a\plus{}1)\equal{}f(f(b))\plus{}f(b\plus{}1)$, thus $ f(a)\equal{}f(b)$, thus f is injective.
Taking $ n\equal{}1$ we get $ f(f(1))\plus{}f(2)\equal{}3$Since $ f: N \rightarrow N$ then we must have
$ f(f(1))\equal{}1$ and $ f(2)\equal{}2$ or
$ f(f(1))\equal{}2$ and $ f(2)\equal{}1$.

Case 1 : $ f(f(1))\equal{}2$ and $ f(2)\equal{}1$. Taking $ n\equal{}2$ we get $ f(f(2))\plus{}f(3)\equal{}4$ thus $ f(1)\plus{}f(3)\equal{}4$. Since $ f$ is injective, then $ f(1)\equal{}1$ or $ f(1)\equal{}3$. If $ f(1)\equal{}1$, then $ f(f(1))\equal{}1$, contradiction. If $ f(1)\equal{}3$ then $ f(3)\equal{}1$. But $ f(f(1))\equal{}f(3)\equal{}2$, contradiction.
Case 2 : $ f(f(1))\equal{}1$ and $ f(2)\equal{}2$. Taking $ n\equal{}2$ we get $ f(f(2))\plus{}f(3)\equal{}4$ thus $ f(3)\equal{}2$. Since $ f$ is injective, then $ 3\equal{}2$, a contradiction.
We are forced to conclude that there doesn't exist a function satisfying the f.eq.

[quote="Harry Potter"]Find all the fundtion $ f: N \minus{} \minus{} > N$ such that :
$ f(f(n)) \plus{} f(n \plus{} 1) \equal{} n \plus{} 2$[/quote]
Yes,It is not too hard,my proof is quite similar to mlequi 's one,but how about
$ f(f(n)) \plus{} f(n \plus{} 1) \equal{} 2n\plus{}1$,I tried it mant time but failed :blush:

[quote="mlequi"]If $ f(a) \equal{} f(b)$ then $ f(f(a)) \plus{} f(a \plus{} 1) \equal{} f(f(b)) \plus{} f(b \plus{} 1)$, thus $ f(a) \equal{} f(b)$, thus f is injective.[/quote]

How do you get $ f(f(a))\plus{}f(a\plus{}1)\equal{}f(f(b))\plus{}f(b\plus{}1)$ from $ f(a)\equal{}f(b)$?

[quote="Allnames"][quote="Harry Potter"]Find all the fundtion $ f: N \minus{} \minus{} > N$ such that :
$ f(f(n)) \plus{} f(n \plus{} 1) \equal{} n \plus{} 2$[/quote]
Yes,It is not too hard,my proof is quite similar to mlequi 's one,but how about
$ f(f(n)) \plus{} f(n \plus{} 1) \equal{} 2n \plus{} 1$,I tried it mant time but failed :blush:[/quote] The obvious solution is $ f(n)\equal{}n$ but I don't know how to prove that it's the only one :blush:

[quote="mlequi"]We shall show there doesn't exist a function satisfying the f.eq.
If $ f(a) \equal{} f(b)$ then $ f(f(a)) \plus{} f(a \plus{} 1) \equal{} f(f(b)) \plus{} f(b \plus{} 1)$, thus $ f(a) \equal{} f(b)$, thus f is injective.
Taking $ n \equal{} 1$ we get $ f(f(1)) \plus{} f(2) \equal{} 3$Since $ f: N \rightarrow N$ then we must have
$ f(f(1)) \equal{} 1$ and $ f(2) \equal{} 2$ or
$ f(f(1)) \equal{} 2$ and $ f(2) \equal{} 1$.

Case 1 : $ f(f(1)) \equal{} 2$ and $ f(2) \equal{} 1$. Taking $ n \equal{} 2$ we get $ f(f(2)) \plus{} f(3) \equal{} 4$ thus $ f(1) \plus{} f(3) \equal{} 4$. Since $ f$ is injective, then $ f(1) \equal{} 1$ or $ f(1) \equal{} 3$. If $ f(1) \equal{} 1$, then $ f(f(1)) \equal{} 1$, contradiction. If $ f(1) \equal{} 3$ then $ f(3) \equal{} 1$. But $ f(f(1)) \equal{} f(3) \equal{} 2$, contradiction.
Case 2 : $ f(f(1)) \equal{} 1$ and $ f(2) \equal{} 2$. Taking $ n \equal{} 2$ we get $ f(f(2)) \plus{} f(3) \equal{} 4$ thus $ f(3) \equal{} 2$. Since $ f$ is injective, then $ 3 \equal{} 2$, a contradiction.
We are forced to conclude that there doesn't exist a function satisfying the f.eq.[/quote]

Oh Boy ! F(n) Could be 0  :)   :)    :)    :)

Assume f(1)=a, we have f(a)+f(2)=3, so f(2) is either 1 or 2.

Case (1)   f(2)=1

f(f(2))+f(3)=4=a+f(3), so a<=3. We can verify a can not be 1 or 2. So f(1)=3. Then we can show, by induction, that
f(n)=n, if n>3 and n is odd; f(n)=2, if n>3 and n is even; f(3)=1

Case (2) f(2)=2

We can show that f(n)>1 for n>2, so f(1) has to be 1. Then we can show, by induction, f(n)=[a*n+1], where a=(sqrt(5)-1)/2, and [x] means the largest integer part of x.


End November/beginning December.  We haven't decided yet.