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

InteGrand · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

shervos said:
$\\ $ Consider a cubic polynomial $ P(x)=x^3+bx^2+cx+d $ .Show that $ |x_i| < 1 $ if and only if $ |bd-c| < 1-d^2 $ and $ |b+d| < |1+c| $where$ |x_i|$ is a root of the polynomial$$

I think we need some clarification.

Are $b,c,d$ allowed to be non-real complex numbers? Do you mean $1-d^2$ , or $| 1-d^2|$ ? And is $|x_i|$ the root, or is it $x_i$ ? It is possible to have all roots have modulus less than 1 and have $|bd-c| < 1-d^2$ be unsatisfied, e.g. $P(x) = x^3 - \frac{1}{8}\mathrm{cis}(\theta)$ for some real $\theta$ such that $1-\left( - \frac{1}{8}\mathrm{cis}(\theta) \right)^2$ is not real (clearly such $\theta$ exists). In this case, $|bd-c| < 1-d^2$ does not make sense since $1-d^2$ is not real.

Sy123 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Sy123 said:
(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)

I've tried for too long at this idea and I can't get to a proof of it

New question

$\\ $Suppose that there are some lines in a plane, no pair of which are parallel, and they do not all intersect at a single point. Prove or disprove the conjecture, 'in any arrangement of the lines and for any number of lines, there is always at least one intersection point that has only 2 lines going through it'$$

shervos · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

InteGrand said:
I think we need some clarification.

Are $b,c,d$ allowed to be non-real complex numbers? Do you mean $1-d^2$ , or $| 1-d^2|$ ? And is $|x_i|$ the root, or is it $x_i$ ? It is possible to have all roots have modulus less than 1 and have $|bd-c| < 1-d^2$ be unsatisfied, e.g. $P(x) = x^3 - \frac{1}{8}\mathrm{cis}(\theta)$ for some real $\theta$ such that $1-\left( - \frac{1}{8}\mathrm{cis}(\theta) \right)^2$ is not real (clearly such $\theta$ exists). In this case, $|bd-c| < 1-d^2$ does not make sense since $1-d^2$ is not real.

the coefficients are all real. and sorry, the root is x_i, not |x_i| (I failed my latex here).....

shervos · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Sy123 said:
I've tried for too long at this idea and I can't get to a proof of it

New question

$\\ $Suppose that there are some lines in a plane, no pair of which are parallel, and they do not all intersect at a single point. Prove or disprove the conjecture, "in any arrangement of the lines and for any number of lines, there is always one intersection point that has only 2 lines going through it"$$

which conjecture are you referring to? If you mean the one in which u quoted, I think it has already been proven

Sy123 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

shervos said:
which conjecture are you referring to? If you mean the one in which u quoted, I think it has already been proven

the line wouldn't come up for some reason, edited

dan964 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Sy123 said:
I've tried for too long at this idea and I can't get to a proof of it

New question

$\\ $Suppose that there are some lines in a plane, no pair of which are parallel, and they do not all intersect at a single point. Prove or disprove the conjecture, 'in any arrangement of the lines and for any number of lines, there is always at least one intersection point that has only 2 lines going through it'$$

could use strong mathematical induction? (n>2)

Sy123 · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

dan964 said:
could use strong mathematical induction? (n>2)

I tried that but couldn't find a conclusive proof for it.

The proof is easy if one knows (a latter conjecture that I knew I had to prove but could not) that there cannot exist a line that goes through all intersection points of degree 2 and goes through every other line through an already established intersection point.

RealiseNothing · Jul 18, 2015

Re: HSC 2015 4U Marathon - Advanced Level

YangplaysSongs said:
Obviously, a proof by contradiction seems like the correct approach.

Choose a point in the plane, and label it as A_0. From the questions conditions, namely the fact that not all lines can intersect at a single point implies that there are in fact at least three distinct intersection points. Of all triangles whose vertices are such intersection points, consider those with minimal area; and of all these triangles, consider one whose centroid is farthest from A_0.

