function
trigonometry
logarithms
calculus
integration
algebra
floor function

Suppose that $ b, X $  are positive integers $(b>2)$. Assuming that $b, X, j , (j \in \{0,1,...,b-1\}), $ are given, [b] how many times the digit $ j $ appears  the representation of $ X $ in base $b$     ?[/b]  Let $ N_j=N_j(X;  b) $ be this  number, e.g.  $ N_0(20052006; 10)=4\; . $  Using only floor function (integer part), it's possible to find a  closed form for $ N_j $ (perhaps as a sum of a convergent series)  ?
Let $[ \cdot ] $ denote the integer part function and define  $ G_b:{\mathbb R}\to {\mathbb R} $ by $ \displaystyle G_b(t)= \left\{\begin{array}{lcl} \displaystyle \frac{1}{b^2}\left( \frac{\sin{\pi t} }{\sin{\frac{\pi t}{b}}}
\right)^2  & , &  t\ne b\cdot p\\ 1 &, &  t=b\cdot p \end{array}\right.\; ,\; p\in {\mathbb Z} \; .$
Try to prove/disprove that
\[
N_j(X;b)=\sum\limits_{k=0}^{\left[\log_b{X}\right]}G_b
\left(\left[\frac{X}{b^k}-j\right]\right)\; \; \; \; \; \;
\mbox{(according to Robert Israel).}
\]

[quote="flip2004"]Suppose that $b, X$  are positive integers $(b>2)$. Assuming that $b, X, j , (j \in \{0,1,...,b-1\}),$ are given, [b] how many times the digit $j$ appears  the representation of $X$ in base $b$     ?[/b]  Let $N_j=N_j(X; b)$ be this  number, e.g.  $N_0(20052006; 10)=4\; .$  Using only floor function (integer part), it's possible to find a  closed form for $N_j$ (perhaps as a sum of a convergent series)  ?
Let $[ \cdot ]$ denote the integer part function and define  $G_b: {\mathbb R}\to {\mathbb R}$ by $\displaystyle G_b(t)= \left\{\begin{array}{lcl} \displaystyle \frac{1}{b^2}\left( \frac{\sin{\pi t} }{\sin{\frac{\pi t}{b}}} \right)^2 & , & t\ne b\cdot p\\ 1 &, & t=b\cdot p \end{array}\right.\; ,\; p\in {\mathbb Z} \; .$
Try to prove/disprove that
\[ N_j(X;b)=\sum\limits_{k=0}^{\left[\log_b{X}\right]}G_b \left(\left[\frac{X}{b^k}-j\right]\right)\; \; \; \; \; \; \mbox{(according to Robert Israel).}  \][/quote]
I (re-)discovered that
\[ \begin{array}{|c|} \hline \\ \displaystyle N_j(X,b)=\displaystyle \sum\limits_{k=1}^{\infty}\left( \left[\frac{X}{b^k} -\frac{j}{b}\right] - \left[\frac{X}{b^k} - \frac{j+1}{b} \right] \right)\\ \\ \hline \end{array}\; ,  \]
where $[\; \cdot\; ] \;$ denotes integral part.
[b]Reference:[/b]
Gazeta Matematica (Seria B), anul XCIV (1989),nr.1,p.35,[i] Problem C :572[/i].,proposed by Alex. L .


function
limit
calculus
calculus computations

Suppose $ f(x) \equal{} \begin{cases} 0 \ \ \ \text{if} \ x \notin \mathbb{Q} \\
1/q \ \ \ \text{if} \ x \in \mathbb{Q} \ \text{and} \ x \equal{} p/q \ \text{in lowest terms} \end{cases}$

1. Fix $ t \in \mathbb{R}$ and $ n \in \mathbb{N}$. Show that $ f$ maps finitely many elements of $ (t \minus{} 1/2, t \plus{} 1/2)$ to $ 1/n$.

So the length of the interval is $ 1$. I think its $ n \minus{} 1$. But that is intuition. How do you make it rigorous?

2. Prove that $ f$ is continuous at every irrational number. So $ \forall \epsilon > 0$, $ \exists \delta > 0$ such that $ |x \minus{} a| < \delta \implies |f(x)| < \epsilon$. Do we want elements that dont map to $ 1/n$?

[quote="lordmahone123"]I think it's $ n\minus{}1$.[/quote]It's not. It's [i]at most[/i] $ n\minus{}1$. How many fractions with denominator $ \frac1n$ are there in that range? Some of them won't be in lowest terms; why isn't that a problem?

2: The essential rule for finding $ \delta$ here is to look for the closest bad point $ y$ at which $ |f(y)|\ge\epsilon$, and choose $ \delta\equal{}|y\minus{}x|$. How can you show that there is a closest bad point?

[quote="jmerry"][quote="lordmahone123"]I think it's $ n \minus{} 1$.[/quote]It's not. It's [i]at most[/i] $ n \minus{} 1$. How many fractions with denominator $ \frac1n$ are there in that range? Some of them won't be in lowest terms; why isn't that a problem?

2: The essential rule for finding $ \delta$ here is to look for the closest bad point $ y$ at which $ |f(y)|\ge\epsilon$, and choose $ \delta \equal{} |y \minus{} x|$. How can you show that there is a closest bad point?[/quote]

Because the function is defined so that $ x$ is in lowest terms. You can show there is a closest bad point by using the Well Ordering Property? But dont you want to pick $ \delta$ to be the minimum of 2 values?

So you end up with $ 1\plus{}1\plus{}2\plus{}3\plus{}5\plus{}7\plus{} \ldots$.

That doesn't give me any confidence that you understood what I said.

Also, it's not about primes.

2)
Let x be irrational.
Define g(n) as follows. Consider the fractions in lowest terms with denominator $ \leq$ n. They are bounded away from $ x$ for each n. Let g(n) be the smallest distance between one of those fractions and $ x$. Then, $ \lim_{n\to\infty}g(n) \equal{} 0$, but $ g(n)\neq0$ for all $ n$, and $ g$ is decreasing. So if we want to find some $ \delta$ such that for all rationals $ q$ in $ (x \minus{} \delta,x \plus{} \delta)$, $ f(q) < \epsilon$. So take $ n$ to be the least positive integer such that $ g(n) < \epsilon$, then $ \delta \equal{} 1/n$. Since all fractions within $ \epsilon$ of x have denominators $ \geq n$ by choice of n, this works I think.

[quote="jmerry"][quote="lordmahone123"]I think it's $ n \minus{} 1$.[/quote]It's not. It's [i]at most[/i] $ n \minus{} 1$. How many fractions with denominator $ \frac1n$ are there in that range? Some of them won't be in lowest terms; why isn't that a problem?

2: The essential rule for finding $ \delta$ here is to look for the closest bad point $ y$ at which $ |f(y)|\ge\epsilon$, and choose $ \delta \equal{} |y \minus{} x|$. How can you show that there is a closest bad point?[/quote]

Basicaly we are trying to show that $ f$ maps only finitely many rational numbers in lowest terms in this interval to $ 1/n$. Let $ I \equal{} (t \minus{} 1/2, t \plus{} 1/2)$. Let $ x \equal{} p/n \in I$ in lowest terms. Then $ p$ is coprime to $ n$. Can we somehow use this to show the maximum number is $ n \minus{} 1$? E.g. $ \varphi(n) \equal{} n\minus{}1$?

Don't worry about that stuff. How many fractions $ \frac{k}{n}$, not necessarily in lowest terms, are in that interval?

[quote="jmerry"]Don't worry about that stuff. How many fractions $ \frac {k}{n}$, not necessarily in lowest terms, are in that interval?[/quote]

$ n \minus{} 1$ by inspection. I let $ t \equal{} 0$ and $ n \equal{} 3$. Thus number in lowest terms is $ \leq n\minus{}1$.

You don't get to choose $ t$ and $ n$. This should apply for all choices. Also, your count is wrong; $ \frac03$ is a fraction with denominator 3.

You fix $ t$ and $ n$. So the length of the interval really only matters. So number of fractions is $ n$. Thus number of fractions in lowest terms is $ \leq n$.

$ p/n < t\plus{}1/2$

So $ p < n(t\plus{}1/2)$.


calculus
vector
search
geometry
linear algebra
graph theory
real analysis

This semester I have found a new love for pure mathematics. Having gone to study actuarial science in university on a hunch rather than having any previous math interest, I currently lack much of the skills that the pure math majors currently have. I am switching from the honors math courses (linear algebra 1 and calculus 2) into advanced linear algebra 2 and advanced calculus 3.

I am asking the people here that have done the advanced stream what I can do to ease the transition? I have a 4 month work term now and have a lot of free time studying.

Here is my current book list to catch up:

Rudin's Introduction to Mathematical Analysis (Not sure if I should start with this for analysis, perhaps spivak's calculus?)
How to Solve It and How to Prove it (Going through these now, very good for proofs/problem solving)

I still need a good linear algebra book.

I'd say starting with Spivak is a good idea. I've also heard Wade's "introduction to analysis" covers the material in a way very similar to 147/148 (although it would probably be a bit dry compared to Spivak). As for linear algebra, the standard 146/245 textbook is Linear Algebra by (oh god... the author escapes me right now but I'll find it in the morning). I'd say that as far as the transition goes, 247 will be a much bigger jump than 245 because I found 146 to be a bit closer to 136 (although everything was catered more to abstract vector spaces and not just a select few finite dimensional spaces) whereas 147/148 differed significantly in content on some topics when compared to 137/138.

To follow up, the book is Linear Algebra by Friedberg, Insel and Spence.

Thank you very much, your help is much appreciated. To my luck, there is an international version.

Very cool, I did the same thing.
I went from regular lin alg 1 and calc 2 to adv lin alg 2 and calc 3...
If you can get a hold of notes and assignments from a previous term, that would help you a lot.
When I did calc 3 there were course notes, not a textbook, so you can try and see if Graphics is still selling the coursenotes from the Winter term.

So, the last post was a while ago, but I was wondering what you guys think of U Waterloo, what you like, what you don't. Do yuou get lots of time with math profs if you need it?

I'm seriously looking at U Waterloo for BMath next year (started the Ontario Application thing today) and then doing the teaching option... I've talked to a bunhc of people, but no math majors... care to shed some light?

I would suggest you nose around the UW website and see if you can find faculty members that can answer your questions about Teaching option.  As for UW, the most valuable experience would be the COOP program, although I am not sure how that plays with students with teaching options.  And yes, you can walk into any math prof's office and they are usually very nice and would be more than happy to chat with you (although I've occasionally heard stories of hard nosed profs)

If anyone is in the double degree program (BMath/BBA) at WLU and UW, how hard is it? Is the Co-op good or a hindrance, and is the business part boring? Also, what  kinds of things would you learn in the business courses?

Good questions.  I can't answer anything about the Teaching Option or the Double Degree option, but I can talk about UWaterloo in general.  I'd be happy to answer anything I can  :)

I love UW.  I find the advanced math courses interesting, in general the math professors are really really good.  They are friendly, not intimidating, and always willing to help.  I'm not sure what you guys would like to know on the side...

I'm in the co-op program here at Waterloo, I'm actually starting my 4th of 6 work terms in January.  I think it's a terrific program.  I must admit we're not fond of Jobmine (the job search system students use), and interviews can come at some stressful times.  If you're in high demand too, it's hard to juggle all your interviews and class times.  Co-op is great because you get more than a year's worth of real world job experience before you graduate, which makes for a very attractive resume when you do enter the real world.  Not only that, but with 6 possible co-op terms, it allows you the flexibility to try different areas and see what tickles your fancy.  More often than not you get introduced into fields of work that you never thought you'd be interested in.  It's also relatively common that the place where you do your last co-op term will extend an offer for permanent placement upon graduation.  If you're looking at a Business degree, I highly recommend co-op, it will let you develop real business skills early on.  There are so many companies that higher Waterloo co-ops, some would argue Google, Amazon, and Microsoft being among the more attractive companies.

Another thing I love about UW is the people.  There are tons of clubs and events where you can meet tons of great people, always willing to help out students or just relax between assignments.  For instance, if you're in math, the PMAMC&OC (Pure math, applied math, combinatorics and optimization club) is one club full of math students who like to hang out, or do math, or take a break and play frisbee.  I hear rumors that some other  university math departments can get pretty competitive, and it's not really the case in Waterloo.

Downsides....first of all, the town of Waterloo itself doesn't have much to do.  It's kind of a bubble in fact.  There's movie theaters and bars and stuff, but if you're with a group of friends on a friday night, sometimes it just seems like there's nothing to do, Waterloo is pretty small.  You get used to it after a while though.  And I usually console myself with trips into Toronto (particularly if I want a good mall, being a girl who likes to shop, heh).

Second downside is sometimes you can get stuck with a crappy co-op job.  In particular this seems to happen to first years, where you don't do too much and seem like a glorified secretary.  Don't worry, it does get better as long as you don't get bad evaluations.

All in all, university is what you make of it.  Make sure you take everything into consideration though...even the town it's in.  Though it might not seem like it, it can make a difference.  =)
I hope that helped...if anyone wants anything more specific, ask away, or message me!

Less than a month till my coop term is over and back to school!

Has anyone taken CO 350, linear optimization and Math 249 Adv Combinatorics?

How are they as courses, in terms of interestingness and difficulty?

Also, how are the upper year pure math courses in terms of difficulty? How many is it recommended to take per term? 4?

As far as I know CO355 is the preferred course in terms of intensity, and for the pure math courses there are two distinct levels of intensity as well.

@samspotting

Well now it is the new term. Are you in Math 249? If so I can't add detail, but if not I can tell you how it has been so far (I am in it this winter term :) )

Yes, I am having an absolute blast. Honours math was ok... but I hated how the profs didnt give a rats ass about the proofs and a lot of the time it became a repeating computational exercise.

Advanced courses so far are manageable. I am finding advanced lin alg is easier than advanced calc, but that might change. I have mixed feelings about advanced combinatorics, I don't like how half the stuff we are doing there's no explanation other than it just works.

Yes that, and I am finding it rather difficult =) Although it is enlightening.

