Hey there! Sign in to join this conversationNew here? Join for free
    Offline

    15
    ReputationRep:
    (Original post by bananarama2)
    LOTF Solution 336

    By maths we have the inequality.
    I'm still not sure if he actually found a solution, or just put up some random statements int eh hope that nobody would check
    Offline

    1
    ReputationRep:
    (Original post by james22)
    I'm still not sure if he actually found a solution, or just put up some random statements int eh hope that nobody would check
    Just notice that from AM-GM, \displaystyle \frac{a^{3}}{b}+ab \ge 2\sqrt{\frac{a^{3}}{b}ab}=2a^{2}.
    The second inequality is just an application of (a-b)^{2} \ge 0.

    Problem 337**

    Let C_{1} and C_{2} be externally tangent circles at M and the radius of C_{2} is greater than the radius of C_{1}. Let A be a point on C_{2} which does not lie on the line joining the centres of C_{1} and C_{2}. Let B and C be points on C_{1} such that AB and AC are tangent to C_{1}. The lines BM and CM intersect C_{2} again at E and F, respectively. Let D be the point of intersection of the tangent to C_{2} at A and the line EF. Prove that as A varies, the locus of D is a line.
    Offline

    12
    ReputationRep:
    Problem 338*

    Consider the sequence for a_n = n! + 100\ for\ n \ge 1, what is the maximum value of gcd(a_n,a_{n+1})?
    Offline

    18
    ReputationRep:
    Solution 338

    Note \gcd (a_{10},a_{11})=100. Now suppose for n>10 there is d>100 s.t. d|a_n and d|a_{n+1} then d|(n+1)a_n-a_{n+1}=100n. Since n>10\Rightarrow 100n|n! we have d|n!\Rightarrow d|100\Rightarrow \Leftarrow
    Offline

    18
    ReputationRep:
    (Original post by bananarama2)
    LOTF Solution 336

    By maths we have the inequality.
    HA! How unfair, I even said AM-GM and everything.
    Offline

    1
    ReputationRep:
    Two warm-up problems.

    Problem 339**

    Let (a_{i})_{1 \le i \le n} be a sequence of non-negative integers. Let \displaystyle m_{k} = \max_{1 \le i \le k} \frac{a_{k-i+1}+\cdots+a_{k}}{i} where k \in \{1,2,\cdots, n\}. Prove that for any m>0 the number of integers k such that m_{k} \ge m is \displaystyle \le \frac{a_{1}+\cdots+a_{n}}{m}.

    Problem 340**

    Find all maps f: \mathbb{N} \to \mathbb{N} such that for all m,n the relation f(m)+f(n) | m+n holds. Now let k be an arbitrary positive integer. Find all maps f : \mathbb{N} \to \mathbb{N} such that f(m)+f(n) | (m+n)^{k} for all choices of positive integers m,n.
    Offline

    3
    ReputationRep:
    (Original post by Mladenov)
    Two warm-up problems.

    Problem 339**

    Let (a_{i})_{1 \le i \le n} be a sequence of non-negative integers. Let \displaystyle m_{k} = \max_{1 \le i \le k} \frac{a_{k-i+1}+\cdots+a_{k}}{i} where k \in \{1,2,\cdots, n\}. Prove that for any m>0 the number of integers k such that m_{k} \ge m is \displaystyle \le \frac{a_{1}+\cdots+a_{n}}{m}.

    Problem 340**

    Find all maps f: \mathbb{N} \to \mathbb{N} such that for all m,n the relation f(m)+f(n) | m+n holds. Now let k be an arbitrary positive integer. Find all maps f : \mathbb{N} \to \mathbb{N} such that f(m)+f(n) | (m+n)^{k} for all choices of positive integers m,n.
    Warm up? Lol

    Posted from TSR Mobile
    Offline

    2
    ReputationRep:
    Solution 340** (partial)

    Attention everyone! I have made unprecedented progress with this fiendish problem. I have found one of the three possible maps - now I am just in a quandary as to what the other two could possibly be?



    UPDATE!
    Spoiler:
    Show
    Eureka, I HAVE FOUND THE SECOND MAP! It is none other than the sentient map from Dora the Explorer! Now for the final map... which continues to antagonize and elude me. I shall update this post when I find that tertiary map and bring it to justice in the form of a fully worked solution to the problem stated.



    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by Mladenov)
    Problem 340**

    Find all maps f: \mathbb{N} \to \mathbb{N} such that for all m,n the relation f(m)+f(n) | m+n holds. Now let k be an arbitrary positive integer. Find all maps f : \mathbb{N} \to \mathbb{N} such that f(m)+f(n) | (m+n)^{k} for all choices of positive integers m,n.
    Ooh, I like this problem, although my solution is a bit plodding and slow. So plodding and slow, in fact, that I have only done the first part. The induction I used is very messy - I'd appreciate it if someone could check it.
    Spoiler:
    Show

    Setting m=n=1 we have 2 f(1) | 2, and hence f(1) = 1.
    Then m=1 gives 1+f(n) | n+1 for all n.
    Also setting m=n we have 2 f(m) | 2m, and so f(m) | m, for all m.

    f(2)+f(n) | 2+n
    Let n be prime > 2. Suppose f(n) = n. Then f(2)+f(n) = f(2)+n | 2+n, but f(2) is 1 or 2, so we must have f(2) = 2. Suppose f(n) = 1. Then f(2)+1 | 2+n, and hence we can't have f(2) = 1 (because then even divides odd). So f(2) = 2.

    Now let m,n be odd prime, with m<n. Then f(m)+f(n) | m+n. Suppose f(n) = n. Then f(n) is greater than half m+n, and hence f(m)+f(n) = m+n, and so f(m) = m. So if we have one odd prime for which f(p) = p, then all lower odd primes have f(q) = q. In other words, considering the odd primes, we must have f(p_i) = p_i for i=1 to k, and then f(p_i) = 1 for i>k (where k might be infinity).

    Now consider p prime, such that f(p) = 1. Then f(m)+1 | m+p, for all m. Letting m=2, we have that 3|p+2. So p must be 1 mod 3 in order for f(p) to be 1. But because we know that there is an infinite number of primes 1 mod 3 and 2 mod 3, and using the previous paragraph, we then see that f(p) = p for all primes p.

    To summarise, so far we have that f(n) = n for n prime and for n=1.

    Unnecessary further result:
    Spoiler:
    Show

    Now, f(p - n)+f(n) | p, for all n<p and for all prime p. So f(p-n)+f(n) = 1 (contradiction because the LHS is greater than or equal to 2), or f(p-q)+f(q) = p, for all q<p and prime p. Hence f(p-q) = p-q for any primes q < p. This is a very powerful statement - any number that is prime or is a difference of two primes, has f(n) = n. This reasoning works not just for prime q, but for any q where f(q) = q. So, in particular, f(p-1) = p-1.

    Then, f(qp-q)+f(q) | qp, so f(qp-q)+q | qp, and dividing by q yields f(q(p-1)) = q(p-1), for prime p,q.


    Now we proceed inductively. Base case: p=2, where all f(2p-n) have f(2p-n) = 2p-n.
    Then assume that for p=p, we have that all f(2p-n) = 2p-n. Then considering q the next prime up from p, we have that f(2q-n)+f(n) | 2q. We only need to check the n that will give us 2p <= 2q-n < 2q, because the n that will give 2q-n < 2p have already been checked under the inductive hypothesis. Hence n <= 2(q-p). But Bertrand's Postulate states that q<2p, so n < 2(2p-p) = 2p. And we have [inductive hypothesis] that all such n have f(n) = n, so f(2q-n) + n | 2q. Hence f(2q-n)+n = 2, q or 2q.
    If it's 2q, we're done straight away.
    It can't be 2, because that requires n=1, f(2q-1) = 1, but then f(2q-1)+f(q+1) | 3q and 1+f(q+1) | 3q - but we know that since q+1<2p [strong form of Bertrand], we have f(q+1) = q+1, and q+2 | 3q which is rubbish.
    Suppose that f(2q-n)+n = q. Then f(2q-n) = q-n; then q-n | 2q-n. But then there is k such that k(q-n) = 2q-n, from which (k-2)q = (k-1)n. If k is odd, then the LHS is odd and the RHS even; if k is even, then the LHS is even so n is even. Hence q-n | 2(q-n/2), but q-n is odd and so q-n | q-n/2, which is a contradiction.
    Therefore, f(2q-n) = 2q-n for all 1 <= n < 2q.

    So by extremely messy induction, we're done: the only valid map is f(n) = n for all n.
    Offline

    1
    ReputationRep:
    (Original post by Smaug123)
    Spoiler:
    Show
    Ooh, I like this problem, although my solution is a bit plodding and slow. So plodding and slow, in fact, that I have only done the first part. The induction I used is very messy - I'd appreciate it if someone could check it.
    Spoiler:
    Show

    Setting m=n=1 we have 2 f(1) | 2, and hence f(1) = 1.
    Then m=1 gives 1+f(n) | n+1 for all n.
    Also setting m=n we have 2 f(m) | 2m, and so f(m) | m, for all m.

    f(2)+f(n) | 2+n
    Let n be prime > 2. Suppose f(n) = n. Then f(2)+f(n) = f(2)+n | 2+n, but f(2) is 1 or 2, so we must have f(2) = 2. Suppose f(n) = 1. Then f(2)+1 | 2+n, and hence we can't have f(2) = 1 (because then even divides odd). So f(2) = 2.

    Now let m,n be odd prime, with m<n. Then f(m)+f(n) | m+n. Suppose f(n) = n. Then f(n) is greater than half m+n, and hence f(m)+f(n) = m+n, and so f(m) = m. So if we have one odd prime for which f(p) = p, then all lower odd primes have f(q) = q. In other words, considering the odd primes, we must have f(p_i) = p_i for i=1 to k, and then f(p_i) = 1 for i>k (where k might be infinity).

    Now consider p prime, such that f(p) = 1. Then f(m)+1 | m+p, for all m. Letting m=2, we have that 3|p+2. So p must be 1 mod 3 in order for f(p) to be 1. But because we know that there is an infinite number of primes 1 mod 3 and 2 mod 3, and using the previous paragraph, we then see that f(p) = p for all primes p.

    To summarise, so far we have that f(n) = n for n prime and for n=1.

    Unnecessary further result:
    Spoiler:
    Show

    Now, f(p - n)+f(n) | p, for all n<p and for all prime p. So f(p-n)+f(n) = 1 (contradiction because the LHS is greater than or equal to 2), or f(p-q)+f(q) = p, for all q<p and prime p. Hence f(p-q) = p-q for any primes q < p. This is a very powerful statement - any number that is prime or is a difference of two primes, has f(n) = n. This reasoning works not just for prime q, but for any q where f(q) = q. So, in particular, f(p-1) = p-1.

    Then, f(qp-q)+f(q) | qp, so f(qp-q)+q | qp, and dividing by q yields f(q(p-1)) = q(p-1), for prime p,q.


    Now we proceed inductively. Base case: p=2, where all f(2p-n) have f(2p-n) = 2p-n.
    Then assume that for p=p, we have that all f(2p-n) = 2p-n. Then considering q the next prime up from p, we have that f(2q-n)+f(n) | 2q. We only need to check the n that will give us 2p <= 2q-n < 2q, because the n that will give 2q-n < 2p have already been checked under the inductive hypothesis. Hence n <= 2(q-p). But Bertrand's Postulate states that q<2p, so n < 2(2p-p) = 2p. And we have [inductive hypothesis] that all such n have f(n) = n, so f(2q-n) + n | 2q. Hence f(2q-n)+n = 2, q or 2q.
    If it's 2q, we're done straight away.
    It can't be 2, because that requires n=1, f(2q-1) = 1, but then f(2q-1)+f(q+1) | 3q and 1+f(q+1) | 3q - but we know that since q+1<2p [strong form of Bertrand], we have f(q+1) = q+1, and q+2 | 3q which is rubbish.
    Suppose that f(2q-n)+n = q. Then f(2q-n) = q-n; then q-n | 2q-n. But then there is k such that k(q-n) = 2q-n, from which (k-2)q = (k-1)n. If k is odd, then the LHS is odd and the RHS even; if k is even, then the LHS is even so n is even. Hence q-n | 2(q-n/2), but q-n is odd and so q-n | q-n/2, which is a contradiction.
    Therefore, f(2q-n) = 2q-n for all 1 <= n < 2q.

    So by extremely messy induction, we're done: the only valid map is f(n) = n for all n.
    It is fine; however, you could have eluded this induction.
    Spoiler:
    Show
    From f(p)=p for all primes p, we get p+f(n)|p+n=p+f(n)+n-f(n), which then gives p+f(n)|n-f(n). Now, choosing p sufficiently large, we are done.
    Offline

    1
    ReputationRep:
    (Original post by Pterodactyl)
    Spoiler:
    Show
    I think this is correct.
    Solution 340
    Part I
    We have two cases to consider \displaystyle m=n, m \ne n
    If \displaystyle m = n \Rightarrow 2f(m)|2m \Rightarrow f(m)|m
    \displaystyle\therefore af(m) = m for \displaystyle a \in \mathbb{N} \Rightarrow a|m for any \displaystyle m\in \mathbb{N}. When m=n this only occurs for k = 1, m. So f(x) = 1, f(x) = x

    Now to check that these work for the other case
    If \displaystyle m \ne n, f(x) = 1 \Rightarrow f(m)+f(n) = 2. m+n is not always even so \displaystyle f(x)\ne 1
    If \displaystyle m\ne n, f(x) = x \Rightarrow f(m)+f(n) = m+n, which clearly divides m+n so the only map is \displaystyle f(x) =x


    Part II
    Using the same cases again.
    If \displaystyle m=n \Rightarrow f(m)|2^{k-1}m^k
    \displaystyle \therefore af(m) = 2^{k-1}m^k for \displaystyle a\in \mathbb{N}
    So \displaystyle a|2^{k-1}m^k \Rightarrow a = 2^{\alpha}m^{\beta} where \displaystyle \alpha \le k-1, \beta \le k
    \displaystyle\therefore f(x)=2^{k-(\alpha+1)}x^{k-\beta}

    Now to check if these work for the other case.
    \displaystyle m\ne n, f(x)=2^{k-(\alpha+1)}x^{k-\beta} \Rightarrow f(m)+f(n) = 2^{k-(\alpha+1)}(m^{k-\beta}+n^{k-\beta})
    \displaystyle f(m)+f(n)|(m+n)^k \Leftrightarrow 2^{k-(\alpha + 1)}|(m+n)^k and \displaystyle m^{k-\beta}+n^{k-\beta}|(m+n)^k
    Clearly \displaystyle (m+n)^k will not always be a multiple of some power of 2 so \displaystyle \alpha = k-1.
    \displaystyle m^{k-\beta}+n^{k-\beta}|(m+n)^k \Leftrightarrow \beta = k - 1 \Rightarrow f(x) = x is the only mapping, again.

    You actually have a_{m}f(m)=m, unless you prove that \displaystyle \frac{m}{f(m)} is constant.
    The second part is also incorrect. The same mistake plus not all divisors of 2^{\alpha}m^{\beta} can be written as 2^{\alpha_{1}}m^{\beta_{1}}.
    Offline

    12
    ReputationRep:
    (Original post by Mladenov)
    You actually have a_{m}f(m)=m, unless you prove that \displaystyle \frac{m}{f(m)} is constant.
    The second part is also incorrect. The same mistake plus not all divisors of 2^{\alpha}m^{\beta} can be written as 2^{\alpha_{1}}m^{\beta_{1}}.
    Ah, stupid of me! Deleted the post.
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by Mladenov)
    It is fine; however, you could have eluded this induction.
    Spoiler:
    Show
    From f(p)=p for all primes p, we get p+f(n)|p+n=p+f(n)+n-f(n), which then gives p+f(n)|n-f(n). Now, choosing p sufficiently large, we are done.
    Aah, much better - thanks!
    Offline

    15
    ReputationRep:
    Problem 341**/***

    Find \displaystyle\int^{\infty}_{-\infty} \frac{log(x^2+1)}{x^2+1}\ dx

    I don't actually know how to solve this one, but I do have the answer.
    Offline

    1
    ReputationRep:
    (Original post by james22)
    Problem 341**/***

    Find \displaystyle\int^{\infty}_{-\infty} \frac{log(x^2+1)}{x^2+1}\ dx

    I don't actually know how to solve this one, but I do have the answer.
    Solution 158. Notice that the function is even.
    Offline

    0
    ReputationRep:
    (Original post by Mladenov)
    Solution 158. Notice that the function is even.
    Completely separate note to the maths; I love your really broad use of the English languages "Thence."
    Offline

    9
    ReputationRep:
    This is an easier one than the normal problems here, maybe for those who don't look at this thread very often.

    Problem 342*

    Evaluate \displaystyle \sum_{k=1}^n \binom{2n -k -1}{n-1}
    Offline

    10
    ReputationRep:
    Problem 343 */**

    Prove that:

     \displaystyle  \sum_{a_{n}=0}^{r} \sum_{a_{n-1} = 0}^{a_n} ... \sum_{a_1=0}^{a_2} \sum_{a_0 = 0}^{a_1} 1 = \binom{n+1+r}{r}
    Offline

    9
    ReputationRep:
    Solution 343

    Let P(r) denote the proposition that  \displaystyle  \sum_{a_{n}=0}^{r} \sum_{a_{n-1} = 0}^{a_n} ... \sum_{a_1=0}^{a_2} \sum_{a_0 = 0}^{a_1} 1 = \binom{n+1+r}{r}

    Consider the case when r=a_1 \Rightarrow n=0.

    \displaystyle LHS = \sum_{a_0 = 0}^{a_1} 1 =a_1 +  1 = \binom{a_1 + 1}{a_1} = RHS [*]

    Assume P(a_n) to be true, (r=a_n) and consider the case for a_{n+1}:

    \displaystyle \sum_{a_n = 0}^{a_{n+1}} \binom{n + a_n}{a_n} = \binom{n}{0}  + \sum_{a_n = 1}^{a_{n+1}} \binom{a_n + n + 1}{a_n} - \binom{a_n + n }{a_n - 1}

     \displaystyle = 1 - \binom{n+1}{0} + \binom{a_{n+1} + n + 1}{a_{n+1}} = \binom{(n+1) + a_{n+1}}{a_{n+1}}

    Hence P(a_{n+1}) is true if P_(a_n) is assumed to be true which, along with [*], implies that P(r) is true by mathematical induction.
    Offline

    13
    ReputationRep:
    (Original post by Ateo)
    This is an easier one than the normal problems here, maybe for those who don't look at this thread very often.

    Problem 342*

    Evaluate \displaystyle \sum_{k=1}^n \binom{2n -k -1}{n-1}
    Solution 342

    \displaystyle \begin{aligned} \sum_{r=1}^{n} \binom{2n - r - 1}{n-1} = \sum_{r=1}^{n} \binom{n + r - 2}{n-1} & = \underbrace{\binom{n-1}{n-1}}_{=1} + \binom{n}{n-1} + \cdots + \binom{2n-2}{n-1} \\ & = \left[ \binom{n}{n} + \binom{n}{n-1} \right] + \cdots + \binom{2n-2}{n-1} \\ & = \left[ \binom{n+1}{n} + \binom{n+1}{n-1} \right] + \cdots + \binom{2n-2}{n-1} \\ & = \left[\binom{n+2}{n} + \binom{n+2}{n-1}\right] + \cdots + \binom{2n-2}{n-1} \\ \\ & \vdots \quad \left( n-1 \ \text{times}\right) \\ \\ & = \binom{2n-2}{n} + \binom{2n-2}{n-1} = \boxed{\binom{2n-1}{n}} \end{aligned}


    Problem 344*/***

    Evaluate \displaystyle \sum_{r=0}^{\infty} \frac{1}{4r+1} - \frac{1}{4r+2}.
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    Has a teacher ever helped you cheat?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Write a reply...
    Reply
    Hide
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.