Suppose that this triangle has vertices P, Q, and R. Because these points are have three or more lines going through them, they must lie also on the sides of a bigger triangle. This new, larger triangle is separated into four triangles by the lines PQ, QR, and RP — namely, triangle PQR is surrounded by three outer triangles.
One can easily show that the PQR's area is >= the minimum of the areas of the other three triangles,
with equality if and only if triangle PQR is the medial triangle of the larger triangle whose sides P,Q, and R lie on. Indeed, equality must hold because of the minimal definition of triangle PQR. Hence, each of the outer triangles is formed by the given lines and has the same area as triangle PQR; but one of the four triangles have centroids further from A_0 than
the centroid of triangle PQR, a contradiction since we defined PQR to be the triangle whose triangle has minimal distance from A_0.

Your username is really subtle isnt it

glittergal96 · Jul 19, 2015

Re: HSC 2015 4U Marathon - Advanced Level

Sy123 said:
I've tried for too long at this idea and I can't get to a proof of it

New question

$\\ $Suppose that there are some lines in a plane, no pair of which are parallel, and they do not all intersect at a single point. Prove or disprove the conjecture, 'in any arrangement of the lines and for any number of lines, there is always at least one intersection point that has only 2 lines going through it'$$

I already proved this on the previous page, in fact there are at least three such intersection points. Yang's proof above is a much more elegant way of proving existence though, which is all we require for induction.

glittergal96 · Jul 19, 2015

Re: HSC 2015 4U Marathon - Advanced Level

YangplaysSongs said:
I've been reading your posts, and I have this gut feeling that I know you from somewhere....Have you attended any events/programs organised by the AMT such as NMSS or selection camp? Or am I completely wrong?

Nope, not quite good enough for selection camp.

shervos · Jul 19, 2015

Re: HSC 2015 4U Marathon - Advanced Level

shervos said:
$\\ $ Consider a cubic polynomial $ P(x)=x^3+bx^2+cx+d $ .Show that $ |x_i| < 1 $ if and only if $ |bd-c| < 1-d^2 $ and $ |b+d| < |1+c| $where$ x_i$ is a root of the polynomial$$

Now that Sy's question has been resolved, BUMP

dan964 · Jul 19, 2015

Re: HSC 2015 4U Marathon - Advanced Level

shervos said:
Now that Sy's question has been resolved, BUMP

I know the second statement comes from P(1) and P(-1).

shervos · Jul 19, 2015

Re: HSC 2015 4U Marathon - Advanced Level

dan964 said:
I know the second statement comes from P(1) and P(-1).

Uh......no. I think you should stop trying to sound smart/ bullshitting and start to post valid solutions.

InteGrand · Jul 21, 2015

Re: HSC 2015 4U Marathon - Advanced Level

YangplaysSongs said:
$p_{0}(x)=0 \\ p_{1}(x)=x-2013 \\ p_{n}(x)=(x-2013)p_{n}(x)+(2014-x)p_{n-2)(x). \\$ For each positive integer n, find all real solutions of p_{n}.$$

$Is there a typo in the recurrence relation? Should it be $p_n (x)=(x-2013)p_{\textbf{\textit{n-1}}}(x) + (2014 - x)p_{n-2}(x)$ or something? Otherwise the recurrence relation basically just simplifies to $p_n (x) = p_{n-2}(x)$, which I don't think was the intention.$

dan964 · Jul 21, 2015

Re: HSC 2015 4U Marathon - Advanced Level

shervos said:
the coefficients are all real. and sorry, the root is x_i, not |x_i| (I failed my latex here).....