Ok things have changed lol

Advanced calc is easy, advanced lin alg is really hard :( almost failed the midterm.

The advanced combinatorics midterm was really hard as well.

Ehh how are you finding this graph theory stuff? I prefer the enumeration ^_^ It was easier.
And yea it was difficult. This is my first advanced class and it is definitely a bump up :(
Marcoux has a reputation for getting very hard. Just pray you don't have him for Real Analysis :P (PMath 351). Lawrence teaches it this summer, might be a good time to take it instead.

graph theory is ok, what i found really really helped was that I did a book on proofs that focused on relations and set theory before the course, so my mastery of proofs involving relations and sets is pretty good.

The midterm was brutal though, I didnt get the last question and the conway's checkers game (grr 2/3 theorem). Gona have to pick it up in the final.

His third assignment was ridiculous, had so much long computation omg. Im not made of time lol. Spent 3 hours correcting myself on the first question.

I love reading your conversations about classes - i'm really not sure what to expect next year in terms of academic stuff. You hear all about rez and food and life, but as for the actual courses I don't know what to expect.

I'm registered right now for Honors mathematics co-op and then the teaching option. But I'm not sure about the honors part.  I'm taking (and doing well in) AP Calculus right now, but my math 12 background was a little sketchy, so Euclid was definitely a challenge.
- Someone mentioned that they were in the honors program - what is the difference between that and regular non-honors math? Who would you suggest the honors courses to?

Thanks,

Honours math is the normal program at Waterloo. Everyone starts in the honours math program, and the people who are unable to maintain a sufficient average are forced to drop into the 3-year general program. Also, I think you are no longer eligible for co-op once you are in the general program, and can't take many of the courses offered by the faculty of math.

Don't worry about it, I came to waterloo having not taken math for a year (finished the math stream in gr 11) and failed the math assesment test with something like 3/15.

I got excellent standing in both my first and second semester (>80%). Honours math is easy.

Ok, that makes a lot of sense. and now I feel a whol lot better about the whole math thing. Thanks a lot:)

Are you going to be in Waterloo this fall, andrea.lee?

Yes, I have a conditional acceptance based on my mark in Calculus (i'm finished now), so UW is my plan for September. I'm really excited - I can't wait. Are you there/planning on going?

I'm going to Waterloo Honours Math Co-op in September too!!!   :lol:

Ahh actually I will be third year come this fall. I am also an Orientation Leader so maybe we'll see each other around, both of you ;)


When I logged in today, I noticed that the way the forums were display was not as it has been.  For example, I have the High School forums showing usually but, today it was missing.  Also the Contests & Programs section has new sections that are uncollapsable.  Though, after I went to my preferences and reapplied them, it is back to normal except for those sections under Contests & Programs.
So, it is not really a problem, just thought I say something.  :)

We had a small problem when uploading some updated files. Problems should be fixed now though.

Edit: if you have any problems please erase your cookies (or go to the Preferences page, hide forums and click submit).


limit
inequalities
real analysis
real analysis unsolved

I can not understand the line denoted by red line .
 can you help me ?
thanks

I think like that .
Because $ f(x_n)\geq x_n$, then $ \lim_{n\to\infty} f(x_n) \geq x_0$.
Because $ f$ is increasing, $ f(x_n)\leq f(x_0)<x_0$,then$ \lim_{n\to\infty} f(x_n)\leq x_0$.
But if $ \lim_{n\to\infty} f(x_n)\leq f(x_0)<x_0$, we can only get $ \lim_{n\to\infty} f(x_n) < x_0$

It is strange.

Oh, you're just being confused by the contradiction structure. How about a completely different approach:

Define $ A$, $ x_0$, $ x_n$ as before. This time, don't even ask whether $ x_0\in A$.
Since $ f(x_n)\ge x_n$, $ \lim_{n\to\infty}f(x_n)\ge x_0$. Since $ f$ is increasing, $ \lim_{n\to\infty}f(x_n)\le f(x_0)$ and $ f(x_0)\ge x_0$.

On the other side, choose some $ \epsilon>0$. Since $ x_0\plus{}\epsilon\not\in A$, $ f(x_0\plus{}\epsilon)<x_0\plus{}\epsilon$. Since $ f$ is increasing, $ f(x_0)\le f(x_0\plus{}\epsilon)<x_0\plus{}\epsilon$. As $ \epsilon\to 0$, this becomes $ f(x_0)\le x_0$.

From the two inequalities, we have $ f(x_0)\equal{}x_0$. Done.

OK, there's one other case: if $ x_0\equal{}b$, we can't do the second argument at all, but we don't need to because the inequality is automatic.

if you're familiar with the squeeze theorem, this is the same. consider sequences

$ a_n \equal{} x_n$
$ b_n \equal{} f(x_n)$
$ c_n \equal{} x_0$

you know $ a_n$ and $ c_n$ converge to the same value ($ x_0$), and $ a_n \leq b_n < c_n$, hence $ b_n$ converges to the same limit.

the contradiction occurs because continuity of $ f$ means $ x_n \to x_0 \implies f(x_n) \to f(x_0)$, meaning $ f(x_0) \equal{} x_0$ because the limit squeezing from earlier must be the same as this one.

[quote="shallow"]if you're familiar with the squeeze theorem, this is the same. consider sequences

$ a_n \equal{} x_n$
$ b_n \equal{} f(x_n)$
$ c_n \equal{} x_0$

you know $ a_n$ and $ c_n$ converge to the same value ($ x_0$), and $ a_n \leq b_n < c_n$, hence $ b_n$
.....[/quote]
How to do prove here $ f(x_n)<x_0$ ?

[quote="water2011"][quote="shallow"]if you're familiar with the squeeze theorem, this is the same. consider sequences

$ a_n \equal{} x_n$
$ b_n \equal{} f(x_n)$
$ c_n \equal{} x_0$

you know $ a_n$ and $ c_n$ converge to the same value ($ x_0$), and $ a_n \leq b_n < c_n$, hence $ b_n$
.....[/quote]
How to do prove here $ f(x_n) < x_0$ ?[/quote]

i think you already used that earlier

$ f$ is increasing, so $ x_n < x_0$ implies $ f(x_n) \leq f(x_0)$. and you start the problem by assuming $ f(x_0) < x_0$, hence $ f(x_n) < x_0$.


[b]1. The problem statement, all variables and given/known data[/b]

Given a function $ f: R\rightarrow R$ and a number L,write down a definition of the statement

$ \lim_{x\rightarrow\minus{}\infty}f(x)\equal{}L$

[b]3. The attempt at a solution[/b]

Is just $ \lim_{x\rightarrow\minus{}\infty}f(x)\equal{}\lim_{x\rightarrow\minus{}\infty}f(\minus{}x)$

and definition is
 for $ \forall \epsilon>0$ $ \exists N$ such that $ \forall n>N$
we have $ |f(\minus{}x)\minus{}L|<\epsilon$

[quote="azatkgz"]Is just $ \lim_{x\rightarrow \minus{} \infty}f(x) \equal{} \lim_{x\rightarrow \minus{} \infty}f( \minus{} x)$[/quote]

Incorrect!

[quote="azatkgz"]Given a function $ f: R\rightarrow R$ and a number L,write down a definition of the statement

$ \lim_{x\rightarrow \minus{} \infty}f(x) \equal{} L$[/quote]

The definition is as follows: for $ \forall \epsilon > 0$ $ \exists N>0$ such that $ \forall x <\minus{} N$ we have $ |f(x) \minus{} L| < \epsilon$


group theory
abstract algebra
superior algebra
superior algebra unsolved

Show that if $ G$ is a group and $ H$ is a subgroup of $ G$ with index $ 2$, then $ H$ is a normal subgroup of $ G$.

I just need a hint, can anyone help?

If $ g \notin H$ then $ gH \equal{} H'$ where $ H' \equal{} G\minus{}H$

Similarly $ Hg \equal{} H'$

Hence gH = Hg making H a normal subgroup


A quadrilater has side lengths 3,3,x, and y.  We choose x randomly, and then we choose y (x and y are integers).  Let N be the number of possible y after x is chosen.  What is the maximum of N.

[hide="Solution"]$4^{9}+9^{4}= 2^{18}+3^{8}$, which from memorization of powers of two and three is
$262144+6561 = 268705$
Which is divisible by 5:
$5*53741$

After some ugly prime checking, I see that 61 divides it.
Expression $= 5 \cdot 61 \cdot 881$, making 881 the largest prime divisor.
[/hide]
How can one do this nicely?

I thought the solution looked "ackward"  for this problem :wink: .

[quote="DiscreetFourierTransform"]$4^{9}+9^{4}= 2^{18}+3^{8}$, which from memorization of powers of two and three is
$262144+6561 = 268705$
Which is divisible by 5:
$5*53741$

After some ugly prime checking, I see that 61 divides it.
Expression $= 5 \cdot 61 \cdot 881$, making 881 the largest prime divisor.

How can one do this nicely?[/quote]

Yea for that 4^9+9^4 thing..its just 2^18+3^8, which is just (2^9)^2+(3^4)^2, which is a^2+b^2, which is (a+b)^2-2ab, so its (2^9+3^4)-2*2^9*3^4, which is (2^9+3^4)-2^10*3^4, which is a^2-b^2.  So we have (2^9+3^4)-(2^5*3^2)^2, which is (2^9+3^4+2^5*3^2)(2^9+3^4-2^5*3^2), 2^9+3^4+2^5*3^2=881.  Now that is the largest possible value that can work, but still check if it works, apparently it does so 881.

For the quadrilateral, it requires some triangle inequality.  But just using diophantient thing, you can get 11 solutions for y after x is chosen (x-5 to x+5)

[quote="AstroPhys"][quote="DiscreetFourierTransform"]Uhoh. I posted a reply to the problem what is the largest prime divisor of $9^{4}+4^{9}$, not this one.
Something odd is going on.[/quote]
DiscreetFourierTransform said that the solution was not for this thread.[/quote]

he wanted a better way to do it.

[hide="Solution"]Per the triangle inequality theorem extended to quadrilaterals, $6+x>y$ and $6+y>x$.
So we have
$6+y>x$ which can also be written $y>x-6$, combined with $x+6>y$
and therefore $x-6<y<x+6$.
Since we're looking for integer values for y, there are $\boxed{11}$ possible values.
[/hide]


For each positive integer $n$, let $f(n)$ denote the number of ways of representing $n$ as a sum of powers of 2 with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance, $f(4)=4$, because the number $4$ can be represented in the following four ways: \[4, 2+2, 2+1+1, 1+1+1+1.\] Prove that, for any integer $n \geq 3$, \[2^{n^{2}/4}< f(2^{n}) < 2^{n^{2}/2}.\]

Solution at http://www.kalva.demon.co.uk/imo/isoln/isoln976.html
The key is to derive a recurrence relation for f(n) [not for f(2n)]. If n is odd, then the sum must have a 1. In fact, there is a one-to-one correspondence between sums for n and sums for n-1. So:

          f(2n+1) = f(2n)

Now consider n even. The same argument shows that there is a one-to-one correspondence between sums for n-1 and sums for n which have a 1. Sums which do not have a 1 are in one-to-one correspondence with sums for n/2 (just halve each term). So:

          f(2n) = f(2n - 1) + f(n) = f(2n - 2) + f(n).

The upper limit is now almost immediate. First, the recurrence relations show that f is monotonic increasing. Now apply the second relation repeatedly to f(2n+1) to get:

  f(2n+1) = f(2n+1 - 2n) + f(2n - 2n-1 + 1) + ... + f(2n - 1) + f(2n) = f(2n) + f(2n - 1 ) + ... + f(2n-1 + 1) + f(2n)   (*)

and hence f(2n+1) ≥ (2n-1 + 1)f(2n)

We can now establish the upper limit by induction. It is false for n = 1 and 2, but almost true for n = 2, in that: f(22) = 222/2. Now if f(2n) ≤ 2n2/2, then the inequality just established shows that f(2n+1) < 2n2n2/2 < 2(n2+2n+1)/2 = 2(n+1)2/2, so it is true for n + 1. Hence it is true for all n > 2.

Applying the same idea to the lower limit does not work. We need something stronger. We may continue (*) inductively to obtain f(2n+1) = f(2n) + f(2n - 1) + ... + f(3) + f(2) + f(1) + 1.   (**)     We now use the following lemma:

  f(1) + f(2) + ... + f(2r) ≥ 2r f(r)

We group the terms on the lhs into pairs and claim that f(1) + f(2r) ≥ f(2) + f(2r-1) ≥ f(3) + f(2r-2) ≥ ... ≥ f(r) + f(r+1). If k is even, then f(k) = f(k+1) and f(2r-k) = f(2r+1-k), so f(k) + f(2r+1-k) = f(k+1) + f(2r-k). If k is odd, then f(k+1) = f(k) + f((k+1)/2) and f(2r+1-k) = f(2r-k) + f((2r-k+1)/2), but f is monotone so f((k+1)/2) ≤ f((2r+1-k)/2) and hence f(k) + f(2r+1-k) ≥ f(k+1) + f(2r-k), as required.

Applying the lemma to (**) gives f(2n+1) > 2n+1f(2n-1). This is sufficient to prove the lower limit by induction. It is true for n = 1. Suppose it is true for n. Then f(2n+1) > 2n+12(n-1)2/4 = 2(n2-2n+1+4n+4)/4 > 2(n+1)2/4, so it is true for n+1.

The link in chien than's answer no longer works. Also, his proof can be a bit hard to read because copying exponents went wrong apparently. Here is my version.

We will first look at the function $f(m)$, where $m$ can be any non-negative integer and is not required to be a power of two itself. Define $f_k(m)$ as the number of ways of representing $m$ as a sum of powers of two where we use $1$ in the sum exactly $k$ times.  With the definition of $f_k(m)$, we clearly get $f(m) = \displaystyle \sum_{k=0}^m f_k(m)$. We also have $f_k(m) = f_0(m-k)$ and, if $m$ is odd, $f_0(m) = 0$, while if $m$ is even, $f_0(m) = f\left(\frac{m}{2}\right)$. The latter equality can be seen by noticing that one can put the expressions for $m$ that do not contain a $1$ in a one-to-one correspondence with all expressions for $\frac{m}{2}$, by simply dividing every term by two. Applying these properties one can obtain the following way to recursively calculate $f(m)$:

\begin{align}
f(m) &= \sum_{k=0}^m f_k(m) \nonumber \\
&= \sum_{k=0}^m f_0(m-k) \nonumber \\
&= \sum_{k=0}^m f_0(k) \nonumber \\
&= \sum_{k=0}^{\left \lfloor \frac{m}{2} \right \rfloor} f_0(2k) \nonumber \\
&= \sum_{k=0}^{\left \lfloor \frac{m}{2} \right \rfloor} f(k)
\end{align}

We will now start our proof of the upper bound. With equality (1) it is straightforward to check $f(8) = f(0) + f(1) + f(2) + f(3) + f(4) = 1 + 1 + 2 + 2 + 4 = 10$, so that the inequality $f(2^n) < 2^{n^2/2}$ is seen to hold for $n = 3$. Let us therefore assume $n \ge 4$ and by induction we may assume $f(2^{n-1}) < 2^{(n-1)^2/2}$. Furthermore note that $f$ is a monotonically increasing function.

\begin{align*}
f(2^n) &= \sum_{k=0}^{2^{n-1}} f(k) \\
&= 1 + 1 + \sum_{k=2}^{2^{n-1}} f(k) \\
&< f(2^{n-1}) + \sum_{k=2}^{2^{n-1}} f(2^{n-1}) \\
&= 2^{n-1} f(2^{n-1}) \\
&< 2^{n-1} 2^{(n-1)^2/2} \\
&= 2^{n^2/2 - n + 1/2 + n - 1} \\
&= 2^{n^2/2 - 1/2} \\
&< 2^{n^2/2}
\end{align*}

For the lower bound, we first need to show a little lemma.

[b]Lemma.[/b]
For all $n \ge 2$ and all $i$ with $1 \le i \le 2^{n-2}$ we have the following inequality:

$$
f(i) + f(2^{n-1} - i + 1) \ge 2f(2^{n-2})
$$

[i]Proof.[/i] We will actually prove $f(i) + f(2^{n-1} - i + 1) \ge f(i + 1) + f(2^{n-1} - i)$, which implies $f(i) + f(2^{n-1} - i + 1) \ge f(2^{n-2}) + f(2^{n-2} + 1) = 2f(2^{n-2})$ by iteration. To show $f(i) + f(2^{n-1} - i + 1) \ge f(i + 1) + f(2^{n-1} - i)$, note that when $i$ is even we have $f(i) = f(i+1)$ and $f(2^{n-1} - i + 1) = f(2^{n-1} - i)$, so that we actually have equality. When $i$ is odd, we have $f(i+1) - f(i) = f\left(\frac{i+1}{2}\right)$ and $f(2^{n-1} - i + 1) - f(2^{n-1} - i) = f\left(\frac{2^{n-1} - i + 1}{2}\right)$, both by equation (1), so that:

\begin{align*}
f(i) + f(2^{n-1} - i + 1) &= f(i+1) - f\left(\frac{i+1}{2}\right) + f(2^{n-1} - i) + f\left(\frac{2^{n-1} - i + 1}{2}\right) \\
&= f(i+1) + f(2^{n-1} - i) + \left(f\left(\frac{2^{n-1} - i + 1}{2}\right) - f\left(\frac{i+1}{2}\right)\right) \\
&\ge f(i+1) + f(2^{n-1} - i)
\end{align*}

Where the final inequality follows from that fact that $f$ is monotonically increasing and $\frac{2^{n-1} - i + 1}{2} \ge \frac{i+1}{2}$ since $i \le 2^{n-2}$. This finishes the proof of the lemma.

Now we can finally prove the lower bound. Since $f(2) = 2$, the inequality $2^{n^2/4} < f(2^n)$ is seen to hold for $n = 1$, so assume $n \ge 2$. By applying equation (1) and the above lemma  we get:

\begin{align*}
f(2^n) &= \sum_{k=0}^{2^{n-1}} f(k) \\
&> \sum_{i=1}^{2^{n-2}} \left(f(i) + f(2^{n-1} - i + 1) \right) \\
&\ge 2^{n-1} f(2^{n-2}) \\
&> 2^{n-1} 2^{(n-2)^2/4} \\
&= 2^{n^2/4 - n + 1 + n - 1} \\
&= 2^{n^2/4}
\end{align*}


search
Diophantine equation
number theory proposed
number theory

Let $ m$ and $ n$ natural numbers such that:
$ \frac{m\plus{}1}{n}\plus{}\frac{n\plus{}1}{m}\equal{}k$, when k is a natural number too(not constant).
Prove that there are infinitely pairs $ (m,n)$.

[hide="Hint"]Use Pell equation,we prove  there are infinitely pairs $ (m,n)$ such that
$ \frac {m\plus{}1}{n}\plus{}\frac{n\plus{}1}{m}\equal{}3$.It is quite obivious
[/hide]


group theory
abstract algebra
number theory
relatively prime
superior algebra
superior algebra unsolved

Hello,

Let G be a finite group and H a normal subgroup of G such that card(H) = n, and n is relatively prime to card(G).
Show that H is the only subgroup of G with cardinal n.

I have a solution using Sylow subgroups but I believe there is something more elementary. Any suggestion ?

I assume you meant that $n$ is coprime to $[G:H]$, right?

Lat $K\le G$ be another subgroup of $G$ of order $n$. Then $H$ is a normal subgroup of $KH$, and $KH/H$ is a subgroup of $G/H$, meaning that $[KH:H]$ divides $[G:H]$. However, $KH/H$ is isomorphic to $K/(K\cap H)$, meaning that, in particular, they have the same order, which must then divide $|K|=n$. We have shown that the order of $KH/H$ divides both $n$ and $[G:H]$, so it must be $1$, or, in other words, $H=KH\Rightarrow K\le H\Rightarrow K=H$.

Very nice Grobber !

I had as a proof: every p-Sylow of H is a p-Sylow of G ( since gcd(n,[G:H])=1 ) and reciprocally every p-Sylow of G (where p divides n) must be conjugated with a p-Sylow of H. But then it must be contained in H (since H is normal). That means every p-Sylow of H' (H' is any group of G of cardinal n) must be contained in H. In particular if n = p_1^k_1* ... *p_n^k_n, then each p_i^k_i divides $H \cap H'$ ...  which I am not sure it's correct, but it is definitely not elementary.

