HSC 2015 MX2 Marathon ADVANCED (archive) (4 Viewers)

simpleetal · Jul 11, 2015

Re: HSC 2015 4U Marathon - Advanced Level

this is a good question, a little easier than the questions which are usually presented here, but harder than the questions on the other thread.
$Show that there are no more than 2005 real numbers x so that $ \ a_{2003}x^{2006}+a_{2002}x^{2005}+...+a_{0}x^3+x^2+x+1=0 $ where a_{2003}, a_{2002}....a_{0} $ \ $are real numbers$

Sy123 · Jul 11, 2015

Re: HSC 2015 4U Marathon - Advanced Level

simpleetal said:
this is a good question, a little easier than the questions which are usually presented here, but harder than the questions on the other thread.
$Show that there are no more than 2005 real numbers x so that $ \ a_{2003}x^{2006}+a_{2002}x^{2005}+...+a_{0}x^3+x^2+x+1=0 $ where a_{2003}, a_{2002}....a_{0} $ \ $are real numbers$

$\\ $Suppose there is a polynomial$ \ P(x) = 1 + x + x^2 + \sum_{k=3}^n a_kx^k \ $and all of the roots$ \ r_1,r_2,\dots,r_n \ $are real$ \\ \\ $Then,$ \\\\ \prod_{k=1}^n r_k = \frac{1}{a_n} \ (*) \\ \\ \sum_{k=1}^n \frac{\prod_{j=1}^n r_j}{r_k} = \frac{-1}{a_n} \ (**) \\ \\ \sum_{1\leq i\neq j \leq n} \frac{\prod_{k=1}^nr_k}{r_ir_j} = \frac{1}{a_n} \ (***)$

$\\ $Using$ \ (*) \ $transform$ \ (**) \ $into$ \ \sum_{k=1}^n \frac{1}{r_k} = -1$

$\\ $Using$ \ (*) \ $transform$ \ (***) \ $into$ \ \sum_{1 \leq i \neq j \leq n} \frac{1}{r_ir_j} = 1$

$\\ \Rightarrow \ (-1)^2 = \left( \sum_{k=1}^n \frac{1}{r_k} \right)^2 = \sum_{k=1}^n \frac{1}{r_k^2} + 2\sum_{1 \leq i \neq j \leq n} \frac{1}{r_ir_j} \\ \\ \Rightarrow 1 = \sum_{k=1}^n \frac{1}{r_k^2} + 2 (1) \\ \\ \Rightarrow \sum_{k=1}^n \frac{1}{r_k^2} = - 1$

$\\ $Contradiction as$ \ r_k^2 > 0 \ $for all$ \ k=1,2,\dots,n \ $and hence$ \ \sum_{k=1}^n \frac{1}{r_k^2} > 0$

$\\ $Therefore, the number of real roots cannot be$ \ n \ $for$ \ P(x) \\ \\ $Meaning there must be at most$ \ n-1 \ $real roots$$

$\\ $Set$ \ n=2006 \ $and the proof is complete$$

andrew12678 · Jul 11, 2015

Re: HSC 2015 4U Marathon - Advanced Level

RealiseNothing · Jul 11, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Sy123 said:
$\\ $Prove that there is no integer$ \ n \ $so that:$ \ (n-3)^3 + n^3 = (n+3)^3$

Just saw this.

Take any cube mod 10 and you get 0,1,8,7,6,5,4,3,2,9... as your cycle.

From here it is obvious that the equation can't have an integer solution.

simpleetal · Jul 12, 2015

Re: HSC 2015 4U Marathon - Advanced Level

andrew12678 said:
View attachment 32199

