The Student Room Group
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>

The Proof is Trivial!

Scroll to see replies

Original post by Jkn

Spoiler



That's kind of the point - it's to demonstrate that the expression 1∞1^{\infty} is meaningless. That's the context it was from originally :smile:
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?
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! :biggrin:

Hmm - I've proved a much weaker result than what I need, but it's an interesting problem. I'll sleep on it :smile:
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 1226\dfrac{1}{2^{26}} chance of not having made a decision. I'm still thinking about ways to improve this.
Original post by Jkn

Spoiler



Hence I said doing some bad maths :tongue:
It's as Smaug says.
Reply 2105
Avatar for Jkn
Jkn
11
Original post by Smaug123
That's kind of the point - it's to demonstrate that the expression 1∞1^{\infty} is meaningless. That's the context it was from originally :smile:

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! :frown:

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∞1^{\infty} (a contradiction).

Also, they have not even proven that a solution greater than 2 exists as they are supposing that
lim⁡n→∞(f(n))n=(lim⁡n→∞f(n))lim⁡n→∞n\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 lim⁡n→∞n\displaystyle \lim_{n \to \infty} n does not exists and so the rule cannot be applied. :tongue:
Reply 2106
Avatar for Jkn
Jkn
11
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 :smile:

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! :smile:

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) :tongue:
Original post by joostan
Hence I said doing some bad maths :tongue:
It's as Smaug says.

Ah good! :tongue:

Spoiler



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)! :biggrin:
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 1226\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.
Reply 2108
Avatar for Jkn
Jkn
11
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 13\frac{1}{3} out of any linear combination of probabilities of the form 12n\frac{1}{2^n} where n is an integer. Here we are essentially considering the construction of one such value of 13\frac{1}{3} as this is a necessary condition (and disproof of any such condition is sufficient for contradiction).

We suppose that 13=∑i=1nai2i\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 aka_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 k=3∑i=1niai\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 2n2^n:

⇒2n3=∑i=1nai2n−i=∑i=1nan−i2i\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 2n2^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
Original post by Jkn
What weaker result have you proven? The special case in which k=1?

Spoiler


Depressingly little progress, I know :tongue:
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!
(edited 10 years ago)
Reply 2110
Avatar for Jkn
Jkn
11
Original post by Smaug123

Spoiler


Depressingly little progress, I know :tongue:
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 ana_n to the set of real numbers. :smile:

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 y0=1y_0=1, yn+1=12(3yn+5yn2−4)\displaystyle y_{n+1}=\frac{1}{2} \left(3y_n + \sqrt{5y_n^2-4} \right) for n≥0n \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 a+b=2009\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 x2+y2\displaystyle x^2+y^2 where x,y are real numbers such that xy(x2−y2)=x2+y2\displaystyle xy(x^2-y^2)=x^2+y^2 and x≠0x \not= 0.

Problem 308*

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

Problem 309*/**/***

Find the volume of the region of points (x,y,z) such that (x2+y2+z2+8)2≤36(x2+y2)\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 ∑m=1∞∑n=1∞m2n3m(n3m+m3n)\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 x0=0x_0=0, x1=1x_1=1 and xn+1=1n+1xn+(1−1n+1)xn−1\displaystyle x_{n+1}=\frac{1}{n+1} x_n + \left(1-\frac{1}{n+1} \right) x_{n-1} for n≥1n \ge 1.

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

Problem 312*

Evaluate 442−1+4244−1+4448−1+48416−1+⋯\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 (x+1)yz=12, (y+1)zx=4, (z+1)xy=4\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+2012n+2012 divides n2+2012n^2+2012 and n+2013n+2013 divides n2+2013n^2+2013.

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