bye

Hi,

A more direct proof:
Let F be the morphism from G to G/H and let K be a subgroup of G with |K|=|H|.
Then F(K) is a subgroup of G/H and |F(K)| is a divisor of |K| and of |G/H|. Thus |F(K)|=1 and K=H.

Friendly,
Georges

Hello Georgres,

That's a very short proof indeed; glad to see you eventually decided to have a look at the forum and become a member !!!

@+

Julien


probability
calculus
symmetry
algebra unsolved
algebra

You have two jars, 50 red marbles, 50 blue marbles. You need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. (when picking, you'll first randomly pick a jar, and then randomly pick a marble out of that jar) You can arrange the marbles however you like, but each marble must be in a jar.

It is some what intuitive that if we put just one red marble in one of the jars and remaining 49 red and 50 blue marbles in the other jar, we get the maximum probability \[ \frac{1}{2}*(\frac{1}{1} \plus{} \frac{49}{99})\]. Can some one prove this claim or give a proof of optimal case.

Did you try to use calculus? Set $ f(k,l)$ to be the probability you want to maximize in terms of
$ k$, the number of red marbles in the first jar, and $ l$ the number of blue marbles in the first jar.
You can do it with $ n$ instead of 50 marbles, and assume by symmetry that $ k \le n/2$.
It shouldn't be too difficult to maximize $ f$ for fixed $ k$ with respect to $ l$, and afterwards
with respect to $ k$ with optimal $ l_k$. Maybe there is some ugly casework that has to be done,
but in principle it should work fine.

In one of the jars, the probability of pick a red marble will be smaller than $ 1/2$, since the number of red marbles is equals to the number of blue marbles (both probabilities will be $ 1/2$ if the number of blue marbles is equals to the number of red marbles in each of the jars, but this case gives probability $ 1/2$, which is smaller than our conjectured answer). Being smaller than $ 1/2$, the maximum possible value of this probability is $ 49/99$. The other probability clearly has maximum $ 1$.


inequalities
trigonometry
geometry proposed
geometry

[color=purple] Let triangle $ ABC$ in plane and M is an arbitrary point.Denote $ r_{a},r_{b},r_{c}$ are three exradii. Prove that :
  $ \frac{MA}{r_{a}}\plus{}\frac{MB}{r_{b}}\plus{}\frac{MC}{r_{c}}\ge 2$
  Easy or not ?  :D  :) [/color]

[hide="maybe a start"] $ \frac{MA}{\tan \frac{A}{2}}+\frac{MB}{\tan \frac{B}{2}}+\frac{MC}{\tan \frac{C}{2}}\geq 2p$ $ \implies$ $ \frac{MA\tan \frac{B}{2}\tan \frac{C}{2}+MB\tan\frac{A}{2}\tan\frac{C}{2}+MC\tan\frac{A}{2}\tan\frac{B}{2}}{\tan\frac{B}{2}\tan\frac{A}{2}\tan\frac{C}{2}}\geq 2p$ and it is know that

 $ \|\begin{array}{cccc}\tan\frac{B}{2}\tan\frac{A}{2}\tan\frac{C}{2}=\frac{r}{p}\\
\\
\tan \frac{B}{2}\tan \frac{C}{2}+\tan\frac{A}{2}\tan\frac{C}{2}+\tan\frac{A}{2}\tan\frac{B}{2}=1\end{array}$[/hide]


How can I prove that $x=30$ "exactly" is the solution of the following equation?

$\frac{\sin(54-x)}{sinx}={\frac{\sin54}{sin84}}$

All I've been able to find is $x=arctan{\frac{\sin84sin54}{sin54+sin84cos54}}{\simeq}30$

Thanks and regards.

You want to prove that $\sin24 \sin 84=\sin 30 \sin 54$ and this is equivalent to $2 \sin24 \sin 84=\sin 54$ or $\cos 60-\cos 108= \sin54$.
Now $\frac{1}{2}= 1-2 \sin^{2}{54}+\sin54$.
The equation $2x^{2}-x-\frac{1}{2}= 0$ has for positive solution $x=\frac{\sqrt5+1}{2}$ and this is exactly $\sin54=\sin \frac{3\pi}{10}$.
I tried to solve the original equation but failed. Maybe you should post it this way ( I mean Solve )
Also such type of equations appear when trying to solve a geometry problem with sine theoreme. If this is the case post the geometry problem.

I believe you should go with delta's method.
I got the relation,
cot x - cot 54 = cosec 84

didn't follow up, see if it gets you anywhere.

It is $\cos 60^\circ-\cos108^\circ=\sqrt{3}\sin54^\circ\implies \frac{1}{2}+\cos 72^\circ = \sqrt{3}\sin54^\circ$

Note that: $54 = 36+18, 72 = 2\cdot36$ and that $\cos 18^\circ = \frac{\sqrt{10+2\sqrt{5}}}{4}, \sin 18^\circ=\frac{\sqrt{5}-1}{4}$

The equation could be written like that:

$\frac{1}{2}+\cos (2\cdot36^\circ)=\sqrt{3}\sin (36^\circ+18^\circ)\implies\ldots$

All the trigonometric numbers are known, so it's a matter of calculations now..

Thanks for the answers and please excuse me for my late reply. Happy new year.


Solve the recurence \[a_{n+1}= \sum_{k = 0}^{n}{\binom{n}{k}}{a_{k}}a_{n-k}\] depending on $a_{0}$

1) This has nothing to do with complex analysis.
2) This is not, in fact, very hard: calculating the first 4 terms makes the general form clear, and induction polishes it off.

JBL I undersand that for you is easy ,but for me ,how I said is hard ,so would someone be so kindly to show me how can it be solved.Thanks

[quote="silviu"]would someone be so kindly to show me how can it be solved.[/quote]

[quote="JBL"]calculating the first 4 terms makes the general form clear, and induction polishes it off.[/quote]

If a moderator could move this to a more appropriate forum (Pre-Olympiad?  Intermediate?), that would be nice.

I might as well add:

There are other ways to look at this.  In particular, the expression on the right is the binomial convolution of $\{a_{i}\}$ with itself, which suggests that we might define the exponential generating function

$A(x) = \sum_{n = 0}^\infty \frac{a_{n}x^{n}}{n!}$,

and then the given relation implies $A'(x) = A(x)^{2}$, which leads to $A(x) = \frac{c}{1-cx}$ and thus to the result.


geometric transformation
geometry
homothety
cyclic quadrilateral
geometry proposed

The circles $W_1, W_2, W_3$ in the plane are pairwise externally tangent to each other. Let $P_1$ be the point of tangency between circles $W_1$ and $W_3$, and let $P_2$ be the point of tangency between circles $W_2$ and $W_3$. $A$ and $B$, both different from $P_1$ and $P_2$, are points on $W_3$ such that $AB$ is a diameter of $W_3$. Line $AP_1$ intersects $W_1$ again at $X$, line $BP_2$ intersects $W_2$ again at $Y$, and lines $AP_2$ and $BP_1$ intersect at $Z$. Prove that $X, Y$, and $Z$ are collinear.