Saw this just then, just a quick note that these days the responses may be slow because year 12s have trials, university is getting busy and some people like me don't log on very often. Regardless, here is the soln.
$$ai) By definition$, \frac{y_{n}}{y_{n-1}}= \frac{n^3(2^{n-1})}{2^n(n-1)^3}. \\ $This equals$ \frac{(n)^3}{2(n-1^3)}. \ = \frac{(1+\frac{1}{n-1})^3}{2}. \ $If 4\geq n\geq 2,$ $then$ \frac{1}{n-1}\geq 1/3. $So this means that$ \frac{y_{n}}{y_{n-1}}\geq \frac{1}{2}(4/3)^3> 1/2(2)=1. $If n\geq 5, then$ \frac{y_{n}}{y_{n-1}}\leq \frac{1}{2}(1+\frac{1}{4})^3< 1 \\ $aii) Notice that,$ \frac{y_{n}}{y_{n-1}}= \frac{(1+\frac{1}{n-1})^3}{2}. $But,$ \frac{1}{n-1} $decreases as n grows.$ \ $So,$ \frac{(1+\frac{1}{n-1})^3}{2}$ decreases as n increases. For n = 5, we get that $\frac{y_{n}}{y_{n-1}}= \frac{(1+\frac{1}{n-1})^3}{2} <0.98 \ $and so as n increases (from 5) $\frac{y_{n}}{y_{n-1}} $will always be less than 0.98.$ \\$aiii) Do base case when n=4. we'll use induction. From part ii we know that $ y_{n+1}\leq 0.98y_{n}\leq 0.98(4(0.98)^{n-4})$(by inductive hypothesis)$=4(0.98)^{n-3} \ $As n approaches infinity, we get that the $y_{n} \ $ approaches 0, since $ (0.98)^{n-4} $approaches 0$.$

simpleetal · Jul 12, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Sy123 said:
$\\ $Suppose there is a polynomial$ \ P(x) = 1 + x + x^2 + \sum_{k=3}^n a_kx^k \ $and all of the roots$ \ r_1,r_2,\dots,r_n \ $are real$ \\ \\ $Then,$ \\\\ \prod_{k=1}^n r_k = \frac{1}{a_n} \ (*) \\ \\ \sum_{k=1}^n \frac{\prod_{j=1}^n r_j}{r_k} = \frac{-1}{a_n} \ (**) \\ \\ \sum_{1\leq i\neq j \leq n} \frac{\prod_{k=1}^nr_k}{r_ir_j} = \frac{1}{a_n} \ (***)$

$\\ $Using$ \ (*) \ $transform$ \ (**) \ $into$ \ \sum_{k=1}^n \frac{1}{r_k} = -1$

$\\ $Using$ \ (*) \ $transform$ \ (***) \ $into$ \ \sum_{1 \leq i \neq j \leq n} \frac{1}{r_ir_j} = 1$

$\\ \Rightarrow \ (-1)^2 = \left( \sum_{k=1}^n \frac{1}{r_k} \right)^2 = \sum_{k=1}^n \frac{1}{r_k^2} + 2\sum_{1 \leq i \neq j \leq n} \frac{1}{r_ir_j} \\ \\ \Rightarrow 1 = \sum_{k=1}^n \frac{1}{r_k^2} + 2 (1) \\ \\ \Rightarrow \sum_{k=1}^n \frac{1}{r_k^2} = - 1$

$\\ $Contradiction as$ \ r_k^2 > 0 \ $for all$ \ k=1,2,\dots,n \ $and hence$ \ \sum_{k=1}^n \frac{1}{r_k^2} > 0$

$\\ $Therefore, the number of real roots cannot be$ \ n \ $for$ \ P(x) \\ \\ $Meaning there must be at most$ \ n-1 \ $real roots$$

$\\ $Set$ \ n=2006 \ $and the proof is complete$$