Problem 315**/***

Determine, with proof, whether the series ∑n=1∞1n2+cos⁡(2πln⁡n)\displaystyle \sum_{n=1}^{\infty} \frac{1}{n^{2+\cos (2 \pi \ln n)}} converges.
(edited 10 years ago)
Original post by Jkn


Ah good! :tongue:

Spoiler



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)! :biggrin:

OK, I won't. :wink:
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 :smile:

Original post by Jkn


Problem 306*

Find all solutions in non-negative integers a,b to a+b=2009\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×287=72×41[br]⇒a+b=7412009=7 \times 287 =7^2 \times 41[br]\Rightarrow \sqrt{a}+\sqrt{b}=7\sqrt{41}
The obvious solutions are therefore:
a=k41⇒a=41k2[br]b=(7−k)41⇒b=41(7−k)2\sqrt{a}=k\sqrt{41} \Rightarrow a=41k^2[br]\sqrt{b}=(7-k)\sqrt{41} \Rightarrow b=41(7-k)^2
k∈{0,1,...,7}k \in \{0,1, . . . ,7\}
To demonstrate that these are the only solutions with the given restrictions, consider:
a+b=2009[br]⇔a+b+2ab=2009[br]⇔(a+b−2009)2=4ab[br]⇒a2+2ab+b2+20092−4018(a+b)=4ab[br]⇒a2−2ab+b2+20092−4018a−4108b=0[br]⇒a2−2(b+2009)a+(b−2009)2=0\sqrt{a}+\sqrt{b} = \sqrt{2009}[br]\Leftrightarrow a+b+2\sqrt{ab}=2009[br]\Leftrightarrow (a+b-2009)^2=4ab[br]\Rightarrow a^2+2ab+b^2+2009^2-4018(a+b)=4ab[br]\Rightarrow a^2-2ab+b^2+2009^2-4018a-4108b=0[br]\Rightarrow a^2-2(b+2009)a+(b-2009)^2=0
Solving for a:
a=2(b+2009)±4(b+2009)2−4(b−2009)22=b+2009±4×2009ba=\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≤a,b≤20090 \leq a,b \leq 2009
⇒a=b+2009−1441b\Rightarrow a=b+2009-14\sqrt{41b}
For this to be an integer, observe that 41b∈Z+\sqrt{41b} \in \mathbb{Z^+} must hold.
Therefore: b=41n2b=41n^2 for some integer n (n≤7)(n \leq 7)
Now we can solve similarly for b and state that:
a=41m2a=41m^2 for some integer m (m≤7)(m \leq 7)
So we find that: a,b\sqrt{a},\sqrt{b} are of the form c41c\sqrt{41}
Whereby the previously found solutions are the only solutions.


Consider the general case:
a+b=c\sqrt{a}+\sqrt{b}=\sqrt{c}
If c=p2qc=p^2q for some integers pp and qq
a+b=pq\sqrt{a}+\sqrt{b}=p\sqrt{q}
Using the same method as above we can deduce that:
Such that:
a=k2qa=k^2q
b=(p−k)2qb=(p-k)^2q
k∈{0,1...,p}k \in \{0,1 . . . ,p\}
If cc is not of the above form then for integer solutions either a=0, b=ca=0 , \ b=c or a=c, b=0a=c, \ b=0
(edited 10 years ago)
Original post by joostan
OK, I won't. :wink:
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 :smile:


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
Original post by FireGarden
Problem 301**

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

arctan⁡(ad+bcac−bd)=arctan⁡(ba)+arctan⁡(dc) \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
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: a+b=pq\sqrt{a}+\sqrt{b}=p\sqrt{q}
In which case:
a=cq[br]b=(p−c)q[br]c∈{0,1,...,p}\sqrt{a}=c\sqrt{q}[br]\sqrt{b}=(p-c)\sqrt{q}[br]c \in \{0,1, . . . ,p \}
which I suspect can be shown after a bit of algebra. :tongue:
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! :frown:

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∞1^{\infty} (a contradiction).

Also, they have not even proven that a solution greater than 2 exists as they are supposing that
lim⁡n→∞(f(n))n=(lim⁡n→∞f(n))lim⁡n→∞n\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 lim⁡n→∞n\displaystyle \lim_{n \to \infty} n does not exists and so the rule cannot be applied. :tongue:



1∞=lim⁡x→∞1x=1[br][br]1∞=lim⁡x→∞(1+1x)x=e[br][br]1≠e  ⟹  1∞≠1∞ 1^{\infty} = \displaystyle\lim_{x\to\infty}1^{x} = 1 [br][br]1^{\infty} = \displaystyle\lim_{x\to\infty} \left(1+\dfrac{1}{x} \right)^{x} = e[br][br]1\not=e \implies 1^{\infty} \not= 1^{\infty}

So 1∞ 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 :s-smilie:.
(edited 10 years ago)
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: a+b=pq\sqrt{a}+\sqrt{b}=p\sqrt{q}
In which case:
a=cq[br]b=(p−c)q[br]c∈{0,1,...,p}\sqrt{a}=c\sqrt{q}[br]\sqrt{b}=(p-c)\sqrt{q}[br]c \in \{0,1, . . . ,p \}
which I suspect can be shown after a bit of algebra. :tongue:


Yup, it's the same algebra, too :smile:
Original post by Smaug123
Yup, it's the same algebra, too :smile:


Okey dokey, I edited it in minus the algebra :laugh:
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 :smile:

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 bn≡an2n>2b_n \equiv \dfrac{a_n^2}{n} > 2 always, after getting a recurrence relation for bnb_n. Also shown previously that bnb_n is strictly decreasing. Now I just need to show that 2 is indeed the limit.
Reply 2119
Avatar for MW24595
MW24595
[QUOTE="Jkn;43834765"]g

Problem 307*

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


Problem 310**

Evaluate ∑m=1∞∑n=1∞m2n3m(n3m+m3n)\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=rsin⁡θ,y=rcos⁡θ x= r \sin {\theta}, y = r \cos {\theta} . Then, r2=x2+y2 r^2 = x^2 + y^2 .

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

xy(x2−y2)=12r4sin⁡2θcos⁡2θ=x2+y2=r2[br][br]⇒r2sin⁡2θcos⁡2θ=2[br][br]⇒r2sin⁡4θ=4[br][br]⇒r2=4sin⁡4θ[br][br]⇒min(x2+y2)=4[br] xy(x^2-y^2) = \frac{1}{2} r^4 \sin {2 \theta} \cos {2 \theta} = x^2 + y^2 = r^2[br][br]\Rightarrow r^2 \sin {2 \theta} \cos {2 \theta} = 2[br][br]\Rightarrow r^2 \sin {4 \theta} = 4[br][br]\Rightarrow r^2 = \frac{4}{\sin {4 \theta}}[br][br]\Rightarrow min(x^2+y^2) = 4[br]


Solution 310

∑m=1∞∑n=1∞m2n3m(n3m+m3n)=12∑m=1∞∑n=1∞(m2n3m(n3m+m3n)+n2m3n(n3m+m3n))[br][br]⇒=12∑m=1∞∑n=1∞(m2n(3nm)+n2m(3mn)3m+n(n3m+m3n))[br][br]⇒=12∑m=1∞∑n=1∞(mn3m+n)[br][br]⇒=12(∑m=1∞m3m)2[br][br] \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)[br][br]\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)[br][br]\Rightarrow = \frac{1}{2} \displaystyle \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \left( \frac{mn}{3^{m+n}}\right)[br][br]\Rightarrow = \frac{1}{2} \left( \displaystyle \sum_{m=1}^{\infty} \frac{m}{3^m} \right)^2[br][br]

Now, note that:

1(1−x)2=∑i=1∞ixi−1[br][br]⇒x(1−x)2=∑i=1∞ixi[br][br]⇒13(23)2=∑m=1∞m3m[br][br]⇒∑m=1∞∑n=1∞m2n3m(n3m+m3n)=12(13(23)2)2=98[br][br] \displaystyle \frac{1}{(1-x)^2} = \sum_{i=1}^{\infty} i x^{i-1}[br][br]\Rightarrow \displaystyle \frac{x}{(1-x)^2} = \sum_{i=1}^{\infty} i x^i[br][br]\Rightarrow \displaystyle \frac{\frac{1}{3}}{(\frac{2}{3})^2} = \sum_{m=1}^{\infty} \frac{m}{3^m}[br][br]\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}[br][br]
(edited 10 years ago)

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you