Let $ B',A'$ denote the 2nd intersections of $ BP_1$ and $ AP_2$ with $ \omega_1$ and $ \omega_2.$ Since $ P_1$ and $ P_2$ are insimilicenters of $ \omega_1 \sim \omega_3$ and $ \omega_2 \sim \omega_3,$ it follows that $ AB \parallel XB' \parallel YA'.$ If $ a,b$ denote the tangents of $ \omega_3$ at $A,B$ and $a',b'$ the tangents of $\omega_2,\omega_1$ at $ A',B',$ we have $ a \parallel a' , b \parallel b'.$ Since $ a \parallel b,$ then $ a' \parallel b'$ $\Longrightarrow$ $ b'$ is image of $ a'$ through the negative homothety that takes $ \omega_1$ into $\omega_2$ $ \Longrightarrow$ $ A',B',P_3$ are collinear. $ B'X,A'Y$ are diameters of $ \omega_1$ and $ \omega_2$ $\Longrightarrow$ $X,Y$ lie on  perpendicular to $ A'B'$ through $ P_3.$ From cyclic quadrilateral $ ABP_2P_1,$  we get

$ \angle ABP_1 \equal{} \angle BB'X \equal{} \angle AP_2P_1 \ , \ \angle BAP_2 \equal{} \angle AA'Y \equal{} \angle BP_1P_2$

On the other hand, from the cyclic quadrilaterals $ P_1P_3XB',$ $ P_2YP_3A'$ we get $ \angle P_1P_3Y \equal{} \angle BB'X,$ $\angle P_2P_3Y \equal{} \angle AA'Y $ $ \Longrightarrow$ $ \angle P_2P_3P_1 \equal{} \angle AP_2P_1 \plus{} \angle BP_1P_2$ $\Longrightarrow$ $ZP_2P_3P_1$ is cyclic. Since $ \angle P_2P_3Y \equal{} \angle ZP_1P_2,$ then $ YX$ is identical with the diagonal $ ZP_3$ of the quadrilateral $ ZP_2P_3P_1,$ i.e. $ X,Y,Z$ are collinear.


ratio
quadratics
algebra
quadratic formula

1)Solve for x: 12abx2 — (9a2 — 8b2) x - 6ab = 0
2)
$ {\rm{If the ratio of the roots of equation, }}lx^2 {\rm{ }} \plus{} {\rm{ }}mx{\rm{ }} \plus{} {\rm{ }}m{\rm{ }} \equal{} {\rm{ }}0{\rm{, is }}p: q{\rm{ prove that: }}\sqrt {\frac{p}{q}}  \plus{} \sqrt {\frac{q}{p}}  \plus{} \sqrt {\frac{m}{l}}  \equal{} 0$
3)Q.4 Using the quadratic formula, solve the equation:
         a2b2x2 – (4b4 – 3a4)x – 12a2b2 = 0
4)
\[ \left( {x \minus{} \frac{1}{x}} \right)^2  \plus{} 8\left( {x \plus{} \frac{1}{x}} \right) \minus{} 29 \equal{} 0
\]

[quote="sanbittu"]1)Solve for x: 12abx^2 — (9a^2 — 8b^2) x - 6ab = 0
2)
$ {\rm{If the ratio of the roots of equation, }}lx^2 {\rm{ }} \plus{} {\rm{ }}mx{\rm{ }} \plus{} {\rm{ }}m{\rm{ }} \equal{} {\rm{ }}0{\rm{, is }}p: q{\rm{ prove that: }}\sqrt {\frac {p}{q}} \plus{} \sqrt {\frac {q}{p}} \plus{} \sqrt {\frac {m}{l}} \equal{} 0$
3)Q.4 Using the quadratic formula, solve the equation:
         a^2b^2x^2 – (4b^4 – 3a^4)x – 12a^2b^2 = 0
4)
\[ \left( {x \minus{} \frac {1}{x}} \right)^2 \plus{} 8\left( {x \plus{} \frac {1}{x}} \right) \minus{} 29 \equal{} 0
\]
[/quote]
1.$ \Delta_x \equal{} (9a^2 \minus{} 8b^2)^2 \plus{} 4.12.6ab \equal{} (9a^2 \plus{} 8b^2)^2$
It follows that:
$ x \equal{} \frac {9a^2 \minus{} 8b^2 \plus{} 9a^2 \plus{} 8b^2}{24ab} \equal{} \frac {3a}{4b}$
or $ x \equal{} \frac {9a^2 \minus{} 8b^2 \minus{} (9a^2 \plus{} 8b^2)}{24ab} \equal{} \frac { \minus{} 2b}{3a}$
3.Similarly, we have: $ x \equal{} \frac {4b^2}{a^2}$ or $ x \equal{} \frac { \minus{} 3a^2}{b^2}$

4)
$ \left({x\minus{}\frac{1}{x}}\right)^2\plus{}8\left({x\plus{}\frac{1}{x}}\right)\minus{}29\equal{}0 \Rightarrow x^2\minus{}2\plus{}\frac{1}{x^2}\plus{}8x\plus{}\frac{8}{x}\minus{}29\equal{}0$
Multily by $ x^2$

$ x^4\plus{}8x^3\minus{}31x^2\plus{}8x\plus{}1\equal{}0$
$ (x^2\minus{}3x\plus{}1)(x^2\plus{}11x\plus{}1)\equal{}0$
$ x^2\minus{}3x\plus{}1\equal{}0 \Rightarrow \boxed {x\equal{}\frac{3\pm \sqrt{5}}{2}}$
$ x^2\plus{}11x\plus{}1\equal{}0 \Rightarrow \boxed {x\equal{}\frac{\minus{}11\pm 3\sqrt{13}}{2}}$


For what integers $ n\ge 3$ is it possible to accommodate, in some order, the numbers $ 1,2,\cdots, n$ in a circular form such that every number divides the sum of the next two numbers, in a clockwise direction?

[hide]$ n\equal{}3$ obviously works for any permutation we choose. We now show no other $ n$ can work.

Let us draw out sections of the circular form linearly, with the understanding that the rightward direction corresponds to a clockwise direction on the circle, and that E represents an even number, while O represents an odd number.

Suppose there were two even numbers next to each other: EE_
Then the next number (clockwise) could not be odd (EEO), for we can not have an even number divide the sum of an even number and an odd number. Thus, the next number must be even. (EEE) Similarly, the following number must also be even, and so on (EEEE...), giving a clear contradiction.

Now consider an even number. It must be surrounded by odds on both sides: OEO
The arrangment EOE is impossible, since the sum of the two rightmost numbers is odd, and an even number cannot divide it. Thus, we cannot have E on the left or the right of OEO; that is, it must be arranged OOEOO, so the two number preceeding and succeding an even number must be odd.

For any even number, consider how many odd numbers are between that number and the next even number (clockwise). Our analysis shows that this number is at least 2. Thus, there are at least twice as many odds as there are evens. This is impossible for any $ n$ except 3, so we are done.[/hide]

[size=100]See that we can't have two evens together because in that case they all will have to be even, so if we have an even it w'd have to be [color=#FF0000]odd[/color]-[color=#0000FF]even[/color]-[color=#FF0000]odd[/color] and from this we can deduce the parity of the next and the previous, something like this:
[color=#FF0000]odd[/color]-[color=#FF0000]odd[/color]-[color=#0000FF]even[/color]-[color=#FF0000]odd[/color]-[color=#FF0000]odd[/color] from this we conclude that for every even we will have at least $2$ odds, if $n=2d$ there are $d$ odds and $d$ evens, so $n$ can't be even, if $n=2d+1$ there are $d$ evens and $d+1$ odds, from this last conclutions we have $d+1 \ge 2d$ thus $1 \ge d$ so $d=1$ and $n=3$.[/size]


Is there $f$ defined on $[0,1]$ with real numbers such that the preimage of any compact interval is never measurable?

Here's a possible construction:

Let $H$ be a Hamel basis of $\mathbb R$ over $\mathbb Q$, and fix some $h_{0}\in H$. Let $V$ be $\mathbb Q$-subspace of $\mathbb R$ with basis $H-\{h_{0}\}$, and let $W$ be its complement in $\mathbb R$ with basis $h_{0}$. Define $f$ to be the projection on $V$ along $W$ (in other words, if $x=\sum_{h\in H}x_{h}h,\ x_{h}\in\mathbb Q$, then $f(x)=\sum_{h\in H-\{h_{0}\}}x_{h}h$).

If $I$ is a bounded interval, then the countable union $\bigcup_{p,q\in\mathbb Q}(ph_{0}+qf^{-1}(I))$ is $\mathbb R$, so $f^{-1}(I)$ can't have measure zero $(*)$. On the other hand, let's look at the set $f^{-1}(I)+f^{-1}(I)$. Its image through $f$ is contained in $I+I$ and hence is bounded, but it's easy to see that the image through $f$ of an interval is dense in $\mathbb R$. This means that $f^{-1}(I)+f^{-1}(I)$ cannot contain an interval, so it's not measurable with positive measure. Together with $(*)$, this proves that $f$ does indeed have the required property.


Let $\epsilon$ be in $(0,1)$ and $n$ in $N^{*}$. We consider $n$ postive ral numbers $x_{1}, \ldots ,x_{n}$ such that:

$\forall (i,j) \in{1,\ldots ,n}^{2}, x_{i}x_{j}\leq \epsilon^{|i-j|}.$

Show that:

$\sum_{i=1}^{n}{x_{i}}\leq\frac{1}{1-\sqrt{\epsilon}}$

Hint:
For every integer $k$,there is at most $k$ numbers of $x_{1},x_{2},\cdots,x_{n}$ $\ge$ $(\sqrt{\epsilon})^{k}$ :D


These are just cool problems we came across in the Introductory Number Theory final challenge for 2006:

1) Prove that with fourteen integers, $a_{1}, a_{2}, a_{3}, ..., a_{14}$, that $a_{1}^{4}+a_{2}^{4}+a_{3}^{4}+...+a_{14}^{4}$ cannot ever equal 9999.

2) Prove that with integers, a, b, and c, that $a^{2}+b^{2}+c^{2}$ cannot equal $a^{2}c^{2}$.

[quote="junggi"] this repeats on and on, and the $a_{i}$s get smaller and smaller infinitly, so they can't be integers[/quote]

I'm pretty sure this situation is called "Infinite Descent". (right?)  :)

Yep.

[hide="Alternate solution"] $(a^{2}-1)(c^{2}-1) = b^{2}+1$

If $b$ is even, then $a, c$ are even so of $a-1, a+1, c-1, c+1$ two must be $\equiv 3 \bmod 4$, but such numbers cannot divide $b^{2}+1$, contradiction.

If $b$ is odd, then one of $a, c$ is odd so the LHS is $\equiv 0 \bmod 4$ but the RHS is $\equiv 1 \bmod 4$, contradiction. [/hide]

[quote="srulikbd"]without checking all the possibilites?[/quote]
It isn't hard. Notice that fourth powers of even numbers are divisible by $16$ and for any $x$ we have $x^{4}\equiv (16-x)^{4}\pmod{16}$, so we only have to check $1,3,5,7$ and it's easy.

[quote="srulikbd"][quote="junggi"][hide="1"]
$a_{1}^{4}+\cdots+a_{14}^{4}=9999$
$a_{1}^{4}+\cdots+a_{14}^{4}=15\mod16$
but all fourths are $=0,1\mod16$ so contradiction[/hide]
[hide="2, actually it can be equal, but they would all be 0."]
WLOG they are all positive
$a^{2}+b^{2}+c^{2}=a^{2}c^{2}\mod4$
$x^{2}$ is 1 mod 4 when x is odd, and 0 mod 4 when even.
if all are odd, $1+1+1=1$, contradiction. so one is even
WLOG let a=even.
$0+b^{2}+c^{2}=0\mod4$ so all must be even
so substitute, $a=2a_{1},b=2b_{1},c=2c_{1}$
so $4a_{1}^{2}+4b_{1}^{2}+4c_{1}^{2}=16a^{2}_{1}c^{2}+1$
$a_{1}^{2}+b^{2}_{1}+c^{2}_{1}=4a^{2}_{1}c^{2}_{1}$
$a_{1}^{2}+b^{2}_{1}+c^{2}_{1}=0\mod4$
so again they are all even.
this repeats on and on, and the $a_{i}$s get smaller and smaller infinitly, so they can't be integers. so contradiction, and $(a,b,c)=(0,0,0)$ is onkly solution
[/hide][/quote]
for Q1, how do you get all fourths are $=0,1\mod16$ so contradiction? (without checking all the possibilites?)[/quote]

Or if you know the fermat-Eular theorem...

[quote="seamusoboyle"]Or if you know the fermat-Eular theorem...[/quote]
Doesn't suffice.
But it's always good to know the structure of prime residue classes, not depending on such weak theorems.

Well if you assume its obvious for even numbers...


function
limit
real analysis
real analysis unsolved

[quote="stergiu"][color=red][b] True or false ?[/b][/color]

 If function $ f$ is continuous on $ [a,b]$ with $ f(a) \equal{} f(b) \equal{} 0$ and between any two roots of $ f$ , there is at least one more root of $ f$, then $ f$ is constant on the interval $ [a,b]$.

[i]Please give an answer as much more simple  as possible(for school use, if possible).[/i]
Thanks in advance - Babis[/quote]
I will give it a shot :)
Assume there exists $ c,d \in [a;b]$  such that $ f(x) \neq 0$ when $ x \in (c;d)$. But then $ f(c) \equal{} f(d) \equal{} 0$, and there is exists $ r \in (c;d)$ such that $ f(r) \equal{} 0$. So there is no open interval $ (c;d)$ such that $ f(x) \neq 0, \forall x \in (c;d)$. And so $ f(x) \equal{} 0, \forall x \in [a;b]$ because of the contiunity. QED

[quote="stergiu"]Dear Mathias, thank you for trying the problem. But I'm afraid that your solution needs more details. I think that we must begin with the asumption : Let$ m$ with $ f(m)$ different from $ 0$ and to find an absurd.But this is not done in the above solution
  Babis[/quote]
Dear Babis,
I will try to clarify :)
Assume there exists $ r \in [a;b]$ such that $ f(r) \neq 0$. Then there would exist a interval $ (c;d)$ (with $ c,d \in [a;b]$) such that $ f(x) \neq 0 \forall x \in (c;d)$ (Because of continuity) But we have proven that no such interval exists! Contradiction. So our assumption was wrong and there exist no $ r$ such that $ f(r) \neq 0$ when $ r \in [a;b]$. (Or $ f(x) \equal{} 0 \forall x \in [a;b]$)

