The Student Room Group

The Proof is Trivial!

Scroll to see replies

Reply 20
Solution 3

The condition is equivalent to 01(1xn)1mdx=01(1xm)1ndx\displaystyle \int_{0}^{1} (1-x^n)^{\frac{1}{m}}dx=\int_{0}^{1} (1-x^m)^{\frac{1}{n}}dx. After the substitutions xxmx \mapsto x^m and xxnx \mapsto x^n, we have to prove that 01mxm1(1xmn)1mdx=01nxn1(1xmn)1ndx\displaystyle \int_{0}^{1} mx^{m-1}(1-x^{mn})^{\frac{1}{m}}dx= \int_{0}^{1} nx^{n-1}(1-x^{mn})^{\frac{1}{n}}dx. Now let x(1x)1mn\displaystyle x \mapsto (1-x)^{\frac{1}{mn}}. Hence 01mxm1(1xmn)1mdx=011n(1x)1n1x1mdx\displaystyle \int_{0}^{1} mx^{m-1}(1-x^{mn})^{\frac{1}{m}}dx= \int_{0}^{1} \frac{1}{n} (1-x)^{\frac{1}{n}-1} x^{\frac{1}{m}}dx, 01nxn1(1xmn)1ndx=011m(1x)1nx1m1dx\displaystyle \int_{0}^{1} nx^{n-1}(1-x^{mn})^{\frac{1}{n}}dx= \int_{0}^{1}\frac{1}{m}(1-x)^{\frac{1}{n}}x^{\frac{1}{m}-1}dx. Finally, integrating by parts, for example, 011m(1x)1nx1m1dx\displaystyle \int_{0}^{1}\frac{1}{m}(1-x)^{\frac{1}{n}}x^{\frac{1}{m}-1}dx, we see that the equality holds true.
Reply 21
Original post by ukdragon37
As expected, the problems I'm interested in are more quaint than the usual :tongue: Here's one that's strange but rather easy once you get it.

