STEP Maths I,II,III 1987 Solutions

STEP III, Question 16

(a)

Spoiler

(b)

Spoiler

Reply 201

Dystopia

STEP III, Q3.

Spoiler

Nice question. :smile:

I'm still getting used to learning the requirements 'proper proof' so i could be wrong, but doesn't Dystopias' proof that |z| <= |x| + |y| assume that the thing he is trying to proove is already true, thus making the proof invalid?

Reply 202

Oh I Really Don't Care

17

maltodextrin

I'm still getting used to learning the requirements 'proper proof' so i could be wrong, but doesn't Dystopias' proof that |z| <= |x| + |y| assume that the thing he is trying to proove is already true, thus making the proof invalid?

No - he has used the result of another theorem (pythagora's theorem) to arrive at an equality then produce an inequality noting that positive terms can be 'dropped'.

Although if you did want to start with what was true then you would probably just reverse the inequality and arrive at a contradiction - i.e. 2|x||y| <= 0 which is false for all x and y unless x = y = 0

Reply 203

DeanK22

No - he has used the result of another theorem (pythagora's theorem) to arrive at an equality then produce an inequality noting that positive terms can be 'dropped'.

Although if you did want to start with what was true then you would probably just reverse the inequality and arrive at a contradiction - i.e. 2|x||y| <= 0 which is false for all x and y unless x = y = 0

Right i see, thanks!

Reply 204

maltodextrin

I'm still getting used to learning the requirements 'proper proof' so i could be wrong, but doesn't Dystopias' proof that |z| <= |x| + |y| assume that the thing he is trying to proove is already true, thus making the proof invalid?

No. He does start from the statement |z| <= |x| + |y|, but he is careful to make sure the implications run both ways for the following statements (so the argument works backwards). Note the use of

\Leftrightarrow

instead of

\implies

.

In other words, you can start from 2|x||y| >=0 and use the argument to show |z| <= |x|+|y|.

This is actually a pretty common situation when proving inequalities; typically you're asked to prove "f <= g", and you're going to manipulate it until you get to something "h >= 0" that is obviously true. Since you don't know at the start what h is going to be, you pretty much have to start at the "wrong end". Once you get to "h >=0", you could write everything out backwards in order to prove "f<=g". But it's a lot quicker to simply use the

\Leftrightarrow

symbol, or even

\Leftarrow

.

Reply 205

DFranklin

No. He does start from the statement |z| <= |x| + |y|, but he is careful to make sure the implications run both ways for the following statements (so the argument works backwards). Note the use of

\Leftrightarrow

instead of

\implies

.

In other words, you can start from 2|x||y| >=0 and use the argument to show |z| <= |x|+|y|.

This is actually a pretty common situation when proving inequalities; typically you're asked to prove "f <= g", and you're going to manipulate it until you get to something "h >= 0" that is obviously true. Since you don't know at the start what h is going to be, you pretty much have to start at the "wrong end". Once you get to "h >=0", you could write everything out backwards in order to prove "f<=g". But it's a lot quicker to simply use the

\Leftrightarrow

symbol, or even

\Leftarrow

.

That's an excellent explanation, I suspected the double implication signs had something to do with it. Because in effect I'm starting from 2|x||y| >=0 do I need to write a statement by it that looks like i have worked that way round. i.e. Should I be writing 'I start with a statement that I know to be true 2|x||y| >= 0' instead of '2|x||y| >= 0, which is true' like Dystopia wrote.

Reply 206

What Dystopia wrote is completely fine. Although in some sense it is "cleaner" to go:

2|x||y|\ge 0 \implies |x|^2+|y|^2 \le |x|^2+|y|^2 + 2|x||y|

\implies |z|^2\le (|x|+|y|)^2 \implies |z|\le |x|+|y|

there is absolutely no need to do so, and arguably it's actually better style to go in the direction Dystopia did, since it actually shows what is going on. (Whereas if you start with "We know 2|x||y| >= 0" the proof might be shorter, and slightly more logical, but people would wonder "where on earth did that starting point come from?").

Reply 207

nota bene

15

DFranklin

What Dystopia wrote is completely fine. Although in some sense it is "cleaner" to go:

2|x||y|\ge 0 \implies |x|^2+|y|^2 \ge |x|^2+|y|^2 + 2|x||y|

Sign error or \ge instead of \le ?

Reply 208

nota bene

Sign error or \ge instead of \le ?

Stupidly sticking with \ge just because I'd used it for the first inequality...

Reply 209

I was wondering if this would be acceptable answer for STEP III Question 1 or whether i've written a load of nonsense.

First checking n = 4 (n - 1)! = 6 4 does not divide 6, so 4 belongs to the set.

Now let n be a positive non-prime integer greater than 4 and let p1.p2.p3....pr be the prime factorisation of n. Clearly all of p1.p2.p3....pr are integers less than n, but (n - 1)! is the product of all integers less than n and so p1.p2.p3....pr|(n - 1)! thus n|(n - 1)!

If n is prime assume that (n - 1)! = a.n for some integer a. Let p1p2...pk be the prime factorisation of (n - 1)! Obviously n is not a multiple of any combination of primes and so this implies that a = (n - 1)! and n = 1, this is a contradiction as we stated that n was prime thus when n is prime does not divide (n - 1)!.

So the full set is 4 and all primes

Reply 210

maltodextrin

Now let n be a positive non-prime integer greater than 4 and let p1.p2.p3....pr be the prime factorisation of n. Clearly all of p1.p2.p3....pr are integers less than n, but (n - 1)! is the product of all integers less than n and so p1.p2.p3....pr|(n - 1)! thus n|(n - 1)!This isn't sufficient - it is possible that some of p1, ..., p_r are duplicates in which case your argument doesn't show their product divides (n-1)!

Another (instructive) way of seeing there's a problem with your argument: You don't ever use the fact that n is greater than 4. So suppose n = 4 and find the point at which your argument breaks down.

Reply 211

DFranklin

This isn't sufficient - it is possible that some of p1, ..., p_r are duplicates in which case your argument doesn't show their product divides (n-1)!

Another (instructive) way of seeing there's a problem with your argument: You don't ever use the fact that n is greater than 4. So suppose n = 4 and find the point at which your argument breaks down.

So the product of primes is unnecessary and you can just say n = xy and consider what happens when x = y. Great I can see the solution now.

Could the advice in your second paragraph be applied to any kind of proof where there is an extra condition such as n must be greater than some number for this to work, i.e should my proof always make it obvious why it won't work for n less than or equal to this number? Thanks

Reply 212

1987PAPER1I.no.11.pdf48.4KB

It's not necessary to show why your proof doesn't work for n < 5 (or whatever the condition is for some other problem), but it is generally a good idea to keep it in mind - it both serves as a check and will often give some hint as to how to approach the overall problem. Certainly in this case it is quite a tipoff to an examiner that "something is wrong" with your answer if the argument appears to work for n = 4.

One word of warning: it is not particularly unusual to get asked to prove something for n > 10 (for example), when in fact is is also true for n > 7; it's just that it is easier to prove the n > 10 case. So it's not automatically an issue if your argument seems to work for n <= 10. But it would be an issue if it seems to work for n = 10 and you can see that it's not actually true for n = 10. (In other words, the thing that "kills" your argument for this question isn't just that it seems to work for n = 4, but that it can't really work, because 4 doesn't divide 3!)

Reply 213

brianeverit

9

1987 Paper 2 no.11

Reply 214

steppity-step

7

SimonM

STEP III, Question 16

(b)

Spoiler

Does this seem ok as an alternative or have I made a mistake?

P = Probability exactly 1 person wins (and so I keep my job)

Unparseable latex formula:

\\[br]P = 4000000p(1-p)^{3999999} \\ \\[br]\frac{dP}{dp} = 4000000[(1-p)^{3999999} - 3999999p(1-p)^{3999998}] = 0\: when\: P \: at\: max \\ \\[br](1-p)^{3999999} = 3999999p(1-p)^{3999998} \\ \\[br]1-p=3999999p \\ \\[br]p=\frac{1}{4000000} \\ \\[br]so\: P_{max} = 4000000 * \frac{1}{4000000} (1 - \frac{1}{4000000})^{3999999} = (1 - \frac{1}{4000000})^{3999999} \approx (1 - \frac{1}{4000000})^{4000000} \approx \frac{1}{e} \ll \frac{3}{5}

The thing that makes me think I've made a mistake is that yours is so much closer to 60%. Let me know what you think.

Reply 215

SimonM

OP

Two people can win and you'll keep your job.

I think I tried your method when I did it, but I couldn't get it out close enough to what I was hoping for

Reply 216

steppity-step

7

SimonM

Two people can win and you'll keep your job.

I think I tried your method when I did it, but I couldn't get it out close enough to what I was hoping for

Ah yes it says more than two. Silly me.

Reply 217

steppity-step

7

brianeverit

1987 STEP Fma numbers 12 -16

Mistake on question 16, it wants the probability both A and B are in the fridge, so it's

\frac{pq}{1-p-q+3pq}

. RTQ!

Reply 218