[quote="marshell"]Assume that there exists a real number $ x_0$ such that: $ f(x)\neq 0$ (Assume that f(x)>0)

Because of the continuity of f(x) there exists an interval $ [c;d]$ such that $ f(x) > 0\forall x\in [c;d]$ (1)

Define $ A \equal{} \{ x\in [a;b]|f(x) \equal{} 0 ; x < c\}$ ; $ B \equal{} \{ x\in [a;b]|f(x) \equal{} 0 ; x > d\}$

So there exists $ \sup A \equal{} c_1$(2) and $ \inf B \equal{} d_1$ (3): $ f(c_1) \equal{} f(d_1) \equal{} 0$. By the hypothesis, there exists $ m\in (c_1;d_1)$ such that: f(m)=0

m cannot be in ][c;d] because (1) and it cannot be in [c1;c) and (d;d1] because (2) and (3) -> contraction[/quote]

 Thank you :)  !
This was also my first approach , but I had  - and have still - this  question.: Why must we have ,  for example ,

$ f(c_1) \equal{} 0$ ? Has   $ \sup A$  the same property with  $ x's$ in $ A$ ? But I'm thinking - by looking just now at your

solution carefully -that we have two possibilities : If $ A$ is finite or if $ c_1 \in A$, then it is clear that $ f(c_1) \equal{} 0$. If $ A$ is infinite and does not contain $ c_1$, then

$ c_1$must be an acumulation point of $ A$.But then we can find a sequence $ a_n$ in $ A$ with  $ \lim {a_n} \equal{} c_1$.Since

$ f$ is continuous, we must have that $ \lim f({a_n}) \equal{} f(c_1)$ But

  $ f(a_n) \equal{} 0$ , so $ f(c_1) \equal{} 0$.

  Well , if the above steps  are correct, then I think that the solution is complete .But is really $ c_1$ a point of acumulation of $ A$ ?My intuition says YES !

 Babis

The set of zeroes of a continuous function is closed.  ($ f^{\minus{}1}$ takes closed sets to closed sets, and $ \{0\}$ is closed.)  Thus its complement is open and so is a union of open intervals or empty.  Suppose not empty.  Then choose one of these intervals, say $ (m, n)$ for some $ m$ and $ n$.  But then $ m, n$ are zeroes of $ f$ with no zero between them, a contradiction, so the complement of the zeroes must actually be empty and $ f$ is the zero function.


function
limit
inequalities
real analysis
real analysis unsolved

If $f: (a,b)\longrightarrow \mathbb R$ is a function s.t. the limit $\lim_{x\nearrow x_{0}}\frac{f(x)-f(x_{0})}{x-x_{0}}$ exists and is finite $\forall x_{0}\in (a,b)$ and the function $g: (a,b)\longrightarrow \mathbb R$, $g(y)=\lim_{x\nearrow y}\frac{f(x)-f(y)}{x-y}$ is increasing, prove that $f$ is convex.

No answer?  :(  Is it too easy? Or the problem is incorrectly stated?

A counterexample: $f(x)=x^{2}$ for $x\le 0$, $f(x)=x^{2}+1$ for $x>0$.

Let's assume in addition that $f$ is continuous. If $f$ is not convex, then there exist numbers $a<c<b$ such that the point $(c,f(c))$ lies above the line passing through $(a,f(a))$ and $(b,f(b))$. Let $y=mx+s$ be the equation of this line. The function $\tilde f(x)=f(x)-mx-s$ also satisfies the assumptions of the problem (with $\tilde g=g-m$ in place of $g$). Since $\tilde f(a)=\tilde f(b)=0$ and $\tilde f(c)>0$, it follows that $\tilde f$ attains its maximum at some point $d\in(a,b)$. Clearly $\tilde g(d)\ge 0$, which implies $\tilde g(x)\ge 0$ for all $x\ge d$. This will be hard to reconcile with the inequality $\tilde f(b)<\tilde f(d)$.


I'm training for MathCounts, and I kinda want to come in the top 12 in Nationals. So, I'll be posting like crazy here. I'll definitely still spoiler post, obviously, but you'll just see pages saying "Last post by: Treething".

I'm just saying that I'm not trying to spam to increase my post count.

Other middle-schoolers are encouraged to stop me from dominating *cough* be active here too :P .

[quote="Treething"]Other middle-schoolers are encouraged to stop me from dominating *cough* be active here too :P .[/quote]I also encourage this :)

[quote="paganinio"]it may work
take myself as example, I do want to reply every problem I see, but 80% of them are too difficult to me, so I don't have the Ability to post like crazy, since he has that ability, he must be good at math
if he wins some awards, even interviewed by some media, he should promote our AoPS then.[/quote]

Lol :P .

General Pinochet comes to mind, but that's a little too severe ;P .

Okay.

I will also be posting like crazy, except not in this forum.

But yes, good luck Treething.

[quote="Treething"][quote="cj"][quote="Treething"]I'm training for MathCounts, and I kinda want to come in the top 12 in Nationals. So, I'll be posting like crazy here. [/quote]

Are you sure your way "posting like crazy" will work (make you in the top12)? Could you please PM me after May this year if it works.  I will do the same thing (posting like crazy) next year. :D[/quote]

Anu reminded me about this post.

It did.[/quote]

He said "this year" it is already "next year"

Good luck making the top twelve at nats :roll:

[quote="mathgeniuse^ln(x)"]Speaking of New Jersey, anyone from New Jersey have a chance?[/quote]
Who was speaking of new jersey?

NO one was, but treething is from New Jersey.


How many different ways can 36 identical chairs be placed in rows
if all rows have the same number of chairs, each chair is in exactly
one row, and no row has more than 20 chairs or less than 3 chairs?

This problem wants the number of factors of 36, such that the factor is greater than 3 and less than 20. Counting you get 4 ways

HUh, you forgot to count 3, so the answer is 5.


[quote="L_Euler"]Solve that equation of system:

$ \left\{\begin{array}{l} x \plus{} \frac {{2xy}}{{\sqrt [3]{{x^2 \minus{} 2x \plus{} 9}}}} \equal{} x^2 \plus{} y \\
y \plus{} \frac {{2xy}}{{\sqrt [3]{{y^2 \minus{} 2y \plus{} 9}}}} \equal{} y^2 \plus{} x \\
\end{array} \right.$[/quote]
Can you prove that $ x \equal{} y$!! :wink:

[quote="pbornsztein"][quote="L_Euler"]
Can you prove that $ x \equal{} y \equal{} z$!! :wink:[/quote]

Seems difficult since there is no $ z$... :wink:

Pierre.[/quote]
Oh, I'm sorry, there isn't $ z$! :wink:

I think we should find $ x\equal{}0$ or $ y\equal{}0$ the first, and we are the root $ (0;0)$.

Thank for solving!! ^^


Find $ x,y\in\mathbb{R}$ such that
$ x|x|\plus{}y|y|\equal{}1$ and $ [[x]]\plus{}[[y]]\equal{}1$

What did you meant by the double square brackets $ [ [ \cdot ] ]$ ?

[quote="pqrs"]Find $ x,y\in\mathbb{R}$ such that
$ x|x| \plus{} y|y| \equal{} 1$ and $ [[x]] \plus{} [[y]] \equal{} 1$[/quote]

i believe the[[.]] were for misleading only :wink:  :wink:  :lol:  but the problem can be easily solved by plotting graphs.

$ [[x]]$ is a integer such that $ x\ge[[x]]>x\minus{}1$

I use [] for this.... $ x\ge[x]>x\minus{}1$, $ [x]$ is integer of cource

$ x\ge y$
$ 1)$
If $ y\ge 0$ that $ 2>x\ge 1$ and $ 1>y\ge 0$($ [x]\plus{}[y]\equal{}1$)
And
$ x|x|\plus{}y|y|\equal{}x^2\plus{}y^2\equal{}1$, but $ x\ge 1$. We have $ x\equal{}1$ and $ y\equal{}0$
$ 2)$
$ y<0$
$ [y]\equal{}\minus{}k (k>0)$
$ [x]\equal{}k\plus{}1$
{y}$ \equal{}a$($ 1>a\ge 0$)
{x}$ \equal{}b$($ 1>b\ge 0$)
$ (\minus{}k\plus{}a)(k\minus{}a)\plus{}(k\plus{}1\plus{}b)^2\equal{}1$, $ 1\plus{}b\equal{}s$, $ 2>s\ge 1$
$ \minus{}k^2\plus{}2ka\minus{}a^2\plus{}k^2\plus{}2ks\plus{}s^2\equal{}1$
$ 2(a\plus{}s)k\plus{}s^2\minus{}a^2\equal{}1$
$ (a\plus{}s)(2k\plus{}s\minus{}a)\equal{}1$
$ a\plus{}s\ge 1$
$ 2k\plus{}s\minus{}a<\equal{}1$
$ 1\ge 2k\plus{}s\minus{}a\ge 2k$
But it's not true, because $ k$ is integer and $ k\ge 1$
We have one solution $ (x,y)\equal{}(1,0)$, $ x\ge y$


[quote="perfectnumber628"]also, you used to be able to get to somebody's blog by viewing their profile, but now you can't.  will this be changed?[/quote]You can see the blog when you are viewing the topic, I forgot about the profile. I will fix it.

Speaking of the profile, could you add the online/offline status to a person's profile?

yes that would be a good idea. Also I noticed the online status thing does not always work properly, ie it says a user is online but he/she is actually not online...

[quote="rem"]Also I noticed the online status thing does not always work properly, ie it says a user is online but he/she is actually not online...[/quote]

I think that's because it's based on the last 5 minutes thing.

Added the new info to the profile of the users :)


I came up with this when doing another problem. It's almost definitely not new, but I couldn't find it with the search function.

Prove that $ [ABC]\equal{}\dfrac{(s\minus{}a)(s\minus{}b)(s\minus{}c)}{r}$.

[hide="solution"]It is well known that $ [ABC] \equal{} \sqrt{s(s\minus{}a)(s\minus{}b)(s\minus{}c)}$ (1) and that $ [ABC]\equal{}rs$ (2). So square (1) and divide by (2) and the desired result is obtained.[/hide]

hmmmm I didn't realize it would be that trivial...my solution was to note that $ \dfrac{s\minus{}a}{r}\equal{}\tan{\dfrac{A}{2}}$ (drop perpendiculars from I to the three sides, and draw AI,BI,CI) then to use the fact that $ \displaystyle\sum\tan{\dfrac{A}{2}}\tan{\dfrac{B}{2}}\equal{}1$ (proven easily by just substituting C=180-A-B). This gives $ r^{2}s\equal{}(s\minus{}a)(s\minus{}b)(s\minus{}c)$, so $ r[ABC]\equal{}(s\minus{}a)(s\minus{}b)(s\minus{}c)$, etc.

I guess this leads to a nicer proof of the aformentioned identity, which was the problem I mentioned in the original post.


function
number theory
prime numbers
algebra proposed
algebra

A function $ f: \mathbb{N} \rightarrow \mathbb{N}$ satisfies:
$ (a)$ $ f(ab)\equal{}f(a)f(b)$ whenever $ a$ and $ b$ are coprime;
$ (b)$ $ f(p\plus{}q)\equal{}f(p)\plus{}f(q)$ for all prime numbers $ p$ and $ q$.
Prove that $ f(2)\equal{}2,f(3)\equal{}3$ and $ f(1999)\equal{}1999.$

[quote="moldovan"]A function $ f: \mathbb{N} \rightarrow \mathbb{N}$ satisfies:
$ (a)$ $ f(ab) \equal{} f(a)f(b)$ whenever $ a$ and $ b$ are coprime;
$ (b)$ $ f(p \plus{} q) \equal{} f(p) \plus{} f(q)$ for all prime numbers $ p$ and $ q$.
Prove that $ f(2) \equal{} 2,f(3) \equal{} 3$ and $ f(1999) \equal{} 1999.$[/quote]

Let $ p$ an odd prime : $ 2,p$ coprime $ \implies$ $ f(2p)\equal{}f(2)f(p)$ but $ p$ prime $ \implies$ $ f(p\plus{}p)\equal{}f(p)\plus{}f(p)$ and so $ f(2)\equal{}2$

$ f(2\plus{}2)\equal{}2f(2)$ and so $ f(4)\equal{}4$
$ f(5)\equal{}f(3\plus{}2)\equal{}f(3)\plus{}f(2)\equal{}f(3)\plus{}2$
$ f(7)\equal{}f(5\plus{}2)\equal{}f(5)\plus{}f(2)\equal{}f(3)\plus{}4$

$ f(12)\equal{}f(3)f(4)\equal{}4f(3)$
$ f(12)\equal{}f(5\plus{}7)\equal{}f(5)\plus{}f(7)\equal{}2f(3)\plus{}6$

So $ 4f(3)\equal{}2f(3)\plus{}6$ and $ f(3)\equal{}3$ and so $ f(5)\equal{}5$ and $ f(7)\equal{}7$

$ 3$ and $ 5$ coprime $ \implies$ $ f(15)\equal{}f(3\times 5)\equal{}f(3)f(5)\equal{}15$
$ 13$ and $ 2$ primes $ \implies$ $ f(15)\equal{}f(13\plus{}2)\equal{}f(13)\plus{}f(2)$ $ \implies$ $ f(13)\equal{}13$
$ 11$ and $ 2$ primes $ \implies$ $ f(13)\equal{}f(11\plus{}2)\equal{}f(11)\plus{}f(2)$ $ \implies$ $ f(11)\equal{}11$
$ 11$ and $ 3$ coprime $ \implies$ $ f(33)\equal{}f(3\times 11)\equal{}f(3)f(11)\equal{}33$
$ 31$ and $ 2$ primes $ \implies$ $ f(33)\equal{}f(31\plus{}2)\equal{}f(31)\plus{}f(2)$ $ \implies$ $ f(31)\equal{}31$
$ 29$ and $ 2$ primes $ \implies$ $ f(31)\equal{}f(29\plus{}2)\equal{}f(29)\plus{}f(2)$ $ \implies$ $ f(29)\equal{}29$
$ 13$ and $ 2$ coprime $ \implies$ $ f(26)\equal{}f(2\times 13)\equal{}f(2)f(13)\equal{}26$
$ 23$ and $ 3$ primes $ \implies$ $ f(26)\equal{}f(23\plus{}3)\equal{}f(23)\plus{}f(3)\equal{}f(23)\plus{}3$ $ \implies$ $ f(23)\equal{}23$
$ 23$ and $ 29$ coprime $ \implies$ $ f(667)\equal{}f(23\times 29)\equal{}f(23)f(29)\equal{}667$
$ 667$ and $ 3$ coprime $ \implies$ $ f(2001)\equal{}f(3\times 667)\equal{}f(3)f(667)\equal{}2001$
$ 1999$ and $ 2$ primes $ \implies$ $ f(2001)\equal{}f(1999\plus{}2)\equal{}f(1999)\plus{}2$ $ \implies$ $ f(1999)\equal{}1999$


