Really? How did they used to say it? And how did they distinguish between a request to prove something and a statement of fact?
You know how in textbooks these days have a set of exercises? Imagine those, except any question which asked you to prove something would just look like a statement of fact. I think it was to save space and paper which these days isn't as a big a deal
You know how in textbooks these days have a set of exercises? Imagine those, except any question which asked you to prove something would just look like a statement of fact. I think it was to save space and paper which these days isn't as a big a deal
So it was more like "verify the following: "This then that", "That then this""?
Nope. As the expression, an=mn is not correct, the subsequent equalities in your solution are also incorrect. And finally, your conclusion is not true.
Oh hmm... But if you were to suppose it tended to a finite limit why is it incorrect to suppose that nan→m as n→∞? (and then proceed in construction a contradiction)
Really, I do not know. After the first exercise the authors said: In subsequent propositions, we shall omit the words "Prove that" and "Show that", and thus stating all problems as theorems.
Let me suggest another lovely functional equation. It seems as though you are the only one who enjoys doing functional eqs.
Problem 99**
Find all continuous functions f(x), defined for all x>1, which satisfy f(xy)=xf(y)+yf(x), for all x,y>1.
If you don't know why a convention is used, why use it?
And I like functional equations too, I'm just nowhere near as good at them. The only widely applicable way of solving them I know is trying special values, like x=y,x=1,x=0 etc.
This problem looks a lot like product rule, although I'm not sure if that has any significance If you take the case x=y, then f(x2)=2xf(x).
If f(x)=ax+c, then f(xy)=axy+c=2axy+(x+y)c. As both x and y are positive integers greater than one, the only possible solution is if both constants are 0. Therefore a possible solution is f(x)=0
b) Does using integration count? Or is that circular reasoning?
Yes. You will need to define the concept of area in your proof.
That would form a circular argument I do believe. Do note that in an elementary proof of this type, using calculus is a little bit mad (and one may argue that in order to be rigorous you would have to include a proof, not only of the fundamental theorem of calculus, but of this operation in a 2 dimension plane being equivalent to area when considering positive values.)
Btw, by rigorous I don't mean for it to be of a university level of rigour, but just explanative justification.
Find all continuous functions f(x), defined for all x>1, which satisfy f(xy)=xf(y)+yf(x), for all x,y>1.
The best I can do at this hour of the night: (∗)f(xy)=f(xy′)⟺xf(x)=−y−y′f(y)−f(y′) let y′=y+ϵ and let epsilon tend to zero giving: xf(x)=−dydf(y). Continuity guarantees existence. let y=x: xf(x)=−dxdf(x)⇒f(x)=−Ax but f(x2)=2xf(x)⇒A=0 so f identically zero is only option. I suspect there's a flaw as calculus is very often fickle.
Yes. You will need to define the concept of area in your proof.
That would form a circular argument I do believe. Do note that in an elementary proof of this type, using calculus is a little bit mad (and one may argue that in order to be rigorous you would have to include a proof, not only of the fundamental theorem of calculus, but of this operation in a 2 dimension plane being equivalent to area when considering positive values.)
Btw, by rigorous I don't mean for it to be of a university level of rigour, but just explanative justification.
I'm not sure how exactly to define area, without some starting point along the lines of "let the area of a 1x1 square be 1". Personally I always thought of the formula for the area of a rectangle as axiomatic. Unless of course we are allowed to state that area is proportional to both the length and width, in which case it becomes trivial.
Oh hmm... But if you were to suppose it tended to a finite limit why is it incorrect to suppose that nan→m as n→∞? (and then proceed in construction a contradiction)
Well. If we take n→∞limnan=m, from the recurrent relation, we obtain n→∞limnan+1=n→∞limnan+n→∞limann1, which is m=m. I doubt that you can obtain a contradiction for this part.
And I like functional equations too, I'm just nowhere near as good at them. The only widely applicable way of solving them I know is trying special values, like x=y,x=1,x=0 etc.
This problem looks a lot like product rule, although I'm not sure if that has any significance If you take the case x=y, then f(x2)=2xf(x).
If f(x)=ax+c, then f(xy)=axy+c=2axy+(x+y)c. As both x and y are positive integers greater than one, the only possible solution is if both constants are 0. Therefore a possible solution is f(x)=0 This is about as far as I've gotten
There are hundreds of techniques when it comes to functional equations. It is annoying that there are no books on functional eqs; I could think of 1-2 really good for olympiad problems. This is only one possible solution and there is an infinite number of them.
The best I can do at this hour of the night: (∗)f(xy)=f(xy′)⟺xf(x)=−y−y′f(y)−f(y′) let y′=y+ϵ and let epsilon tend to zero giving: xf(x)=−dydf(y). Continuity guarantees existence. let y=x: xf(x)=−dxdf(x)⇒f(x)=−Ax but f(x2)=2xf(x)⇒A=0 so f identically zero is only option. I suspect there's a flaw as calculus is very often fickle.
Yup, you are right, there is a flaw. Your first equation may not be true for y=y′, since it is possible that f is injective. Secondly, continuity does not imply differentiability.
Well. If we take n→∞limnan=m, from the recurrent relation, we obtain n→∞limnan+1=n→∞limnan+n→∞limann1, which is m=m. I doubt that you can obtain a contradiction for this part.
Why is it not valid to omit the limit notation if accompanied with the assumption that n is very large? (sorry if these are stupid questions)
There are hundreds of techniques when it comes to functional equations. It is annoying that there are no books on functional eqs
I've never really tried functional equations questions. For me these methods seem non-rigourous (not justifying that all solutions are found). Similar to curve sketching
Just realised I never posted that alternate solution I thought of for problem 88. It seems way too elaborate and, of course, I did it the other way initially, but it seems creative so I'll post it for people's interest...
Let y=(nN)n. Substituting x=nN yields y=(xx1)N. Noting that N is a constant we note that it is easy shown that this function has a stationary point at x=e and that this point is a maximum. Hence we deduce that a1a2...an is at a maximum when n is chosen such that n=eN.
This implies two possibilities. Defining [.] as the greatest integer smaller than or equal to "." (arithmetic function) we have P(N)=a1a2...a[eN] or P(N)=a1a2...a[eN]+1 (as the maximum when specifying integer solutions must occur either with the integers above or below).
Assume there exists a subset of the values of a (denoted by ai) such that ai>[e]+1=3. This implies that this particular subset (of size p) is such that a1a2...ap>3p which implies 3p<max(a1+a2+...+ap)<3p however this is a contradiction as it can be easily shown that the function f(p) defined such that f(p)=3p−3p is greater than or equal to zero for all real p (and hence the positive integers). Therefore, as no such subset can exist (for all p), the optimal value for a is "[e]+1"=3 and clearly the second most optimal value would be 2 (notice that we need not consider any values greater than that of the optimal, as has had been shown. Note also that we could have guessed that 3 was optimal as it is closer to e than 2).
As every positive integer can be expressed as the sum of 2s and 3s except for 1 we get the following result for P(N)...
For some positive integer m, P(N)=1,N=1.P(N)=33N,N=3m.P(N)=22.33N−1,N=3m+1.P(N)=2.33N,N=3m+2.
(I was going to leave my answer in terms of the arithmetic function (i.e. all one case) but it seemed tedious).
Why is it not valid to omit the limit notation if accompanied with the assumption that n is very large? (sorry if these are stupid questions)
There are two possibilities: You write either: n→∞limnan=m, or: for each positive number ϵ there exists N such that for all n>N, ∣nan−m∣<ϵ. This is the concept, you have nan→m as n→∞, not nan=m for all sufficiently large n; in other words, for all sufficiently large n, nan is arbitrarily close to m but it is not equal to m.
I've never really tried functional equations questions. For me these methods seem non-rigourous (not justifying that all solutions are found). Similar to curve sketching
I shall post my solution to problem 97 in order to demonstrate rigorous solution to functional equation. Although, I would say that Lord of the Flies' solution is perfectly justified.
Solution 100
Define S be the unit square with area 1. Let A(R) be the area of the rectangle R. Obviously, the function A is completely additive, and if R′ is isomorphic to R′′, we have A(R′)=A(R′′). It is clear that every square which has side of length 1 is isomorphic to S. Suppose R is a rectangle with sides of length m and n, where m,n∈Z+. We partition R into unit squares. Hence A(R)=m×n×A(S)=m×n. Next, let R be a square with side of length n1, where n is a positive integer. We partition the unit square into n2 squares with side of length n1, which are isomorphic to R. So, n2×A(R)=1. We are ready to prove the formula for rational numbers. Suppose we have R with sides of length mn1, and mn2. We partition this rectangle into n1×n2 squares with side of length m1. Hence A(R)=(n1×n2)×m21. Finally, let R be a rectangle with sides of length x and y. I suppose that both x and y are irrational. Let xk be a sequence of rational numbers such that x−xk<10−k. We define yk similarly. Now, let Rk′ be the sequence of rectangles with side of length xk and yk. Also Rk′′ is the sequence of rectangles with sides of length xk+10−k, yk+10−k. Notice A(Rk′)<A(R)<A(Rk′′). Therefore A(R)=x×y.
There are two possibilities: You write either: n→∞limnan=m, or: for each positive number ϵ there exists N such that for all n>N, ∣nan−m∣<ϵ. This is the concept, you have nan→m as n→∞, not nan=m for all sufficiently large n; in other words, for all sufficiently large n, nan is arbitrarily close to m but it is not equal to m.
Thanks for taking the time to explain that. It makes sense now.
I shall post my solution to problem 97 in order to demonstrate rigorous solution to functional equation. Although, I would say that Lord of the Flies' solution is perfectly justified.
Solution 100
Okay, sounds good. A won't ask you to explain the methods to me because they don't look too taxing and so, if I have time, I will look them up! When you say rigorous methods do you mean something like induction? (because I can see how you could use that to prove something true for all rationals)
Your solution is excellent to my knowledge. I posted it in the hope that people would notice that consideration must be given to irrationality and I was glad to see you had considered this in ample detail.
More problems please!
Btw, have you done your team selection test yet?
---------------
I'm gonna be a complete **** and post a problem I can't solve (and have no intention of trying to )
Problem 101**
Prove that (427(x2+y2+z2))41≥cyc∑x+yx≥(427(xy+yz+zx))41 for positive real numbers x, y and z.
We require that there are 3 distinct real roots. We must conclude, based on the fact that the polynomial is of degree 4 (i.e. cannot be reduced to a polynomial of a lower degree) and that all imaginary roots come in pairs (i.e. theory of conjugate pairing), that there are 4 real roots. From this the deduction has been made that there exists exactly one repeated root. This is correct.
What isn't correct is that we have assumed that, in the quadratic factorisation found, the repeated roots must be that of those in the same quadratic. This is incorrect! (I believe siklos addresses issues like this in two different questions in A.P.I.M.)
One way to address this is to find all other ways in which to factories the polynomial. Allow me to propose another strategy. Starting from the factorisation found in your solution, we deduce two possibilities either the roots are shared between one of the polynomials (leading to a=10023+419 only) or one root from one is equal to one root from another. There is only one such root for which this could occur and the other roots must be equal and opposite (there are a number of strategies that could be used but we only need to find one so observation is sufficient). A keen eye will spot that both quadratics have the root x=0 when 1-a=0 (i.e. a=1).
Substituting this in yields x2(x+3)(x−3)=0 and hence, for a=1, the quadratic has roots x=0, x=3 and x=-3. Therefore ∑a=100123+419. QED.
We require that there are 3 distinct real roots. We must conclude, based on the fact that the polynomial is of degree 4 (i.e. cannot be reduced to a polynomial of a lower degree) and that all imaginary roots come in pairs (i.e. theory of conjugate pairing), that there are 4 real roots. From this the deduction has been made that there exists exactly one repeated root. This is correct.
What isn't correct is that we have assumed that, in the quadratic factorisation found, the repeated roots must be that of those in the same quadratic. This is incorrect! (I believe siklos addresses issues like this in two different questions in A.P.I.M.)
One way to address this is to find all other ways in which to factories the polynomial. Allow me to propose another strategy. Starting from the factorisation found in your solution, we deduce two possibilities either the roots are shared between one of the polynomials (leading to a=10023+419 only) or one root from one is equal to one root from another. There is only one such root for which this could occur and the other roots must be equal and opposite (there are a number of strategies that could be used but we only need to find one so observation is sufficient). A keen eye will spot that both quadratics have the root x=0 when 1-a=0 (i.e. a=1).
Substituting this in yields x2(x+3)(x−3)=0 and hence, for a=1, the quadratic has roots x=0, x=3 and x=-3. Therefore ∑a=100123+419. QED.
Spoiler
Ok, I will add the last part to my post too. That site brilliant.org is fantastic! When you complete a whole week's solution can you have a go at the next level or do I have to wait until next week now?
Ok, I will add the last part to my post too. That site brilliant.org is fantastic! When you complete a whole week's solution can you have a go at the next level or do I have to wait until next week now?
Okay awesome. I hope people besides those who post are doing/trying some of these problems. It's such an awesome problem-solution collection that has been created We've completely gone into olympiad territory now though. Would be really nice to have some more like problem 66 don't you think? I was so chuffed with that one! It's so nice you the irrationality of pi is a consequence of the convergence of the maclaurin expansion for e
Unfortunately not! I managed to complete all the number theory and geo/combinatorics last week on level 4 and so found out that way
My advice to you if you have just started on the site is to try and work out what level you want to be at and make sure you don't rush their "initial test" (take time and get some paper!) What I did was to fire through the first 3 questions on each test and then pretty much guessed the 4th on each one. This resulted in me being placed in level 3 for both olympiad sets (though working your way up is good training). I am such that you would be suited to starting on level 4 or 5 so make sure you do well on the test!
Also note that the format/style of the questions are not similar to british olympiad questions but are very similar to the US's.
Okay awesome. I hope people besides those who post are doing/trying some of these problems. It's such an awesome problem-solution collection that has been created We've completely gone into olympiad territory now though. Would be really nice to have some more like problem 66 don't you think? I was so chuffed with that one! It's so nice you the irrationality of pi is a consequence of the convergence of the maclaurin expansion for e
Unfortunately not! I managed to complete all the number theory and geo/combinatorics last week on level 4 and so found out that way
My advice to you if you have just started on the site is to try and work out what level you want to be at and make sure you don't rush their "initial test" (take time and get some paper!) What I did was to fire through the first 3 questions on each test and then pretty much guessed the 4th on each one. This resulted in me being placed in level 3 for both olympiad sets (though working your way up is good training). I am such that you would be suited to starting on level 4 or 5 so make sure you do well on the test!
Also note that the format/style of the questions are not similar to british olympiad questions but are very similar to the US's.
I'm on Level 3 as well, after making your mistake yesterday. I think it might help mastering Level 3 on Combinatorics though.
May I ask what cyc on the bottom of a sigma means?