HSC Stuff > HSC Mathematics Extension 1
Inequality Induction
edmododragon:
--- Quote from: Lottie99 on October 07, 2016, 02:54:10 pm ---I have an excessive amount of inequalities questions that I dont understand.
Here is another one :)
Thank you so much
--- End quote ---
Like Rui said, these types of induction questions are uncommon even in the Ext2 course. They require you to consider what actually happens in the geometric conditions provided.
Here's my working for it.
Firstly, to create the "greatest" number of regions, none of the lines can be parallel (or the same line).
We want to somehow create a link between the number of regions and the expression given. To do this we want to establish a pattern. This can be done by simply drawing and seeing what happens to the number of regions for n amount of lines.
We get:
n=1 makes 2
n=2 makes 4
n=3 makes 7
n=4 makes 11
As we can see, each new line seems to add the amount of regions as the number of line it is, starting with 2 regions for 1 line. We can turn this into a pattern. The number of regions for n lines is 1 + (1 + 2 + 3... + n). Using the sum of an arithmetic series, this can be simplified to 1 + n(n+1)/2 = (n^2 + n + 2)/2. We got the expression given! So we're on the right track.
Now realise we haven't actually proven this expression for n is equal to the number of regions for n lines. we've just noticed a pattern for the first few cases. This is where the induction comes in. For case n=1, there are two regions. (1+1+2)/2 + 2. Proven for initial case.
Assume that for k lines, there are (k^2+k+2)/2 regions.
For the case for k+1 lines, we're trying to prove there are [(k+1)^2+k+1+2)/2 = (k^2+3k+4)/2 regions.
Now what happens when we have k+1 lines? We added an extra line in. As mentioned before, it seems to add k+1 regions. How do we prove this? Notice that the added line will cut k lines, since it isn't parallel to any of them. As it cuts each line, it will split each region the line is in, into two, essentially adding another region, however adding that line itself split the overall circle in two, which adds another region. This means that one region is added, plus one region for every line it crosses. That's k+1 regions added! So for the case n=k+1, the number of regions is equal to the number of regions in the case n=k and then with k+1 regions added.
That's (k^2+k+2)/2 + k + 1 = (k^2+3k+4)/2
True for n=k+1 when true for n=k
True for n=1
Proven by induction :)
I hope my working wasn't too hard to follow. You can see why they don't ask these questions anymore.
RuiAce:
Yes that proof is right. I revised over a proof I did recently and it's similar.
An observation to be made: The maximum number of lines is achieved when no three lines are concurrent as well as being non-parallel. That is to say, no three lines meet at the same point.
This is crucial - This is how we ensure that the maximum amount of regions is always achieved. It is how we ensure that the nth line divides out n new regions.
edmododragon:
--- Quote from: RuiAce on October 07, 2016, 03:49:42 pm --- Yes that proof is right. I revised over a proof I did recently and it's similar.
An observation to be made: The maximum number of lines is achieved when no three lines are concurrent as well as being non-parallel. That is to say, no three lines meet at the same point.
This is crucial - This is how we ensure that the maximum amount of regions is always achieved. It is how we ensure that the nth line divides out n new regions.
--- End quote ---
Woops yeah I missed that. I've seen this question before without the "circle" and just lines forming regions on a plane.
RuiAce:
--- Quote from: edmododragon on October 07, 2016, 03:54:07 pm ---Woops yeah I missed that. I've seen this question before without the "circle" and just lines forming regions on a plane.
--- End quote ---
Exactly. The proof is virtually identical to the one without the circle. It's basically trying to see how well you know your partitioning
These things were all taken out of the HSC in 2001.
I also realised that the question came out of the old Fitzpatrick textbook, which I don't like
Lottie99:
This has all just gone way over my head haha
I think I'll stick to just doing past Ext1 Papers
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version