Hello, I was referred to this site by someone in my school, who said he visited here to sharpen and improve his problem solving skills. I didn't really care for it at the time, but now that school is about to start, I'm beginning to take things more seriously.

My parents usually push me to enter math contests and the like, but I haven't really had the confidence to enter them. I've tried the AMC 10, but I didn't do so well (I guessed on too many problems, which is a bad habit I have). On the last SAT practice test I took (8th grade), I scored a 580 in math. I'm hoping to fix all this by working much harder on my math skills.

I also am starting to feel that I may be beginning to struggle in math; most people in my class have also felt this way, and they all say its due to our merciless teacher. Whether this is the truth or not, I don't enjoy the feeling of struggling, so I've taken it to myself to improve, hopefully with the help of this site and books.

I am not very far ahead in the math classes at my school; I'm ahead only by one year. By my school district I'm considered gifted and above average, but I have a feeling that my district seems to be pretty lenient on those sort of titles. I'm going into 10th grade at my high school, which, at my school, means Algebra 2. My parents don't have the money to spend on a summer courses, but this site, as well as the Art of Problem Solving books, sound like a perfect alternative. As another alternative, I'm beginning to look into online courses.

I've looked at a few of the problems in this forum, and I've had difficulty solving a few of them, but I think it is because I haven't learned some of the necessary material. That will probably change as my high school education progresses.

The point to all this is that hopefully I will be able to enter math competitions and perform well in them, as well as do better in class, and maybe even on the SAT (College entrance exams). Do you think I'll be able achieve all this through visiting this site often for problems and tips, as well as reading through the Art of Problem Solving?

Thanks

THis is definitely a great place to be.  There are a lot of things happening on this site.  By the sounds of it you are perfect for the getting started forum.  I also suggest that you participate in Math Chat's.  Recently I have hosted them.  Usually they are on Friday's.  You need Aol INstant Messenger.  I have a thread on this in this forum... you can find more info there.

[quote="Startup"]Hello, I was referred to this site by someone in my school, who said he visited here to sharpen and improve his problem solving skills.[/quote]

Welcome aboard. This site is made for people like you and your classmate.

[quote="Startup"]I've tried the AMC 10, but I didn't do so well (I guessed on too many problems, which is a bad habit I have).[/quote]

A key "secret" for scoring better on the AMC 10 is to do exactly and ONLY the questions you are quite sure about. The penalty for guessing on the AMC 10 is severe, as is also true for the AMC 12. My son has told the story here on this site about following advice from JBL, another forum participant who is now a math major at Harvard, to do enough problems to score decently and then leave all other problems blank. My son did the first eighteen problems, all correctly, on the AMC 10 last year, and completely disregarded the last seven problems. His score (18*6 + 7*2.5=125.5) was enough to qualify him for the AIME and make him the state winner in Minnesota on the AMC 10B. It's important not to guess on the AMC 10 or AMC 12.

[quote="Startup"]I also am starting to feel that I may be beginning to struggle in math . . . . I don't enjoy the feeling of struggling, so I've taken it to myself to improve, hopefully with the help of this site and books.[/quote]

If you're willing to take the advice of a forty-six-year-old fuddy-duddy, I can advise that that feeling of struggling can be your friend, if you take it as a clue to not give up. Often people reach learning plateaus just before they break through to a higher level of understanding. I can't comment at all on how good your school math program is (and I homeschool my own children because I hardly trust any school program), but your plan now to add other sources of information to your set of learning resources is a VERY good idea. You may continue to struggle a while, but if you persist, then I think you will break through and reach a new, higher level of understanding, and enjoy the concepts that now cause your struggling. I learned this from my wife, a pianist and piano teacher, who often appeared to hit brick walls years ago while practicing piano but who persisted and now plays MUCH better than she did when I first met her. Don't give up.

[quote="Startup"]By my school district I'm considered gifted and above average, but I have a feeling that my district seems to be pretty lenient on those sort of titles. I'm going into 10th grade at my high school, which, at my school, means Algebra 2.[/quote]

I was considered "gifted" at a school in suburban Minneapolis that also offered algebra 2 as a tenth-grade class for its most advanced students. Later I met kids in Taiwan, and I mean AVERAGE kids in Taiwan, who learned that math at younger ages. In the United States, algebra 2 counts as a somewhat advanced math class for a tenth grader, but certainly not internationally.

[quote="Startup"]My parents don't have the money to spend on a summer courses, but this site, as well as the Art of Problem Solving books, sound like a perfect alternative. As another alternative, I'm beginning to look into online courses.[/quote]

We hammered our family budget this year by sending our son to a [url=http://www.jhu.edu/gifted/summer/catalogs/osmath.html]CTY summer program[/url], but no pain, no gain. My son also got a full scholarship to another summer program, but even the minimal out-of-pocket expenses we had from that program hurt our budget. If your family has a typical middle-class income, as mine does, you should qualify for SUBSTANTIAL financial aid from the [url=http://epgy.stanford.edu/courses/math/]EPGY distance learning programs[/url], which I highly recommend.

[quote="Startup"]I've looked at a few of the problems in this forum, and I've had difficulty solving a few of them, but I think it is because I haven't learned some of the necessary material. That will probably change as my high school education progresses.[/quote]

Yes, and we are also encouraging everyone to post more EASY problems on all the forums here, as there are many beginners (of various ages) who need more easy problems for practice.

[quote="Startup"]The point to all this is that hopefully I will be able to enter math competitions and perform well in them, as well as do better in class, and maybe even on the SAT (College entrance exams). Do you think I'll be able achieve all this through visiting this site often for problems and tips, as well as reading through the Art of Problem Solving?[/quote]

Using this site regularly, and reading the varied advice it has on study tips and taking tests, will surely be helpful. The Art of Problem Solving books are very good resources for a second, deeper look at most secondary school mathematics topics.

Enjoy the site. Good luck in your studies.

I'm actually in the same boat as you. I've never taken math seriously until now and am also going into the 10th grade. I hope to aim for the AIME as well.

I wish you the best of luck!

Just note that 15 years isn't too late; the mathematician Lagrange only took math seriously at 15 and I know one physicist who took it seriously only at age 20.

[quote="countersixte"][quote="Startup"]Do you think I'll be able achieve all this through visiting this site often for problems and tips, as well as reading through the Art of Problem Solving?[/quote]

No doubt about it.  :)  I haven't ever seen anything like AoPS before... It truly is amazing!  BTW, the classes here are excellent, too![/quote]

About several months ago, I did see something like AoPS, Mathlinks! Perhaps you could call the site AoPS-Mathlinks? :)

Hi!
[quote="Startup"]My parents usually push me to enter math contests and the like,[/quote]
My parents encouraged me to learn math ever since I first started school, and I think it really helped to get me where I am now. I scored well on the AMC8 and got invited to Mathpath. I think math contests and stuff is a good way to practice for future contests. Even if you don't do well you'll do better next time. Good Luck with math!! :)


Congratulations to all those who competed in the 2009 State Competition.

The WV State Winners / 2009 Team Members were:

Benjamin Taylor - 7       Ayscue Taylor Home School
Jennifer Yu - 8                Suncrest Middle School
Shiv Sunil - 8                 Suncrest Middle School
Michelle Ma - 8               Suncrest Middle School

Coach: Lois Swineford      Suncrest Middle School

Good Luck in Florida!!!

[quote="O M G"]Do you know the scores? Cause my teacher ain't telling me.[/quote]

I do not know the scores, I got the names off of the MATHCOUNTS site.  I am not of MATHCOUNTS level anymore, but I was a previous competitor for our state.  Actually, I'm the only competitor from the last few years that didn't come from Morgantown.

I don't know who you could contact about the scores, sorry...

Got any advice for me next year for mathcounts? Got 7th....

I'm guessing you are from Suncrest, so ask Ms. Swineford for all the help you can get and maybe even get some books from this site.

If you aren't from Suncrest, then ask your teacher for all the State or Nationals rounds he/she has.

Reading this, you can see how much it pays to go to Suncrest...lol

I rly didint "study" for the comp, idk how i made nats...gl tho next yr

So... you saw my post of some of the scores right?


Find all natural numbers $n$ such that the equation

$a_{n+1}x^2 - 2x\sqrt{a^2_{1} + a^2_{2} + ... + a^2_{n+1}} + a_{1} + a_{2} + ... + a_{n} = 0$

has real solutions for all real numbers $a_{1}, a_{2}, ..., a_{n+1}$.


[b]suggestion[/b]
use ineq Minkowski
( \sum (a_k-b_k) 2 ) 0.5 +( \sum (b_k-c_k)) 0.5  \geq ( \sum (c_k-a_k)) 0.5

In fact that is the solution:

apply Minkowsky to the cuples: (a1-b1,a2-b2,..,an-bn) and (b1-c1,..,bn-cn)

cheers! :D


Prove why does the equations n^2+n+41 and n^2-n+41?
not always give you a prime number??please show the steps

This is actually true of any integer-valued polynomial.  The proof is only slightly harder.

[quote="pythag011"][hide="hint"]substitute 41.[/hide][/quote]

This is the whole answer. A counterexample is enough in questions like this.

Please don't double post http://www.mathlinks.ro/viewtopic.php?p=1261945


If you want to find [tex]\sqrt{a + b\sqrt{c}}[/tex], for any real values of a, b and c (including negative for c), does the single method I read before work all the time?

It goes like

[tex]
\sqrt{a + b \sqrt{c})} = (r+s)

(a + b \sqrt{c}) = (r+s) = r + 2rs + s

so a = r + s

bc = rs
[/tex]

And solve with r and s roots of the quadratic equation
x + 2a + bc = 0 ?

I think... does this work for every real value of a, b and c?
And if I have this wrong, please tell me.. its new to me and I only remembered half the steps so I guestimated the rest. :lol:

eum could you please translate this in english? :?

what is ? and what is   ?? :?

Just displaying a square here...

I think this is a great problem in itself - trying to work out what it all means, so here goes:
Clue 1: ? and  only ever occur together so could stand for one symbol
Clue 2: "including negative for c" is relevant
Clue 3: ?(a + b?c) = (r+s) and then writes (a + b?c) = (r+s)
So I reckon ? is just  :sqrt: which means that the question is:
[quote]If you want to find [tex]\sqrt{a + b\sqrt{c}}[/tex], for any real values of a, b and c (including negative for c), does the single method I read before work all the time?[/quote]
Now it's up to mikewd to say if I am right or wrong  :)

PS Next problem: work out how ? came to be used

[quote="stevem"]PS Next problem: work out how ? came to be used[/quote]

Different character system/encoding (unicode vs. ANSI, maybe)?

therefor we got latex: $\sqrt{perfect\ square}=integer$

Oops! You are correct - it's a square root sign. Copied and pasted from microsoft word. It worked on another forum. Sorry for the confusion, I'll edit it.

edit (after correcting): latex is pretty handy actually!

[quote="mikewd"]$\sqrt{a + b \sqrt{c})} = (r+s)$
so $a = r + s$
and $bc = rs$[/quote]

no clue where you get that non-sense: $a=1, b=4, c=4, r=3/2, s=3/2$

the condition $\sqrt{1 + 4 \sqrt{4})} = ( \frac32 + \frac32 )$ is fulfilled

but $1 = \frac{18}4$ and $64 = \frac{81}{16}$ are luckily false :)

It would be true though IF $a,b,c,r,s$ are integers and $c$ is not a perfect square...

I think wanting to solve [tex]\sqrt{a+b\sqrt{c}} = r + s\sqrt{c}[/tex] That makes a bit more sense, and also gives [tex]a = r^2 + cs^2, b = 2rs[/tex], which looks like what mikewd was meaning.

Still, you're in trouble when c is a perfect square. And still, they need to be integers.


I don't understand the first part of their solution.
the first pic is the solution so be careful!!

They just applied the conjugation in $\mathbb{Z}\left[\sqrt{2}\right]$ to both sides.


Who made it on AoPS?

I just got my letter today. Woot! See you guys next school year!

