Hey there! Sign in to join this conversationNew here? Join for free
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by Jkn)
    Spoiler:
    Show
    Not to be a ****, but surely you can both see that all of this is utterly wrong?

    If you are intending it as a 'joke problem' of the sort where the object is to spot the error (e.g. prove that 1=2), then please make sure that this is clear in the statement of the problem.
    That's kind of the point - it's to demonstrate that the expression 1^{\infty} is meaningless. That's the context it was from originally
    Offline

    15
    ReputationRep:
    Problem 304*

    Does there exist an integer, k, such that using only at most k coin flips, a number in the set {1,2,3} can be randomly picked with each being equally likely?
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by Jkn)
    I hadn't actually tried this problem when I posted it (as it was a 'problem 6' from the Putnam exam and I was hunting around for things that were going to challenge people), but I've given it a go and just managed to solve it! Really enjoyable so I hope people take a crack at it!
    Hmm - I've proved a much weaker result than what I need, but it's an interesting problem. I'll sleep on it
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by james22)
    Problem 304*

    Does there exist an integer, k, such that using only at most k coin flips, a number in the set {1,2,3} can be randomly picked with each being equally likely?
    It's easy to get "arbitrarily likely to have made a random pick" if we get k high enough… after nine flips, I can have a 1/256 chance of not having made a decision, for instance, while after 27 flips, I can have a \dfrac{1}{2^{26}} chance of not having made a decision. I'm still thinking about ways to improve this.
    Offline

    11
    ReputationRep:
    (Original post by Jkn)
    Spoiler:
    Show
    Not to be a ****, but surely you can both see that all of this is utterly wrong?

    If you are intending it as a 'joke problem' of the sort where the object is to spot the error (e.g. prove that 1=2), then please make sure that this is clear in the statement of the problem.
    Hence I said doing some bad maths
    It's as Smaug says.
    Offline

    2
    ReputationRep:
    (Original post by Smaug123)
    That's kind of the point - it's to demonstrate that the expression 1^{\infty} is meaningless. That's the context it was from originally
    Yeah but I get that horrible sick feeling in the pit of my stomach whenever I see incorrect mathematical reasoning - it reminds me of every Physics lesson I've ever been in!

    Also, showing that it is greater than 2 does not prove that it is indeterminate. We need to theorems that rely on it having been established that a limit exists and so all that needs to be done is to show that the utilization of such theorems can lead to more than one value for 1^{\infty} (a contradiction).

    Also, they have not even proven that a solution greater than 2 exists as they are supposing that
    \displaystyle \lim_{n \to \infty} \left( f(n) \right)^n = \left( \lim_{n \to \infty} f(n) \right)^{\lim_{n \to \infty} n}
    which, even if the final limit exists, is invalid as \displaystyle \lim_{n \to \infty} n does not exists and so the rule cannot be applied.
    Offline

    2
    ReputationRep:
    (Original post by Smaug123)
    Hmm - I've proved a much weaker result than what I need, but it's an interesting problem. I'll sleep on it
    What weaker result have you proven? The special case in which k=1?

    Yes it certainly is! I did half an hour yesterday, went round in circles, and then tried it again this morning and got it in just over half an hour!

    My solution is really elegant (in my opinion) but in my searching online I have found that the most commonly found solution was very long and very (very!) insane. One guy had an similarl method to mine though but I am unable to find any officially solutions (yet)
    (Original post by joostan)
    Hence I said doing some bad maths
    It's as Smaug says.
    Ah good!
    Spoiler:
    Show
    But please don't do any more bad maths, I'm not sure I can take it! :lol:


    Had a go at the awesome sequence question yet? I have the feeling it is the kind of problem you would demolish (so long as you have the proper toolbox of techniques at your disposal)!
    Offline

    15
    ReputationRep:
    (Original post by Smaug123)
    It's easy to get "arbitrarily likely to have made a random pick" if we get k high enough… after nine flips, I can have a 1/256 chance of not having made a decision, for instance, while after 27 flips, I can have a \dfrac{1}{2^{26}} chance of not having made a decision. I'm still thinking about ways to improve this.
    That's the tricky bit, the number of potential flips needs to be bounded.
    Offline

    2
    ReputationRep:
    (Original post by james22)
    Problem 304*

    Does there exist an integer, k, such that using only at most k coin flips, a number in the set {1,2,3} can be randomly picked with each being equally likely?
    Solution 304

    There exists no such integer k.

    The problem is essentially equivalent to constructing a probability of \frac{1}{3} out of any linear combination of probabilities of the form \frac{1}{2^n} where n is an integer. Here we are essentially considering the construction of one such value of \frac{1}{3} as this is a necessary condition (and disproof of any such condition is sufficient for contradiction).

    We suppose that \displaystyle \frac{1}{3} = \sum_{i=1}^{n} \frac{a_i}{2^i} which is a necessary condition (though not sufficient as we choose not to place constraints on a_k besides from the obvious one that it is a positive integer). This is also implied by the existence of a value of an integer k as \displaystyle k = 3 \sum_{i=1}^n i a_i.

    The impossibility of this construction can be proven in a number of ways. The most simple way is to prove this is by noting that 2 and 3 are coprime and so no fraction on the right hand side could be constructed with a denominator of 3. To bring mathematical justification to this statement we multiply through by 2^n:

    \displaystyle \Rightarrow \frac{2^n}{3} = \sum_{i=1}^{n} a_i 2^{n-i} = \sum_{i=1}^{n} a_{n-i} 2^i

    which is a contradiction as the left hand side is not an integer as 2 and 3 being coprime implies that 2^n and 3 are coprime and the right hand side is obviously as integer as n is finite.

    This is implies that no such linear combination exists and, hence, that no integer k exists \square
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by Jkn)
    What weaker result have you proven? The special case in which k=1?
    Spoiler:
    Show
    For all integer k, we have that the sequence \dfrac{a_{n}^{k+1}}{n^k} is strictly decreasing; it is bounded below by 0, and hence converges. So the limit exists. (Argument: suppose it's not strictly decreasing for some n, then make the inequality and do a binomial expansion, using that a_n is increasing, which is evident from the definition, a_{n+1} being a sum of two positive things.)

    Depressingly little progress, I know
    ETA: Also, the starting value a_0 shouldn't matter, because a_n is unbounded so eventually we'll exceed wherever we started. A little thing, but it might help!
    Offline

    2
    ReputationRep:
    (Original post by Smaug123)
    Spoiler:
    Show
    For all integer k, we have that the sequence \dfrac{a_{n}^{k+1}}{n^k} is strictly decreasing; it is bounded below by 0, and hence converges. So the limit exists. (Argument: suppose it's not strictly decreasing for some n, then make the inequality and do a binomial expansion, using that a_n is increasing, which is evident from the definition, a_{n+1} being a sum of two positive things.)

    Depressingly little progress, I know
    ETA: Also, the starting value a_0 shouldn't matter, because a_n is unbounded so eventually we'll exceed wherever we started. A little thing, but it might help!
    Hmm well it sounds like youve got he initial tedious bit of rigour out o the way!

    They need to be greater than zero in order to restrict a_n to the set of real numbers.

    Here's some problems I just shared on ASOM (though I would pop them on here too as, if people are going to be writing solutions without extensive discussion, this is certainly the place for it). The first 4 are from BMO2 and the 5th is from Putnam (though it is a 'problem 1').

    Problem 305*

    Prove that the sequence defined by y_0=1, \displaystyle y_{n+1}=\frac{1}{2} \left(3y_n + \sqrt{5y_n^2-4} \right) for n \ge 0 consists only of integers.

    [As a bonus, can you find any 'similar' sequences for which this is true?]


    Problem 306
    *

    Find all solutions in non-negative integers a,b to \displaystyle \sqrt{a}+\sqrt{b}=\sqrt{2009}

    [As a bonus, why not generalise this in the obvious way? Giving all solutions a,b,c dependent on either c having a certain property or c simply being any integer]


    Problem 307
    *

    Find the minimum possible value of \displaystyle x^2+y^2 where x,y are real numbers such that \displaystyle xy(x^2-y^2)=x^2+y^2 and x \not= 0.

    Problem 308
    *

    Find all pairs of integers (x,y) such that \displaystyle 1+x^2y=x^2+2xy+2x+y

    Problem 309*/**/***

    Find the volume of the region of points (x,y,z) such that \displaystyle (x^2+y^2+z^2+8)^2 \le 36(x^2+y^2)

    Time to see who has been paying attention to this thread (if you have been you will do this in minutes)! This one is a 'problem 4' from Putnam:

    Problem 310
    **

    Evaluate \displaystyle \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \frac{m^2 n}{3^m (n 3^m + m 3^n)}

    Some easier ones. Please do not post a solution if they do not interest/challenge you - though whilst they are mostly easier than those above, they are still by no means 'trivial' or 'easy' and would still be considered difficult by the standards of numerous institutions/exams. Also, do not be discouraged if you cannot do them as problem-solving takes practice and is certainly something that has to be learnt in almost all cases:

    Problem 311*/**/*** (the one-* solution does exist and is not hard to find - please don't moan on about it!)

    Let x_0=0, x_1=1 and \displaystyle x_{n+1}=\frac{1}{n+1} x_n + \left(1-\frac{1}{n+1} \right) x_{n-1} for n \ge 1.

    Show that the sequence \{ x_n \} convergences as n \to \infty and determine its limit.

    Problem 312*

    Evaluate \displaystyle \frac{4}{4^2-1}+\frac{4^2}{4^4-1}+\frac{4^4}{4^8-1}+\frac{4^8}{4^{16}-1}+\cdots

    Problem 313*

    Find all real values of x,y and z such that \displaystyle (x+1)yz=12, \ (y+1)zx=4, \ (z+1)xy=4

    [As a bonus, can you solve the problem with a more general set of constraints?]


    Problem 314*

    Find all positive integers n such that n+2012 divides n^2+2012 and n+2013 divides n^2+2013.

    This is the kind of problem you could find really easy or rather difficult:

    Problem 315**/***

    Determine, with proof, whether the series \displaystyle \sum_{n=1}^{\infty} \frac{1}{n^{2+\cos (2 \pi \ln n)}} converges.
    Offline

    11
    ReputationRep:
    (Original post by Jkn)

    Ah good!
    Spoiler:
    Show
    But please don't do any more bad maths, I'm not sure I can take it! :lol:


    Had a go at the awesome sequence question yet? I have the feeling it is the kind of problem you would demolish (so long as you have the proper toolbox of techniques at your disposal)!
    OK, I won't.
    Is that problem 161? Looks like a mess, but I might take a punt, right now I'm having a go at some of the others that you just posted

    (Original post by Jkn)

    Problem 306
    *

    Find all solutions in non-negative integers a,b to \displaystyle \sqrt{a}+\sqrt{b}=\sqrt{2009}

    [As a bonus, why not generalise this in the obvious way? Giving all solutions a,b,c dependent on either c having a certain property or c simply being any integer]
    Solution 306:
    Note that:
    2009=7 \times 287 =7^2 \times 41

\Rightarrow \sqrt{a}+\sqrt{b}=7\sqrt{41}
    The obvious solutions are therefore:
    \sqrt{a}=k\sqrt{41} \Rightarrow a=41k^2

\sqrt{b}=(7-k)\sqrt{41} \Rightarrow b=41(7-k)^2
    k \in \{0,1, . . . ,7\}
    To demonstrate that these are the only solutions with the given restrictions, consider:
    \sqrt{a}+\sqrt{b} = \sqrt{2009}

\Leftrightarrow a+b+2\sqrt{ab}=2009

\Leftrightarrow (a+b-2009)^2=4ab

\Rightarrow a^2+2ab+b^2+2009^2-4018(a+b)=4ab

\Rightarrow a^2-2ab+b^2+2009^2-4018a-4108b=0

\Rightarrow a^2-2(b+2009)a+(b-2009)^2=0
    Solving for a:
    a=\dfrac{2(b+2009) \pm \sqrt{4(b+2009)^2-4(b-2009)^2}}{2}=b+2009 \pm \sqrt{4 \times 2009 b}
    Observing that: 0 \leq a,b \leq 2009
    \Rightarrow a=b+2009-14\sqrt{41b}
    For this to be an integer, observe that \sqrt{41b} \in \mathbb{Z^+} must hold.
    Therefore: b=41n^2 for some integer n (n \leq 7)
    Now we can solve similarly for b and state that:
    a=41m^2 for some integer m (m \leq 7)
    So we find that: \sqrt{a},\sqrt{b} are of the form c\sqrt{41}
    Whereby the previously found solutions are the only solutions.


    Consider the general case:
    \sqrt{a}+\sqrt{b}=\sqrt{c}
    If c=p^2q for some integers p and q
    \sqrt{a}+\sqrt{b}=p\sqrt{q}
    Using the same method as above we can deduce that:
    Such that:
    a=k^2q
    b=(p-k)^2q
    k \in \{0,1 . . . ,p\}
    If c is not of the above form then for integer solutions either a=0 , \ b=c or a=c, \ b=0
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by joostan)
    OK, I won't.
    Is that problem 161? Looks like a mess, but I might take a punt, right now I'm having a go at some of the others that you just posted


    Solution 306:
    Damn, you got there before me - it generalises in the obvious way, of course, if you just replace c with p^2 q, but I can't be bothered to look at p^2 q r, etc :P
    Offline

    3
    ReputationRep:
    (Original post by FireGarden)
    Problem 301**

    Prove, given  a,c > 0;\ \ ac-bd\not=0

     \arctan\left(\dfrac{ad+bc}{ac-bd}\right) = \arctan\left(\dfrac{b}{a}\right) + \arctan\left(\dfrac{d}{c}\right)
    This is pretty much a standard a level question.


    Posted from TSR Mobile
    Offline

    11
    ReputationRep:
    (Original post by Smaug123)
    Damn, you got there before me - it generalises in the obvious way, of course, if you just replace c with p^2 q, but I can't be bothered to look at p^2 q r, etc :P
    Ninja-ed :ninja:
    Yeah, you can do the generalisation, I don't really know what he's after.
    Unless he wanted: \sqrt{a}+\sqrt{b}=p\sqrt{q}
    In which case:
    \sqrt{a}=c\sqrt{q}

\sqrt{b}=(p-c)\sqrt{q}

c \in \{0,1, . . . ,p \}
    which I suspect can be shown after a bit of algebra.
    Offline

    3
    ReputationRep:
    (Original post by Jkn)
    Yeah but I get that horrible sick feeling in the pit of my stomach whenever I see incorrect mathematical reasoning - it reminds me of every Physics lesson I've ever been in!

    Also, showing that it is greater than 2 does not prove that it is indeterminate. We need to theorems that rely on it having been established that a limit exists and so all that needs to be done is to show that the utilization of such theorems can lead to more than one value for 1^{\infty} (a contradiction).

    Also, they have not even proven that a solution greater than 2 exists as they are supposing that
    \displaystyle \lim_{n \to \infty} \left( f(n) \right)^n = \left( \lim_{n \to \infty} f(n) \right)^{\lim_{n \to \infty} n}
    which, even if the final limit exists, is invalid as \displaystyle \lim_{n \to \infty} n does not exists and so the rule cannot be applied.

     1^{\infty} = \displaystyle\lim_{x\to\infty}1^  {x} = 1 



1^{\infty} = \displaystyle\lim_{x\to\infty} \left(1+\dfrac{1}{x} \right)^{x} = e



1\not=e \implies 1^{\infty} \not= 1^{\infty}

    So  1^{\infty} is an indeterminate form. I don't know why you think you need to prove the limit exists; that's contradictory to it being an indeterminate form in the first place. You do need to show that the limits exist of the functions that you use to make a contradiction about the value, which we shan't bother doing since one's trivial (constant function) and the others a standard result. We did not suppose your second paragraph, either .
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by joostan)
    Ninja-ed :ninja:
    Yeah, you can do the generalisation, I don't really know what he's after.
    Unless he wanted: \sqrt{a}+\sqrt{b}=p\sqrt{q}
    In which case:
    \sqrt{a}=c\sqrt{q}

\sqrt{b}=(p-c)\sqrt{q}

c \in \{0,1, . . . ,p \}
    which I suspect can be shown after a bit of algebra.
    Yup, it's the same algebra, too
    Offline

    11
    ReputationRep:
    (Original post by Smaug123)
    Yup, it's the same algebra, too
    Okey dokey, I edited it in minus the algebra :laugh:
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by Jkn)
    What weaker result have you proven? The special case in which k=1?
    Here's my "progress post", updated as I solve the question

    k=1 case: I used Mathematica to get a couple of hundred iterations, I just couldn't intuit the limit… then it was easy enough to show by induction that b_n \equiv \dfrac{a_n^2}{n} > 2 always, after getting a recurrence relation for b_n. Also shown previously that b_n is strictly decreasing. Now I just need to show that 2 is indeed the limit.
    Offline

    0
    ReputationRep:
    (Original post by Jkn)
    g

    Problem 307
    *

    Find the minimum possible value of \displaystyle x^2+y^2 where x,y are real numbers such that \displaystyle xy(x^2-y^2)=x^2+y^2 and x \not= 0.
    [B]+y^2)


    Problem 310
    **

    Evaluate \displaystyle \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \frac{m^2 n}{3^m (n 3^m + m 3^n)}
    Solution 307

    Let  x= r \sin {\theta}, y = r \cos {\theta} . Then,  r^2 = x^2 + y^2 .

    Now, we have to minimize  r^2 , essentially.

     xy(x^2-y^2) = \frac{1}{2} r^4 \sin {2 \theta} \cos {2 \theta} = x^2 + y^2 = r^2



\Rightarrow r^2 \sin {2 \theta} \cos {2 \theta} = 2



\Rightarrow r^2 \sin {4 \theta} = 4



\Rightarrow r^2 = \frac{4}{\sin {4 \theta}}



\Rightarrow min(x^2+y^2) = 4


    Solution 310

      \displaystyle \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \frac{m^2 n}{3^m (n 3^m + m3^n)} = \frac{1}{2} \displaystyle \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \left( \frac{m^2 n}{3^m (n 3^m + m3^n)} + \frac{n^2 m}{3^n (n 3^m + m3^n)} \right)



\Rightarrow = \frac{1}{2} \displaystyle \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \left( \frac{m^2 n(3^n m)+ n^2 m (3^m n)}{3^{m+n} (n 3^m + m3^n)} \right)



\Rightarrow =  \frac{1}{2} \displaystyle \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \left( \frac{mn}{3^{m+n}}\right)



\Rightarrow = \frac{1}{2} \left( \displaystyle \sum_{m=1}^{\infty} \frac{m}{3^m} \right)^2

    Now, note that:

     \displaystyle \frac{1}{(1-x)^2} = \sum_{i=1}^{\infty} i x^{i-1}



\Rightarrow \displaystyle \frac{x}{(1-x)^2} = \sum_{i=1}^{\infty} i x^i



\Rightarrow \displaystyle \frac{\frac{1}{3}}{(\frac{2}{3})  ^2} = \sum_{m=1}^{\infty} \frac{m}{3^m}



\Rightarrow  \displaystyle \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \frac{m^2 n}{3^m (n 3^m + m3^n)} = \frac{1}{2} \left( \displaystyle \frac{\frac{1}{3}}{(\frac{2}{3})  ^2} \right)^2 = \frac{9}{8}
 
 
 
  • 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
    Have you ever participated in a Secret Santa?
    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

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