Problem 6**/***

Let Nω=N{ω}\mathbb{N}_\omega = \mathbb{N} \cup \{\omega\} where we define for all nNωn \in \mathbb{N}_\omega, ωn\omega \geq n. For any set SNωS \subseteq \mathbb{N}_\omega we write S\sqcup S to denote the smallest member of Nω\mathbb{N}_\omega such that Sn\sqcup S \geq n for all nSn \in S. (Hence Nω=ω\sqcup\mathbb{N}_\omega = \omega.)

Let f:NωNωf:\mathbb{N}_\omega \to \mathbb{N}_\omega be a function such that:

For all m, n, mn    f(m)f(n)m \leq n \implies f(m) \leq f (n).

For all S={a1,a2,}NωS = \{a_1, a_2, \dots\} \subseteq \mathbb{N}_\omega, we have f(S)={f(a1),f(a2),}f(\sqcup S) = \sqcup\{f(a_1), f(a_2), \dots\}.



Show that the value F given by F={fn(1)nN{0}}F = \sqcup\left\{f^n(1)|n \in \mathbb{N}\cup\{0\}\right\} satisfies f(F)=Ff(F) = F and is the smallest member of Nω\mathbb{N}_\omega to do so.

Just to clarify... Nω\mathbb{N}_\omega is the set of natural numbers up to and including ω\omega, and S\sqcup S is the greatest element of any subset SS of Nω\mathbb{N}_\omega or in case of the empty set it is 1?

I see why that is the case but the problem for me here will be clarity and rigour in how I present the proof.
(edited 10 years ago)
Original post by und
Just to clarify... Nω\mathbb{N}_\omega is the set of natural numbers up to and including ω\omega, and S\sqcup S is the greatest element of any subset SS of Nω\mathbb{N}_\omega or in case of the empty set it is 1?

I see why that is the case but the problem for me here will be clarity and rigour in how I present the proof.


Yes all you said is correct. :smile:

EDIT: Actually just a slight clarification/correction: suppose SS is infinite but does not include ω\omega, in this case S\sqcup S is still clearly ω\omega so your definition that it is the "the greatest element of any subset SS of Nω\mathbb{N}_\omega" is not technically right.
(edited 10 years ago)
Original post by ukdragon37
Actually just a slight clarification/correction: suppose SS is infinite but does not include ω\omega, in this case S\sqcup S is still clearly ω\omega so your definition that it is the "the greatest element of any subset SS of Nω\mathbb{N}_\omega" is not technically right.


But how can SS be infinite if SNω?S\subseteq \mathbb{N}_{\omega}?
Reply 24
One simple number theory problem.

Problem 7*

Let p\displaystyle p be a prime number. Find all triples of positive integers (a,b,p)\displaystyle (a,b,p) such that 2a+pb=19a\displaystyle 2^{a}+p^{b}=19^{a}.

@ukdragon37 I am still unable to comprehend your definition of Nω\mathbb{N}_\omega. Can we write Nω={αα{N{ω}},αω}\mathbb{N}_\omega = \{ \alpha | \alpha\in \{\mathbb{N} \cup \{\omega\}\}, \alpha \le \omega \}? And if this is the case, then is Nω\mathbb{N}_\omega not finite?
Original post by Lord of the Flies
But how can SS be infinite if SNω?S\subseteq \mathbb{N}_{\omega}?


For example let SS be all the even numbers.

Original post by Mladenov

@ukdragon37 I am still unable to comprehend your definition of Nω\mathbb{N}_\omega. Can we write Nω={αα{N{ω}},αω}\mathbb{N}_\omega = \{ \alpha | \alpha\in \{\mathbb{N} \cup \{\omega\}\}, \alpha \le \omega \}? And if this is the case, then is Nω\mathbb{N}_\omega not finite?


:confused: I'm not sure what you are trying to do. All am saying is Nω\mathbb{N}_\omega is the same as the set of natural numbers except with the addition of an "infinity" ω\omega element that is defined to be geq all the naturals (and trivially geq itself). Nω\mathbb{N}_\omega is definitely infinite.
(edited 10 years ago)
Original post by joostan
x

Solution 5
I can't even begin to comprehend ukD's question so here's joostan's :ninja:

part i



S_1



S_2

(edited 10 years ago)
Reply 27
Original post by Felix Felicis
Solution 5
I can't even begin to comprehend ukD's question so here's joostan's :ninja:

part i



S_1



S_2


The first part was a warm up, to get you thinking about De Moivre's Theorem, some people need a hint Felix :tongue:- Lol same about ukD's :redface:
Original post by Felix Felicis
I can't even begin to comprehend ukD's question so here's joostan's :ninja:


Objectively the difficulty of actually doing the question I think is lower than a lot of the interesting techniques that I know people here are capable of (and in fact it only relies on A-level knowledge and manipulation on sets). It's just the material seems alien since nobody at high school level, even STEP, emphasises set theory to any depth. :sigh: It's a trend that I think should change, especially if we want to be able to produce the next generation of theoretical computer scientists.
Reply 29
Partial Solution 6

The first assertion is true since f(F)={fn+1(1)nN{0}}f(F) = \sqcup\left\{f^{n+1}(1)|n \in \mathbb{N}\cup\{0\}\right\}, and f(1)1f(1)\ge 1
I shall edit, if I manage to prove that FF is the smallest element such that f(F)=Ff(F)=F.
By induction, we obtain fn(1)fn+1(1)f^{n}(1)\le f^{n+1}(1). Now suppose that there is FF' such that:
F<FF' < F;
f(F)=Ff(F')=F'.
Then there is mm with F=fm(1)=f(fm(1))F'=f^{m}(1)=f(f^{m}(1)). Therefore, for every n>mn>m, we have fn(1)fm(1)f^{n}(1)\le f^{m}(1) - contradiction.
(edited 10 years ago)
Original post by joostan
The first part was a warm up, to get you thinking about De Moivre's Theorem, some people need a hint Felix :tongue:- Lol same about ukD's :redface:

Ha, fair enough :wink:

Original post by ukdragon37
Objectively the difficulty of actually doing the question I think is lower than a lot of the interesting techniques that I know people here are capable of (and in fact it only relies on A-level knowledge and manipulation on sets). It's just the material seems alien since nobody at high school level, even STEP, emphasises set theory to any depth. :sigh: It's a trend that I think should change, especially if we want to be able to produce the next generation of theoretical computer scientists.

Sets does look quite interesting, definitely something to look at over the summer :tongue:
Reply 31
Original post by ukdragon37
Objectively the difficulty of actually doing the question I think is lower than a lot of the interesting techniques that I know people here are capable of (and in fact it only relies on A-level knowledge and manipulation on sets). It's just the material seems alien since nobody at high school level, even STEP, emphasises set theory to any depth. :sigh: It's a trend that I think should change, especially if we want to be able to produce the next generation of theoretical computer scientists.


IMHO it looks like a horrendous mess of notation :s-smilie:
But still, I agree things like groups, sets and rings seem fascinating and applicable. :smile:
Reply 32
Problem 8*

A harder version of problem 0. Prove that for any n, it is possible to fine n consecutive integers such that none of them are prime powers.
Original post by joostan
IMHO it looks like a horrendous mess of notation :s-smilie:
But still, I agree things like groups, sets and rings seem fascinating and applicable. :smile:


To be fair, I am trying to sneak in a few interesting concepts, which is why I had to expend notation defining them. :tongue: But this kind of question is very much like what a nasty university examiner (or even interviewer :wink: ) would give you - define some new concepts and see what you can make of them.

Spoiler

Original post by ukdragon37
To be fair, I am trying to sneak in a few interesting concepts, which is why I had to expend notation defining them. :tongue: But this kind of question is very much like what a nasty university examiner (or even interviewer :wink: ) would give you - define some new concepts and see what you can make of them.

Spoiler


I can see you being a totally nasty supervisor to the undergrads at Cornell :tongue:
Original post by Felix Felicis
I can see you being a totally nasty supervisor to the undergrads at Cornell :tongue:


They don't have supervisions there, only recitations to medium-sized groups where the grad student demonstrates example questions. I don't get to actually set the questions for undergrads. :sad:
Original post by ukdragon37
They don't have supervisions there, only recitations to medium-sized groups where the grad student demonstrates example questions. I don't get to actually set the questions for undergrads. :sad:

Aww :frown: You'll have your dictatiorial rise to power some day :tongue:
Original post by Felix Felicis
Aww :frown: You'll have your dictatiorial rise to power some day :tongue:


I look forward to it :tongue:

Original post by Mladenov
Partial Solution 6

The first assertion is true since f(F)={fn+1(1)nN{0}}f(F) = \sqcup\left\{f^{n+1}(1)|n \in \mathbb{N}\cup\{0\}\right\}, and f(1)1f(1)\ge 1
I shall edit, if I manage to prove that FF is the smallest element such that f(F)=Ff(F)=F.
By induction, we obtain fn(1)fn+1(1)f^{n}(1)\le f^{n+1}(1). Now suppose that there is FF' such that:
F<FF' < F;
f(F)=Ff(F')=F'.
Then there is mm with F=fm(1)=f(fm(1))F'=f^{m}(1)=f(f^{m}(1)). Therefore, for every n>mn>m, we have fn(1)fm(1)f^{n}(1)\le f^{m}(1) - contradiction.


Nearly there, you want to make the last bit clearer. For example it is not a contradiction if f is a constant function. But I'm glad someone is able to look beyond the notation and make quite a bit of headway. :tongue:
Reply 38
Original post by ukdragon37

Nearly there, you want to make the last bit clearer. For example it is not a contradiction if f is a constant function. But I'm glad someone is able to look beyond the notation and make quite a bit of headway. :tongue:


Let me try again.

Solution 6

Firstly, f(F)={fn+1(1)nN{0}}\displaystyle f(F) = \sqcup\left\{f^{n+1}(1)|n \in \mathbb{N}\cup\{0\}\right\}, and f(1)1f(1)\ge 1 lead to f(F)=Ff(F)=F
Secondly, by induction, we obtain fn(1)fn+1(1)\displaystyle f^{n}(1)\le f^{n+1}(1). Consequently, {fn(1)nN{0}}\displaystyle \left\{f^n(1)|n \in \mathbb{N}\cup\{0\}\right\} is a directed complete partial order, and its supremum is obviously FF.
If ff is a constant, let f(n)=αf(n)= \alpha for some αNω\alpha \in \mathbb{N}_\omega. Then obviously the smallest nNωn \in \mathbb{N}_\omega such that f(n)=n\displaystyle f(n)=n is n=αn=\alpha. Furthermore, F=αF=\alpha.
Now suppose that ff is not a constant function. Suppose also that there is FF' such that:
F<FF' < F;
f(F)=Ff(F')=F'.
Then there is mm with F=fm(1)=f(fm(1))F'=f^{m}(1)=f(f^{m}(1)). Therefore, for every n>mn>m, we have fn(1)fm(1)f^{n}(1)\le f^{m}(1), which implies that FF is not the supremum of {fn(1)nN{0}}\displaystyle \left\{f^n(1)|n \in \mathbb{N}\cup\{0\}\right\}.
Solution 7:

Spoiler

(edited 10 years ago)

Quick Reply