i wish i could go there next year as a freshman...too bad i like like 2.5 hrs away :(

But oh well, if i went there, i wouldnt be considered "smart" since everyone's smart at TJ...but here, there arnt a lot of prob-solving smart people... :roll:


I just thought I'd get it started early this year, and go ahead and ask if they've graded the tests yet.....
Not actually.
But- is there any way to get scores on individual problems when they do release the scores? As far as I can tell, there isn't. Is there a philosophical reason for this? Does the CAMC just not want people second guessing them or posting scanned solutions and saying "I only got a 5 I can't believe it I should've made MOP"? Or is it something else?
Thanks

I don't believe so. However, it's generally pretty easy to tell what you got on a problem, since you'll almost always get a 0, 1, 6, or 7 on any given problem.

Hamster is going to get 7 on all problems and be the 2007 IMO perfect scorer!

Dang, I got a 3 last year...and i only answered one correctly another one had a completely incorrect answer...which i dont think they gave credit for or do they give credit for incorrect/incomplete solutions.

[quote="MysticTerminator"][quote="mrosett"]I just thought I'd get it started early this year, and go ahead and ask if they've graded the tests yet.....
Not actually.[/quote]

haha nice

also delong wtf?[/quote]

He made this prediction at mathcamp...apparently I'm also supposed to prove the Riemann Hypothesis.

In regard to your second question, which was kind of mixed up with the first, I quote the 2007 USAMO Teacher's Manual:

USAMO Winners and all those invited to the MOSP will be notified by telephone shortly after the [b]USAMO grading on May 4,5, & 6, 2007[/b]. Information regarding the MOSP will be sent to those selected beginning on [b]May 8th[/b]. A copy of the USAMO with solutions and results [including the score of your student(s)] will be mailed to you on [b]Wednesday, May 10rd[/b]. Also included will be a USAMO Certificate of Participation to be presented to your student(s). Students and teachers should not inquire about results before [b]Friday, May 11th[/b].

I like the "Wednesday, May 10rd" part.  Just try saying that.  It's quite amusing.  I also like "the MOSP".  Somehow "MOSP" never seems to need an article.

Isn't "May 10rd" a Thursday anyway? unless they are trying to trick us.

lol ya it is. I wonder where they think Thursday goes. Maybe we'll get warped into the 7th dimension and it will change all of our days around. Then by Friday it will be back to normal. (wait then I won't be able to fly to nats!)darn.

wow - that is kinda dumb.  i missed something else which was obvious:

Wednesday, May 10rd ... Friday May 11th

probably it is meant to be thursday may 10th, but they changed it from previous years and somebody at CAMC didn't check their grammar - that's why we're here though.

hey mr. dunbar (or whoever reads this first and has access to the AMCDirector account) care to comment?

EDIT: Also to AMCDirector - will this forum be closed for the USAMO?  I think I saw this asked somewhere else (maybe it was for AIME) but I assume it will...

[quote="Teki-Teki"]Also to AMCDirector - will this forum be closed for the USAMO?  I think I saw this asked somewhere else (maybe it was for AIME) but I assume it will...[/quote][url]http://www.artofproblemsolving.com/Forum/viewtopic.php?p=818495#818495[/url]

Luckily, since the USAMO is administered at the same time the forum doesn't [i]have [/i]to be closed until like 12:25PM EST tomorrow.

Olympiad scoring arithmetic is so awesome

----

A small, non-trivial correct step in a problem: 1 point
Two small non-trivial correct steps in a problem: 1 point

1 + 1 = 1

----

A correct solution: 7
A nearly correct solution with something small missing (like a trivial equality case): 6
Having only the said trivial equality case: 0

7 - 0 = 6

----


For a,b,c positive reals

$\frac {a^5+b^5+c^5}{5}+a^2bc^2\geq  ab^3c$


Find the smallest integer n with following property: do not exist prime with n digits.

No such $ n$ exists by [url=http://en.wikipedia.org/wiki/Bertrand%27s_postulate]Bertrand's postulate[/url].


If A is the sequence a1, a2, a3, ... , define ΔA to be the sequence a2 - a1, a3 - a2, a4 - a3, ... . If Δ(ΔA) has all terms 1 and a19 = a92 = 0, find a1.

Well, I just found this site a week or so ago, and after getting a good amount of AIME practice due to your posting problems, fiery, I guess I will post one of my solutions.  (which is probably wrong anyway)

[hide]

First, notice that the difference of the sequence  :tri: A is 1, so we can rewrite

 :tri: A_1=d

 :tri: A_2=d+1 ...etc

now since  :tri: A_n is the difference between the terms A_n and A_n+1, we can write the sequence:

A_1=A_1

A_2=A_1+d

A_3=A_1+2*d+1

A_4=A_1+3*d+2+1

A_n=A_1+(n-1)*d+(n-2)(n-1)/2

Setting this value equal for A_19 and A_92, D was equal to -54, and then putting this back into our equation for A_n for A_19, and then solving for A_1

A_19 = 0 = A_1+18*-54+(18)(17)/2

A_1 = 819

I can sort of see some ways of getting A_1 without solving for d (or  :tri: A_1), but this is the way in which i can "see" the solution best, where I am not doing any manipulations that I don't fully understand.

[/hide]

To everyone, thanks for posting all the practice AIME problems (and hints+solutions) in the last few days, they have been very helpful, and I will most definetly be back after the AIME tomorrow.  GL

Welcome to the forum GeoMar. Good job, your solution is correct. If you hang around here a lot, you oughta post a bit more. Its fun, and I've learned so much stuff on here just by being around smart people.


logarithms
search
inequalities
analytic geometry

1.Solve the following inequality. \[2\log_{a}(x-4)>\log_{a}(3x-8)\ (a>0,\ a\neq 1).\] 2. Explalin the meanimg of the real roots of the following equation. \[x^{2}=2^{x}.\] 3.Explain the meaning of the real roots of the following equation. \[(x-1)^{3}+1-a=0.\]

[hide="1"]
$log((x-4)^{2})>log(3x-8)$
$x^{2}-8x+16>3x-8$
$x^{2}-11x+24>0$
$(x-8)(x-3)>0$
Think about the graph

Answer: x<3 or x>8

[/hide]
Thanks, SplashD. The roots are 2, 4, and a negative irrational.
[/hide]
[hide="3"]
$(x-1)^{3}= a-1$
$x-1 = (a-1)^\frac{1}{3}$
$x = 1+(a-1)^\frac{1}{3}$
Again, don't know the meaning.
[/hide]

For number 2, x can also equal to 4 as well as a negative irrational that I don't know the exact value of

[quote="kunny"]2. Explalin the meanimg of the real roots of the following equation. \[x^{2}=2^{x}.\] [/quote]
We can see the obvious integer solutions, but I'm guessing the next best way to find the values of $x$ which satisfy this would be to set $f\left(x\right)=x^{2}-2^{x}$ and use Newton's Method to approximate the roots.

[quote="Altheman"][quote="vvr1590"]
$log((x-4)^{2})>log(3x-8)$
[/quote]

what if $\log a<0$?

[quote="kunny"]...
3.Explain the meaning of the real roots of the following equation.
[/quote]

I don't understand what you want when you say: "meaning."[/quote]

Sorry for my poor english, I ask you that what is the solution of equation on graphically.

kunny

Number 2 was discussed many times before, please search for it (I've searched for it, but without result, maybe the search tool is not working well)

#1

[hide]

Remember that you cannot take the log of a negative number, so x-4>0 and 3x-8>0, the intersection of these two inequalities being x>4.

For a>1:
x>8

For 0<a<1:
4<x<8

[/hide]

[hide="2"]$x^{2}= 2^{x}\Leftrightarrow \frac{\ln 2}{2}= \frac{\ln x}{x}$

We consider the graph of $f(x) = \frac{\ln x}{x}$ and draw a horizontal line at $(2, \frac{\ln 2}{2})$.  It intersects the graph at exactly one other point, the $x$-coordinate of which is our other solution. [/hide]


solve for all values of X:

tan ^3 X   - 9tan^2 X   - 3tanX   + 3 = 0

[hide="Solution"]
The equation is equivalent to $ tan^3x \minus{} 3tanx \equal{} 3(3tan^2x \minus{} 1)$ where we can easily figure out that the roots of the second part are not roots of the first one. Therefore, our next equivalent equation is the   $ \ \frac {tan^3x \minus{} 3tanx}{3tan^2x \minus{} 1} \equal{} 3$ or $ tan3x \equal{} 3$...
[/hide]


$ \boxed{1}$ $ a,\ b,\ c$ satisfy that $ a \plus{} b > c,\ b \plus{} c > a,\ c \plus{} a > b$.

(1) Prove that $ a > 0,\ b > 0,\ c > 0$.

(2) Prove that $ |b \minus{} c| < a,\ |c \minus{} a| < b,\ |a \minus{} b| < c$.

(3) Prove that $ 1\leq \frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} bc \plus{} ca} < 2.$

$ \boxed{2}$ Let $ S$ the area of the right triangle with the perimeter 1 and the hypotenuse $ t$ in length.

(1) Let $ a,\ b$ be the other two side lengths. Find the values of $ a \plus{} b,\ ab$ in terms of $ t$.

(2) Let $ t$ vary to move, find the range of $ S$ for which $ S$ can be valued.

For #1 part 1:
Suppose only c is negative. Then we have c>a-b and c>b-a, but one of a-b,b-a is positive (or 0), contradiction.
Suppose b and c are negative. Then b+c>a, contradiction.
Suppose all three are negative. Adding all three inequalities, we get a+b+c>0, contradiction.

For part 2, assume $ a \ge b \ge c$, then it is obvious, as the three are equivalent to the original three.

For part 3, it is equivalent to
$ 0 \le (a \minus{} b)^2 \plus{} (b \minus{} c)^2 \plus{} (c \minus{} a)^2 \le a^2 \plus{} b^2 \plus{} c^2$
The LHS is obvious. But for the RHS, we have -c<a-b<c, -a<b-c<a, -b<c-a<b

For #2 part 1:
Since a+b+t=1, a+b=1-t
$ (a \plus{} b)^2 \equal{} t^2 \minus{} 2t \plus{} 1 \equal{} a^2 \plus{} 2ab \plus{} b^2 \equal{} t^2 \plus{} 2ab$
$ ab \equal{} \frac {1 \minus{} 2t}{2}$

I have to go to school now!  :(

[hide="#1"](1) Add up the first two inequalities: $ a\plus{}2b\plus{}c>a\plus{}c\implies 2b>0\implies b>0$. Similarly for $ a>0, c>0$

(2) From the first inequality, $ a>c\minus{}b$, and from the third, $ a>b\minus{}c$. Therefore $ a>|b\minus{}c|$. Similarly for the remaining two.

(3) Use $ (a\minus{}b)^2\plus{}(b\minus{}c)^2\plus{}(c\minus{}a)^2\geqslant 0$, expand and rearrange to get $ a^2\plus{}b^2\plus{}c^2\geqslant ab\plus{}bc\plus{}ca$. Then use the result (2) to write $ (a\minus{}b)^2\plus{}(b\minus{}c)^2\plus{}(c\minus{}a)^2<c^2\plus{}a^2\plus{}b^2$, expand and simplify to get $ a^2\plus{}b^2\plus{}c^2<2(ab\plus{}bc\plus{}ca)$[/hide]

$ \boxed{2}$
[b](1)[/b] $ a\plus{}b\equal{}1\minus{}t$, also $ a^2\plus{}b^2\equal{}t^2 \Rightarrow 2ab\equal{}(1\minus{}t)^2\minus{}t^2\equal{}1\minus{}2t \Leftrightarrow ab\equal{}\minus{}t\plus{}\frac{1}{2}$
[b](2)[/b] We have $ \frac{1}{2}>t$, also
$ \frac{a^2\plus{}b^2}{2} \ge \frac{(a\plus{}b)^2}{4} \Leftrightarrow \sqrt{2}t \ge a\plus{}b$
$ \Leftrightarrow (\sqrt{2}\plus{}1)t \ge 1$

So $ \frac{1}{2}>t \ge \frac{1}{\sqrt{2}\plus{}1}\equal{}\sqrt{2}\minus{}1$ is the range of $ t$

$ \frac{1}{2}\minus{}(\sqrt{2}\minus{}1)\equal{}\frac{3}{2}\minus{}\sqrt{2} \ge ab >0$
$ \Leftrightarrow \frac{3\minus{}2\sqrt{2}}{4} \ge S >0$ is the range of $ S$

[color=blue]1st place: Mnjm   :winner_first:  :first:
2nd place: Iijm  :winner_second:
3rd place: Ski :winner_third: [/color]

$ \displaystyle \displaystyle \displaystyle \begin{tabular}{|c|c|c|c|c|c\parallel{}c|}\hline Name & Problem 1 & Problem 2 & Total Score \\
\hline Mnjm & 50 & 33 & 83 \\
\hline Iijm & 30 & 46 & 76 \\
\hline Ski & 50 & 25 & 75 \\
\hline Average & 20.8 & 18.8 & 39.6 \\
\hline\end{tabular}$

Entry 55

sorry, i will not show the details because i have to be fast.
$ 1$:
1:
suppose it is not true and try arrive to an absurd.or use these: $ a\plus{}b>{c}$and $ b\plus{}c>{a}$.we´ll have that $ 2b\plus{}c>c$,so $ b>0$.

2:i think this is literally direct from the question  :)

3:$ ab\plus{}bc\plus{}ca<a^2\plus{}b^2\plus{}c^2$ comes from rerrangement inequality.the other part is item 2 (just square both sides from all of the inequalities to prove in iten 2 and sum them all) :)

Number 1, part 3,
$ MHS\minus{}RHS$
If I'm not mistaken, it can be factorized into
$ (\sqrt{a}\plus{}\sqrt{b}\plus{}\sqrt{c})(\sqrt{a}\plus{}\sqrt{b}\minus{}\sqrt{c})(\sqrt{a}\minus{}\sqrt{b}\plus{}\sqrt{c})(\minus{}\sqrt{a}\plus{}\sqrt{b}\plus{}\sqrt{c})>0$

This is true since we can assume $ a,b,c$ are the sides of a triangle.. :)


Suppose that $ n$ is a positive integer. Prove that there is a positive integer k for which $ (\sqrt{n}-1)^{n}=\sqrt{k}-\sqrt{k-1}$

I will disprove the problem statement.

Lets assume that the problem statement is true:

Let $ n = 1$

$ \Rightarrow (\sqrt{n}-1)^{n}= (\sqrt{1}-1)^{1}= 0$

$ \Rightarrow \sqrt{k}-\sqrt{k-1}= 0$

$ \Rightarrow \sqrt{k}= \sqrt{k-1}$

$ \Rightarrow k = k-1$

$ \Rightarrow 0 =-1$

This is a contradiction therefore the problem statement is false.

i think the problem is true for $ n>1$ though. but i don't have a solution yet.

Really? How so? Am I not understanding the problem?

Note that the LHS side increases without bound and the RHS starts at 1 and converges to zero...

In fact, let $ n = m^{2}, \; m \in \mathbb{Z}$. Then, the LHS is equal to $ (m-1)^{m^{2}}$, an integer.