Yep, this was essentially the same as what I did. You can motivate this by the observation that the only the coefficients of the last 3 terms stay the same, and since the question is asking about the roots, I figured that the relationship between roots and the coefficients (or vieta's formula) would be the way to go.

glittergal96 · Jul 13, 2015

Re: HSC 2015 4U Marathon - Advanced Level

$Suppose we have $n$ lines in a plane, no pair of which are parallel. Given that there is no point in the plane that they all pass through, what is the minimum number of points of intersection?$

Drsoccerball · Jul 13, 2015

Re: HSC 2015 4U Marathon - Advanced Level

glittergal96 said:
$Suppose we have $n$ lines in a plane, no pair of which are parallel. Given that there is no point in the plane that they all pass through, what is the minimum number of points of intersection?$

n+1?

InteGrand · Jul 13, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Drsoccerball said:
n+1?

That doesn't work for (say) n = 2.

Drsoccerball · Jul 13, 2015

Re: HSC 2015 4U Marathon - Advanced Level

InteGrand said:
That doesn't work for (say) n = 2.

But for n=2 it has one intersection point therefore its excluded

InteGrand · Jul 13, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Drsoccerball said:
But for n=2 it has one intersection point therefore its excluded

Ah right.

Drsoccerball · Jul 13, 2015

Re: HSC 2015 4U Marathon - Advanced Level

InteGrand said:
Ah right.

The answer might be n tbh

glittergal96 · Jul 13, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Drsoccerball said:
The answer might be n tbh

Indeed it might be, but without proof you will never know

.

Drsoccerball · Jul 13, 2015

Re: HSC 2015 4U Marathon - Advanced Level

glittergal96 said:
Indeed it might be, but without proof you will never know .

You just draw lines everywhere

glittergal96 · Jul 14, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Drsoccerball said:
You just draw lines everywhere

I wish maths was that easy

.

Sy123 · Jul 14, 2015

Re: HSC 2015 4U Marathon - Advanced Level

I hope this is valid

glittergal96 said:
$Suppose we have $n$ lines in a plane, no pair of which are parallel. Given that there is no point in the plane that they all pass through, what is the minimum number of points of intersection?$

$\\ $Suppose that the plane$ \ P_n \ $has some arrangement of lines no pair of which is parallel, and they do not all pass through a single point, and let the number of intersection points be at most$ \ n-1 \\\\ $Let the proposition that this is possible be$ \ \rho_n \ $and$ \ n \geq 3$

$\\ $Remove a line in$ \ P_n \ $that intersects the most other lines (case 1) (or the arrangement is such that all lines intersect a single point bar one, in which case remove one of the lines that goes through the common intersection (case 2)).$$

$\\ $Case 1: Since the line intersects most other lines, removing it will give a plane$ \ P_{n-1} \ $that removes at least 1 intersection point, therefore$ \ P_{n-1} \ $has at most$ \ n-2 \ $intersection points therefore$ \ \rho_n \Rightarrow \rho_{n-1}$

$\\ $Case 2: In such specific case, removing a line going through the 'major' intersection point doesn't change (if$ \ n > 3 $) the existence of that intersection point, however it will remove the intersection point between that line and the line that doesn't go through the major intersection point, meaning 1 intersection point has gone, meaning there are precisely$ \ n-2 \ $intersection points remaining, therefore$ \ \rho_n \Rightarrow \rho_{n-1}$

$\\ $Therefore,$

$\\ \textbf{1.} \ \rho_{n} \Rightarrow \rho_{n-1} \ $for$ \ n > 3$

$\\ \textbf{2.} \therefore \ \rho_n \Rightarrow \rho_3 \ $(iterate (1)$ \ n-2 \ $times)$$

$\\ \textbf{3.} \ \rho_3 \ $is not true, as one cannot arrange three lines that intersect in total two times, for a more precise formulation, see A.1$$

$\\ \textbf{4.} \therefore \rho_n \ $is not true (modus tollens), meaning it is impossible to have in total$ \ n-1 \ $intersection points$$

$\\ \textbf{5.} $ It is possible to have$ \ n \ $intersection points, by making all the lines intersect in one major intersection point, and having a single line going through the rest, for a precise formulation see A.2$$

$\\ \textbf{6.} $ Therefore, there are at minimum$ \ n \ $intersection points$$

----------------------------------------

$\\ \textbf{A.1} $ To show this fact, place two lines in the plane that are non-parallel, therefore they must intersect at exactly one point. One can put the third line anywhere on this plane as long as it does not intersect this already established intersection point. Since the gradient of the third line is distinct from the other two, it must intersect the other two lines. If it intersects the other two lines in the same place, then the other two lines also intersect there, but since they already have one intersection point, this leads to the absurdity of the two original lines having two intersection points, which is impossible.$$

$\\ \textbf {A.2} $ Consider the set of lines in the cartesian plane$ \ y = 0, y = 1 + kx \ $for$ \ k=1,2,\dots,{n-1} \ $the intersection points are$ \ (1,0) \ $and$ \ \left(-\frac{1}{k},0 \right) \ $for$ \ k=1,2,\dots , n-1 \ $which are all distinct points, meaning there are$ \ n \ $intersection points$$

glittergal96 · Jul 14, 2015

Re: HSC 2015 4U Marathon - Advanced Level

This kind of argument seems the logical approach (I haven't solved this problem satisfactorily to myself yet btw). Why does removing a line with a maximal number of intersection points on it necessarily remove intersection points though? And also why should your two cases exhaust the possibilities?

(I think the answer is surely n, but proving optimality could be slightly tricky.)

Sy123 · Jul 14, 2015

Re: HSC 2015 4U Marathon - Advanced Level

glittergal96 said:
This kind of argument seems the logical approach (I haven't solved this problem satisfactorily to myself yet btw). Why does removing a line with a maximal number of intersection points on it necessarily remove intersection points though? And also why should your two cases exhaust the possibilities?

(I think the answer is surely n, but proving optimality could be slightly tricky.)

(taking the word degree to describe the number of lines that goes through a specific intersection point)

It is sufficient to prove that there is at least one intersection point of degree 2, because if there is, one can just remove a line that goes through there, which in turn removes that intersection point (since removing a line decreases the degree by 1, and no intersection point can have degree 1).

I have a strong intuition that it is indeed the case that there is always at least 1 point of degree 2, but I'm not sure yet how to prove this (if I was to guess it would be a clever invocation of the pidgeonhole principle)

glittergal96 · Jul 14, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Yep, I had the same idea.

SilentWaters · Jul 15, 2015

Re: HSC 2015 4U Marathon - Advanced Level

I would like to propose my own solution to the lines-in-a-plane problem. It's a simple two-case interpretation, which I hope it's comprehensive.

Looking at our definitions, we know that parallel lines never meet in a plane. Any one non-parallel line, therefore, will meet all other lines of similar nature, once within the plane. These intersections can be shared by two or more lines, but if any one line does not share an intersection with any other line within the plane, it must intersect it once elsewhere.

We start off with 2 non-parallel lines, introducing our first intersection to the plane. From here, the minimum number of added intersections with the next line would be 0, by sharing the first intersection with the other lines. However, since we have to exclude at least 1 line from the common intersection, our last line would have to intersect all others once.

If at any point before the last line (let's say, at the rth line, where 1 < r < n) we decide not to share the initial intersection with previous lines, our first deviant line would have to intersect with all other lines once at separate points, adding r-1 intersections to the plane. After this first digression, we know that there is no point on the plane shared by all lines. That is, there is no one point on the plane where lines after the rth line will intersect with all other lines at once. At the very least, therefore, all lines after this will add 1 new intersection to the plane. This is the best case scenario, where we keep adding lines to the intersection shared by the r-1 lines from before (ensuring that each new line intersects with all other lines except for the rth one, which it will have to intersect at a separate point).

Compare the two cases:
(1) where we share the initial intersection until the last line, whereupon the sequence of added intersections will be $1,0,0,...,0,n-1$ .

(2) where we introduce a new intersection anytime before the last line, whereupon the sequence would change to

$\1,\underbrace{0,0,...0}_\text{r-2 times},r-1,1,...,1$

at the very best.

Each sequence constitutes a set of n elements (for our n lines). Thus, in the first sequence, we have a total of 1+n-1 = n distinct intersections. In the second case, at the very least we have 1+r-1+(n-r)(1) = n distinct intersections.

Therefore, the absolute minimum number of distinct intersections throughout our plane is n.

HSC 2015 MX2 Marathon ADVANCED (archive) (4 Viewers)

Member

This too shall pass

Active Member

what is that?It is Cowpea

Member

Member

Active Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Active Member

Well-Known Member

Active Member

This too shall pass

Active Member

This too shall pass

Active Member

Member

Users Who Are Viewing This Thread (Users: 0, Guests: 4)