shervos, further clarification. if that is the case is it supposed be just $x_{i} < 1 $ or $ -1 < x_{i}<1$
(I am assuming you only need one root in that range.

InteGrand · Jul 21, 2015

Re: HSC 2015 4U Marathon - Advanced Level

dan964 said:
shervos, further clarification. if that is the case is it supposed be just $x_{i} < 1 $ or $ -1 < x_{i}<1$
(I am assuming you only need one root in that range.

It was that all roots had modulus less than 1 (the roots could be non-real).

dan964 · Jul 21, 2015

Re: HSC 2015 4U Marathon - Advanced Level

thanks for that.

glittergal96 · Jul 23, 2015

Re: HSC 2015 4U Marathon - Advanced Level

For the cubic question:

Let A be the statement that the pair of inequalities in the question hold.

Let B be the statement that the polynomial has all roots in the open unit disk.

Let S(n) be the statement that the polynomial has n real roots.

It suffices to show:

(1.) A & S(1) <=> B & S(1)

and

(2.) A & S(3) <=> B & S(3).

I prove (1.) below. I have not proven (2.) yet, but hopefully it is not much harder. I will post it if/when I get it.
---

If p has roots $\alpha,\beta,\gamma$ ,

A & S(1) <=> S(1) & {all real roots of p lie in unit interval and all real roots of $q(x)=(x-\alpha\beta)(x-\alpha\gamma)(x-\beta\gamma)$ lie in unit interval.}

<=> S(1) & {p(1)>0 & p(-1) < 0 & q(1)>0}

<=> S(1) & {|b+d|<|1+c| & 1-d^2>c-bd.}

So it remains to show that the RHS implies S(1) & {|b+d|<|1+c| & 1-d^2 < bd-c}.

Since we have S(1), we can write the roots as $r,\alpha,\overline{\alpha}$

So $c+1=|\alpha|^2+2r\Re{(\alpha)}+1 > (|\alpha|-1)^2+\Im{(\alpha)}^2 >0$ .

This means that c+1=|c+1|, and we have |b+d|<1+c.

so bd+d^2 = d(b+d) < |b+d| < 1+c which implies that 1-d^2 < bd-c as required. So this completes the proof of (1.).

(If there is anything you would like me to clarify please ask, I am being brief in explanation because to do otherwise would be quite tedious.)

glittergal96 · Jul 23, 2015

Re: HSC 2015 4U Marathon - Advanced Level

(A almost identical argument establishes B & S(3) => A & S(3). p and q must have all roots in the unit interval so we get p(1) > 0, p(-1) < 0, q(1) > 0. Which gives us |b+d| < |1+c| = 1+c and 1-d^2 > c-bd. As with my previous post, the 1-d^2 > bd-c inequality comes from the |b+d| < 1+c one.)

So the problem is now 3/4 done. It remains to show A & S(3) => B & S(3).

InteGrand · Jul 24, 2015

Re: HSC 2015 4U Marathon - Advanced Level

YangplaysSongs said:
$p_{0}(x)=0 \\ p_{1}(x)=x-2013 \\ p_{n}(x)=(x-2013)p_{n-1}(x)+(2014-x)p_{n-2}(x). \\$ For each positive integer n, find all real solutions of polynomial p_{n}.$$

$The answer is that for each positive integer $n$, 2013 is the only real root of $p_n$ (it turns out that 2013 is a double root when $n$ is even, and a simple root when $n$ is odd). It is easy to see this is true for $n=1$.$

$We have for $n\geq 2$, $p_n (x) = (x-2013)p_{n-1}(x) + (2014-x)p_{n-2}(x)$$

$\Rightarrow p_n (x) = (x-2013)p_{n-1}(x) + ((2013-x)+1)p_{n-2}(x)$

$= (x-2013)p_{n-1}(x) + (2013-x)p_{n-2}(x)+p_{n-2}(x)$

$$\Rightarrow p_n (x) = (x-2013)\left( p_{n-1}(x) -p_{n-2}(x)\right)+p_{n-2}(x)$. \ \ (*)$

$Denoting $D_{n-1}=p_{n-1}(x) -p_{n-2}(x)$, we have $D_1 = p_1 (x) -p_0(x)= x-2013 - 0 = x-2013$, and for $n-1\geq 2,$$

$D_{n-1}=(x-2013)p_{n-2}(x) + (2014-x)p_{n-3}(x) - p_{n-2}(x)$

$=(x-2014)p_{n-2}(x) + (2014-x)p_{n-3}(x)$

$=(x-2014)(p_{n-2}(x) -p_{n-3}(x))$

$$\Rightarrow D_{n-1}=(x-2014)D_{n-2}$.$

$It follows that for $n-1\geq 2$, $D_{n-1}=(x-2014)^{n-2}D_1$$

$i.e. $D_{n-1}=(x-2014)^{n-2}\cdot (x-2013)$ (and we can check that this also works for $n-1 = 1\Longleftrightarrow n =2$).$

$So in (*), we have for $n\geq 2$, $p_n (x) = (x-2013)D_{n-1}+p_{n-2}(x)\Rightarrow p_n (x) = (x-2013)\times(x-2014)^{n-2}\cdot (x-2013)+p_{n-2}(x)$$

$$\Rightarrow p_n (x) = (x-2013)^2 (x-2014)^{n-2} + p_{n-2}(x)$ for $n\geq 2$. \ \ (**)$

$For \underline{even $n$}, (**) implies that$

$p_n (x) = (x-2013)^2 (x-2014)^{n-2} + (x-2013)^2 (x-2014)^{n-4}+\cdots + (x-2013)^2 (x-2014)^{2} +(x-2013)^2 (x-2014)^{0} +p_0(x)$

$$\Rightarrow p_n (x) = (x-2013)^2 \left[1+a^2+a^4+\cdots + a^{n-2} \right]$, where $a\equiv x-2014$ (since $p_0 (x)=0$).$

$So for even $n\geq 2$, the only real root is 2013 (which we can see is a double root), since $1+a^2+a^4+\cdots + a^{n-2} \neq 0$ for real $x$ (as it is 1 + the sum of squares of real numbers, hence always greater than or equal to 1).$

$For \underline{odd $n\geq 2$}, (**) implies that$

$p_n (x) = (x-2013)^2 (x-2014)^{n-2} + (x-2013)^2 (x-2014)^{n-4}+\cdots + (x-2013)^2 (x-2014)^{1} +p_1 (x)$

$= (x-2013)^2 (x-2014)^{n-2} + (x-2013)^2 (x-2014)^{n-4}+\cdots + (x-2013)^2 (x-2014) +(x-2013)$

$$\Rightarrow p_n (x)= (x-2013)\left[1+(x-2013)(x-2014)+(x-2013)(x-2014)^3 + \cdots + (x-2013)(x-2014)^{n-2} \right]$.$

$Clearly $2013$ is a root, and it now suffices to show that the following equation ($\star$) has no real roots:$

$1+(x-2013)(x-2014)+(x-2013)(x-2014)^3 + \cdots + (x-2013)(x-2014)^{n-2} =0\Longleftrightarrow (x-2013)\cdot \left(\underbrace{(x-2014) + (x-2014)^3 + \cdots + (x-2014)^{n-2}}_{S} \right)=-1, x\in \mathbb{R}:x\neq 2013$ $(\star)$

$Clearly for $x\geq 2014$, since the sum $S$ is non-negative, and $x-2013 > 0$, $(\star)$ does not hold as the L.H.S. is non-negative. Also, for $x<2013$, $S<0$ (being the sum of negative terms) and $x-2013<0$, so the L.H.S. is positive and $(\star)$ does not hold (clearly 2013 would not satisfy the equation). So consider $2013<x<2014$. Using $a\equiv x-2014$, this means that $-1<a<0$, and the L.H.S. of ($\star$) can be rewritten as:$

$LHS = (a+1)(a+a^3 + a^5 + \cdots + a^{n-2})$

$$=(a+1)\times \frac{a\left(\left( a^2\right) ^{\frac{n-1}{2}} - 1 \right)}{\underbrace{a^2-1}_{(a+1)(a-1)}}$ (GP sum formula)$

$$=\frac{a}{a-1}\left(a^{n-1}-1 \right)$,$

$so we can rewrite $(\star)$ (for $2013<x<2014$) as$

$$\frac{a}{a-1}\left(a^{n-1}-1 \right)=-1,$ where $-1<a<0$.$

$Clearly there are no solutions, because $0<\frac{a}{a-1}<\frac{1}{2}$ (this is easy to prove, e.g. by using calculus) and $-1<a^{n-1}-1<0$ (as $n-1$ is even; also easily proved, as $-1<a<0\Rightarrow 0<a^{n-1}<1\Rightarrow -1<a^{n-1}-1<0$), so $|LHS|=\left | \frac{a}{a-1}\left(a^{n-1}-1 \right) \right |=\left | \frac{a}{a-1} \right |\left |a^{n-1}-1 \right |<\frac{1}{2}\times 1<1=|RHS|$. This completes the proof. $\blacksquare$$

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

Well-Known Member

This too shall pass

Member

Member

This too shall pass

what

This too shall pass

what is that?It is Cowpea

Active Member

Active Member

Member

what

Member

Well-Known Member

what

Well-Known Member

what

Active Member

Active Member

Well-Known Member

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