$ \sqrt{k}-\sqrt{k-1}$ is an integer iff. $ k=1$, in which case it equals $ 1$.


Hey all,

I'm new to the board and have a quick question.

Where would I post anything related to Mathematical Reasoning, Induction, and Recursion?

Thank you,
Shamrock Hoax

:welcome:

Don't quote me on this, but I think probably High School Basics or Intermediate Topics would be your best bet.

Hello and welcome :wink:  to AOPS/MathLinks.

If you would like to see an overview of all the subforums here, click:
[url=http://www.mathlinks.ro/Forum/index.php]this link[/url]

Hello! I didn't want to make myself a new topic so are you okay iff i post this:
[url]http://www.claymath.org/millennium/[/url]
are there anyother things you can be on this forum?
this is sort of another newbie thing but i am not a newbie so i hope you are okay with me posting it....i second the, "Don't quote me on this, but I think probably High School Basics or Intermediate Topics would be your best bet." but cross out the don't quote me part...


geometry
perimeter
function
inequalities
number theory proposed
number theory

1) For any natural number n, (n \geq 3), let f(n) denote the number of congruent integer sided triangles with perimeter n
 (eg f(3)=1, f(4)=0,f(7)=2 ) .Show that
  a) f(1999) > f(1996)
  b) f(2000) = f(1997)

2) Show that there do not exists integers m and n such that
   m/n +  n+1/m =4

For (2):

We have m/n+n+1/m=4 iff m^2/mn+mn^2/mn+n/mn=4 iff m^2+mn^2+n=4mn iff m(m+n^2)=n(4m-1), thus m|n because (m,4m-1)=1. We have n=km, so m(m+k^2*m^2)=km(4m-1) iff m(1+mk^2)=k(4m-1), so m|k because (m,4m-1)=1, so k=am, so m(1+a^2*m^3)=am(4m-1) iff 1+a^2*m^3=a(4m-1), so a is 1, so 1+m^3=4m-1 iff 4m-m^3=2, so m|2, so m can only be 1, -1, 2, or -2. By checking all of these we see that there are no solutions.

Maybe there's something wrong here, because it seems too easy :)

For 1) :
More generally, we prove that f(n+3) = f(n) if n is odd, and f(n+3) > f(n) if n is even (and the triangles are supposed to be nondegenerated).

Let E(n) = {(a,b,c) / a,b,c integers, a \leq  b  \leq c, a+b > c}.
Then f(n) = |E|.

Let F the function defined on E(n) by F(a,b,c) = (a+1,b+1,c+1).
Clearly, F(a,b,c) belongs to E(n+3) and F is injective.
Thus equality or inequality between f(n) and f(n+3) will follows from that F is surjective or not.

- If n = 4q :
Then n+3 = 4q+3.
It's easy to see that (x,y,z) = (q+1, q+1, 2q+1) is in E(n+3). But (x-1,y-1,z-1) = (q,q,2q) is not in E(n). Thus, (x,y,z) is not in F(E(n)), which proves that F is not surjective.

- If n = 4q+2 :
Then n+3 = 4q+5, and we get the same conclusion as above with (x,y,z) = (q+1, q+2, 2q+2).

Thus f(n+3) > f(n) if n is even.

- if n is odd :
Let (x,y,z) in E(n+3). Let (a,b,c) = (x-1,y-1,z-1).
Clearly, a,b,c are integers such that a \leq b \leq c and a+b+c = n.
Since x+y > z and x,y,z are integers, we have x+y  \geq z+1.
If x+y = z + 1 then n+3 = x+y+z = 2z+1, which is impossible since n+3 is even. Then x+y > z+1, which leads to a+b > c.
It remains to prove that a  \geq 1, that is x \geq 2. Now suppose that x = 1. Then, from the triangular inequality, we have y > z - 1, that is y \geq z, since we are dealing with integers. Since y \leq z, we then have y = z. Thus n+3 = x + y + z = 1 + 2z, and we get the same contradiction as above. Thus x \geq 2, and (a,b,c) is in E(n), and F(a,b,c) = (x,y,z), which proves that F is surjective. Thus F is bijective from E(n) onto E(n+3) and f(n) = f(n+3).

Pierre.


How many negative bases exists in which all positive integral numbers can be expressed? (Negative bases work the same way as positive bases. For example, 562 in base -7 is 5*(-7):^2:+6*(-7)^1+2*(-7)^0=5*(49)+6*-7+2*1=205)

Easier Question: How many negative bases exists in which all integral numbers can be expressed?

Negative bases don't work very well in general because the representations for numbers aren't unique.

Yup, but that shouldn't be a problem...or will it?

Well, it can be. If I tell you to convert 43 to base -10, do I want you to write 163 or -57? It's not clear at all.

While it may be true (and I'm not quite sure since I think -57 in base -10 is just 57 in base 10), it shouldn't be a problem in this problem.

Oh, I thought it was (-5)7, not -(57), but oh well. Again, since the problem only ask if it [b]can [/b]be expressed, this shouldn't be a problem.


A set $M$ of positive integers is called [i]connected[/i] if for any element $x\in M$ at least one of the numbers $x-1,x+1$ is in $M$. Let $U_n$ be the number of the connected subsets of $\{1,2,\ldots,n\}$.

a) Compute $U_7$;

b) Find the smallest number $n$ such that $U_n \geq 2006$.

[hide]In other words, no number can be "isolated" (like in {2,3,5,8,9}, 9 is isolated.)
So U_n must consist of at least 2 elements.

For U7 there can be 2,3,4,5,6 or 7 elements.

2 - each one must be a pair, there are 6 sets.
3 - no isolation-- there must be a triplet, there are 5 sets.
4 - we can either have a string of 4 (4 sets), or two pairs (10 sets) = 14 sets.
5 - we can either have a 3-string and 2-string (6 sets), or a 5-string (3 sets) = 9 sets.
6 - if 2 or 6 were missing we would have isolations, this leaves us with 5 sets.
7 - 1 set.

6+5+14+9+5+1 = [b]40 sets. [/b]

Don't know #2 though :blush: [/hide]

[hide]Actually the answer is 37: there are only 6 connected subsets of ${1, \dots, 7}$ that consist of 2 separate pairs, but you forgot to count the null set, which is connected.

To give this post some semblance of constructivity, I'll remark that the smallest $n$ in the second part is 15; if I'm right in my computation, $U_{14} = 1897$ but $U_{15} = 3329$.[/hide]

It doesn't right from my point of view.
When you disscus about the numbers of 4-element sets, the two situations have something in common :!:

And I think the correct recursion should be Un=Un-1 +Un-2 +2

I got the answer U7=32, and 16 is the smallest number satisfies the request.

No.Here's an indication.Let's consider M={a,b,c,d} whith a<b<c<d.After the hypothesis, a-1 isn't in M, but then a+1 is in M.How a<b then b=a+1.The same thing for d.Because d+1 isn't in M, then d-1 is in M, but c<d, results
c=d-1.We have obtained M={a,a+1,d-1,d}.Now the problem is simple.We go directly to the generalisation.We see easly that the number of U(n) is (n-3)(n-2)/2.To find the smallest n we have to solve the inequation (n-3)(n-2)?>=2006, which gives n>=66.The answer is n=66.

Valentin, is the question perhaps misstated?  The previous poster solves a question you didn't ask, but one which is suggested by the title of the topic, namely where $U_n$ is the number of connected [i]4 element[/i] subsets of $\{1, 2, \ldots, n\}$.

(So far, by the way, Saul is the only person to give a correct calculation of $U_7$ as it is defined in the question.)

I don't think the Saul's solution is correct.How is Valentin? :?

Saul is definitely correct, given the current statement of the question.

In particular, the formula for the thing that the question currently asks is given by:

$1+\sum_{n=0}^m\sum_{i=0}^{\lfloor \frac n2\rfloor} {n-i-1 \choose i-1}\cdot{m-n+1 \choose i}$.

The process to get to this is to define a function $P_i(n)$, the number of ordered partitions of $n$ into $i$ parts, each at least size 2, which works out to be $n - i - 1 \choose i$, and the function $Q_i(k)$, the number of ordered partitions of $k$ into $i$ non-empty parts, which is $k+i-1 \choose i-1$.  The result comes from counting the subsets based on the shape and arrangement of their connected components.

I don't think so!I was at this olympiad and I took 7p for 7p(maximum) for this problem.Let's ask Valentin...

Read the question that Valentin has written here -- it is not the same question that you have solved in this thread!

Yo say about the problem, no?I've solved directly b)-find the smallest n such that U(n)>=2006 and this is n=66.

[quote="Altheman"]perhaps create a recursion for $U_n$[/quote]

[i]Is there anyone working along this line of attack?[/i]

Let M be any connected subset of {1,2,3....,n}

Case 1 $n \notin M$
Then M is a connected subset of {1,2,3,...,n-1}
There are $U_{n-1}$ cases.

Case 2 $n \in M$
Then it is necessary that $n-1 \in M$ also, for otherwise the number n will be isolated.
Basically, I think we need to consider a subset of the form $M=N \cup \{n-1,n\}$
Now, either  $N=P \cup \{n-2 \}$ with P being a connected subset of {1,2,...,n-4}, if N is [b]disconnected[/b], or else $N$ is any [b]connected[/b] subset of {1,2,...,n-2}.
Hence, there are $U_{n-4}+U_{n-2}$ ways of forming $M$ in this case.

Combine the results, $U_n =U_{n-1}+U_{n-2}+U_{n-4}$ for n >4.

Let us work out some cases for n:
$U_1=1$,
$U_2=2$,
$U_3=4$,
$U_4=7$,
$U_5=U_4+U_3+U_1=7+4+1=12$,
$U_6=U_5+U_4+U_2=12+7+2=21$, and
$U_7=U_6+U_5+U_3=21+12+4=37$ which is the same as Saul's result.

If this recurrsion is correct, then we may solve the problem in an easier way.  :idea:

With this recurrsion, I found that $U_{14}=1896$ and $U_{15}=3329$.
Therefore, the answer of this problem should be $n = 15$.

Is there anyone who knows the answer for checking?

JBL,
Thank you for your confirmation.
The value 1896 is a typing mistake.  hehehe  :lol:

[quote="JBL"]@stancioiu sorin:
Did you re-read the question as written?  Here is the definition of $U_n$ in the first post in this thread:
[quote="Valentin Vornicu"] Let $U_n$ be the number of the connected subsets of $\{1,2,\ldots,n\}$. [/quote]

You are solving a question which uses the following definition:
[quote="Not Valentin Vornicu"]Let $U_n$ be the number of [i]4-element[/i] connected subsets of $\{1,2,\ldots,n\}$. [/quote]

Do you understand?

@Luimichael:
Looks good to me!  Except that you wrote down 1896 when you should have written 1897.  These are also the values Saul gave and which my, much uglier, solution gives.[/quote]
   Yes, JBL, I've understood the mistake.But Vlaentin has changed the problem.When I solved this problem at the District Olympiad, M had this forme: M={a,b,c,d}-four integer numbers.That is[b] sure![/b]But, how I said, V.V has changed the problem;or he didn't read it correctly.


[quote="masum billal"]a^n+b^n=c^n isnt true for all even integers,say n=2p,then (a^p,b^p,c^p)is a pythagorean triple which are same exponent of different numbers which is impossible,can you prove this for odd numbers,then it will be proved totally[/quote]

What about n = 2, im sure $ 3^2 \plus{} 4^2 \equal{} 5^2$.

And i think that if it really was that simple to prove, then it would have been solved by Euler in the 18th century ;)

1) This isn't the forum for this

2) If the proof was that easy, Andrew Wiles wouldn't write hundreds of pages

3) There were many guesses and tries to prove it

4) kurt.math, I think you know that the LFT is for $ n>2$ :)

[quote="Bugi"]kurt.math, I think you know that the LFT is for $ n > 2$ :)[/quote]

I know :D lol


Find all monic polynomials P(x) and Q(x) with integer coefficients such that Q(0)=0 and P(Q(x))=(x - 1)(x - 2)(x - 3) ... (x - 15).

Hey! This is still unsolved. what's the matter?
     Ashwath

degP+degQ odd then
1, degP odd, degQ even. therefore the range of PQ is not R, the range of (x-1)..(x-15) is R
2. similarly.
=> there dont exist P and Q

Isn't $Q(X)=X$ and $P(x)=(x - 1)(x - 2)(x - 3) ... (x - 15)$ a solution nmtruong1986 ?

I guess this is the only one  ;)

My proposal (a bit complicated) :

Obviously $d \textdegree Q \geq 1$.
Let's suppose $d \textdegree Q > 1$ and then $d \textdegree P \leq 13$.

All values of the $Q(k)$, $k=1..15$ can't be different otherwise $P$ would have $> 13$ roots which is impossible ($P \neq 0$).

We must have $Q(k_1) = Q(k_2)$ and $Q(k_3) = Q(k_4)$ or $Q(k_1) = Q(k_2)= Q(k_3)$, $k_i$ being in $1..15$ and different.

Let's look at first case, wlog, $k_1< k_2 < k_3 < k_4$ :

$Q(X) = A + (X-k_1)(X-k_2)R_1(X)$
$Q(X) = B + (X-k_3)(X-k_4)R_2(X)$

First note that $A$ and $B$ are not null otherwise $P(Q(X))$ would not be divisible by $(X-k_1)(X-k_2)$ or
$(X-k_3)(X-k_3)$

$Q(X) = 0 \Rightarrow k_1*k_2 | A$
$Q(X) = 0 \Rightarrow k_3*k_4 | B$
Since $1 \leq A,B \leq 15$ ($A$ is a root of $(x - 1)(x - 2)(x - 3) ... (x - 15)$) the only possibility is $k_1=1$, $k_2$ = 2, $k_3=3$, $k_4=4$ and $A=2$, $B=12$

$Q(X) = 2 + (X-1)(X-2)R_1(X)$
$Q(X) = 12 + (X-3)(X-4)R_2(X)$

But then $P$ is then given only even numbers, which prevent odd roots to be reachable.