HSC 2014 MX2 Marathon ADVANCED (archive) (1 Viewer)

dan964 · Sep 14, 2014

Re: HSC 2014 4U Marathon - Advanced Level

q14 and 16 are both out of 16 not 15

Sy123 · Sep 14, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Here is a good question:

$\\ $Let$ \ f(n) \ $be the average of all positive divisors of positive integer$ \ n \\ \\ $Show that$ \ f(n) \geq \sqrt{n}$

RealiseNothing · Sep 14, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Sy123 said:
Here is a good question:

$\\ $Let$ \ f(n) \ $be the average of all positive divisors of positive integer$ \ n \\ \\ $Show that$ \ f(n) \geq \sqrt{n}$

$\tau{(n)}$ is the number of positive divisors of $n$ , and note that these divisors must occur in pairs $n=de$ and thus $\tau{(n)}$ is even.

Define the divisors to be $a_1,~a_2,...,~a_{\tau{(n)}}$

$n = de = a_ka_{k+1}$

$a_k+a_{k+1} \geq 2\sqrt{a_ka_{k+1}} = 2\sqrt{n}$

$\sum_{k=1}^{\tau{(n)}} a_k+a_{k+1} \geq \tau{(n)}\sqrt{n}$

$f(n) \geq \sqrt{n}$

dan964 · Sep 15, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Axio said:
Is this the solution for 14ai?

$LHS=z^{n}-z^{-n}\\=(cos\theta +isin\theta )^{n}-\frac{1}{(cos\theta +isin\theta)^{n}}\\=(\frac{cos^{2}\theta +2icos\theta sin\theta -sin^{2}\theta -1}{cos\theta +isin\theta })^{n}\\=(\frac{2icos\theta sin\theta -2sin^{2}\theta }{cos\theta +isin\theta })^{n}\\=(\frac{2isin\theta (cos\theta +isin\theta )}{cos\theta +isin\theta })^{n}\\=2isinn\theta$ =RHS

yep although there is an easier way of doing it using demouivre's theorem.

dan964 · Sep 15, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Errata in q16, last part is R^2 not R

Sy123 · Sep 15, 2014

Re: HSC 2014 4U Marathon - Advanced Level

RealiseNothing said:
$\tau{(n)}$ is the number of positive divisors of $n$ , and note that these divisors must occur in pairs $n=de$ and thus $\tau{(n)}$ is even.

Define the divisors to be $a_1,~a_2,...,~a_{\tau{(n)}}$

$n = de = a_ka_{k+1}$

$a_k+a_{k+1} \geq 2\sqrt{a_ka_{k+1}} = 2\sqrt{n}$

$\sum_{k=1}^{\tau{(n)}} a_k+a_{k+1} \geq \tau{(n)}\sqrt{n}$

$f(n) \geq \sqrt{n}$

Nice proof!
Here is mine:

$\\ $Consider the prime factorisation of$ \ n \ $so let$ \ n = p_1 p_2 \dots p_m \ $where$ m \ $is the number of prime factors including duplicates$ \\ \\ $The sum of divisors is given by$ \ \binom{m}{0} + \binom{m}{1} + \dots + \binom{m}{m-1} + \binom{m}{m} = 2^m \ $where each term represents a certain number of prime factors taken together as a product, i.e.$ \ \binom{m}{k} \ $is the sum of all divisors of$ \ n \ $that involve$ \ k \ $prime factors of$ \ n \\ \\ $Let$ \ \delta(k) \ $be the sum of prime factors, taken$ \ k \ $at a time, so$ \ \delta(2) = p_1p_2 + p_1 p_3 + \dots \ $and$ \ \delta(1) = p_1 + p_2 + \dots + p_m \\ \\ $Sosum of all positive divisors of$ \ n \ $is given by$ \ \sum_{k=1}^{m} \delta(k)$

$\\ $Consider the polynomial$ \ P(x) = \prod_{k=1}^m (x-p_k) \\ \\ $It is clear that$ \ \frac{P(-1)}{(-1)^m} = \sum_{k=1}^m \delta (k) \ $by expanding the polynomial$ \\ \\ \therefore \sum_{k=1}^m \delta(k) = \prod_{k=1}^m (1+p_k)$

$\\ $Thus$ \ f(n) = \frac{\prod_{k=1}^m (1+p_1)}{2^m} \ , \ n = \prod_{k=1}^m p_k$

$\\ $Thus it must be proven that$ \\ \\ \prod_{k=1}^m \frac{1+p_k}{2} \geq \prod_{k=1}^m \sqrt{p_k}$

$\\ $It is true that$ \ \frac{1+p_k}{2} \geq \sqrt{p_k} \ $by AM-GM, thus taking the product from$ \ k=1 \ $to$ \ m \ $keeps the inequality, completing the proof$$

RealiseNothing · Sep 15, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Sy123 said:
Nice proof!
Here is mine:

$\\ $Consider the prime factorisation of$ \ n \ $so let$ \ n = p_1 p_2 \dots p_m \ $where$ m \ $is the number of prime factors including duplicates$ \\ \\ $The sum of divisors is given by$ \ \binom{m}{0} + \binom{m}{1} + \dots + \binom{m}{m-1} + \binom{m}{m} = 2^m \ $where each term represents a certain number of prime factors taken together as a product, i.e.$ \ \binom{m}{k} \ $is the sum of all divisors of$ \ n \ $that involve$ \ k \ $prime factors of$ \ n \\ \\ $Let$ \ \delta(k) \ $be the sum of prime factors, taken$ \ k \ $at a time, so$ \ \delta(2) = p_1p_2 + p_1 p_3 + \dots \ $and$ \ \delta(1) = p_1 + p_2 + \dots + p_m \\ \\ $Sosum of all positive divisors of$ \ n \ $is given by$ \ \sum_{k=1}^{m} \delta(k)$

$\\ $Consider the polynomial$ \ P(x) = \prod_{k=1}^m (x-p_k) \\ \\ $It is clear that$ \ \frac{P(-1)}{(-1)^m} = \sum_{k=1}^m \delta (k) \ $by expanding the polynomial$ \\ \\ \therefore \sum_{k=1}^m \delta(k) = \prod_{k=1}^m (1+p_k)$

$\\ $Thus$ \ f(n) = \frac{\prod_{k=1}^m (1+p_1)}{2^m} \ , \ n = \prod_{k=1}^m p_k$

$\\ $Thus it must be proven that$ \\ \\ \prod_{k=1}^m \frac{1+p_k}{2} \geq \prod_{k=1}^m \sqrt{p_k}$

$\\ $It is true that$ \ \frac{1+p_k}{2} \geq \sqrt{p_k} \ $by AM-GM, thus taking the product from$ \ k=1 \ $to$ \ m \ $keeps the inequality, completing the proof$$

I think this is only valid if all m prime factors are distinct.

Sy123 · Sep 15, 2014

Re: HSC 2014 4U Marathon - Advanced Level

RealiseNothing said:
I think this is only valid if all m prime factors are distinct.

Yea it is, my bad

glittergal96 · Sep 16, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Realisenothing, were you able to find a closed form for that sum in the end? I am still a bit doubtful that one exists.

Thanks for posting so many questions Dan, will try some this afternoon.

glittergal96 · Sep 16, 2014

Re: HSC 2014 4U Marathon - Advanced Level

By the way, I think the "only if" statement in 15bii) is not true. Counterexample: p=561.

dan964 · Sep 16, 2014

Re: HSC 2014 4U Marathon - Advanced Level

glittergal96 said:
By the way, I think the "only if" statement in 15bii) is not true. Counterexample: p=561.

read the question "absolutely every n" is the key phrase. Sure it may work for non-prime p for certain n, but for all.
If you think I am bluffing, Q15b is a reworking of Fermat's theorem.

2047 is another. Have you tried with base 3 (n=3), or base 5 (n=5) as well.
part (iii) proves that for n=2, some numbers other than primes work e.g. 2047

the proof to Q15(b)(ii) comes from part (i) which is an interesting property of Pascal's triangle that can be proved quite easily.

Errata Q14 (A)(ii) use part (i)

One other interesting thing about Primes (p>5), and testing for them. (a quick way)
1. You can test all numbers up to the squareroot
2. Check whether divisible by 2,3 and 5.
3. You can easily check whether the last digit is a 2,4,5,6,8 or 0
4. You can also only divide by numbers that are of the form 6m +1 or 6m - 1 (since all primes occur either side of these numbers), so that removes all multiples of 3 as well.

here is an interesting extension (for if p/n is not an integer) for all prime numbers if I write (p-1) 1s (then a zero) in that base it is also divisible. (Provided n/= p). Hence 1,111,110 (and therefore 111,111) is divisible by 7, and 111,111,111,1110 and therefore (111,111,111,111) is divisible by 13.

glittergal96 · Sep 16, 2014

Re: HSC 2014 4U Marathon - Advanced Level

dan964 said:
read the question "absolutely every n" is the key phrase. Sure it may work for non-prime p for certain n, but for all.
If you think I am bluffing, Q15b is a reworking of Fermat's theorem.

2047 is another. Have you tried with base 3 (n=3), or base 5 (n=5) as well.
part (iii) proves that for n=2, some numbers other than primes work e.g. 2047

the proof to Q15(b)(ii) comes from part (i) which is an interesting property of Pascal's triangle that can be proved quite easily.

Errata Q14 (A)(ii) use part (i)

One other interesting thing about Primes (p>5), and testing for them. (a quick way)
1. You can test all numbers up to the squareroot
2. Check whether divisible by 2,3 and 5.
3. You can easily check whether the last digit is a 2,4,5,6,8 or 0
4. You can also only divide by numbers that are of the form 6m +1 or 6m - 1 (since all primes occur either side of these numbers), so that removes all multiples of 3 as well.

here is an interesting extension (for if p/n is not an integer) for all prime numbers if I write (p-1) 1s (then a zero) in that base it is also divisible. (Provided n/= p). Hence 1,111,110 (and therefore 111,111) is divisible by 7, and 111,111,111,1110 and therefore (111,111,111,111) is divisible by 13.

I did read the question.

I claim that for every n, p=561 satisfies the statement "n^p-n is divisible by p" despite 561 not being prime. If you think there is an n such that this is not true can you please supply it?

I don't think you are "bluffing", I just don't believe the statement you made is true. Also, Fermat's little theorem is equivalent to the "if" statement, not the "only if".

Part i) is true because the prime factorisation of the denominator of p!/k!(p-k)! does not contain any copies of p toe cancel out the numerator's. So each pCk is divisible by p for k=1,2,...,p-1. It is easy to use this result to prove the "if" statement in ii) inductively, but I still don't believe the "only if".

dan964 · Sep 16, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Prove by induction for n rather than p is a bit easier.

glittergal96 · Sep 16, 2014

Re: HSC 2014 4U Marathon - Advanced Level

dan964 said:
Use a similar method to Q15(b) with n = 3 but this time prove by contradiction it doesn't work.
Done

What is this post in reply to? I still think n^561-n is divisible by 561 for every positive integer n, despite 561 not being prime. This is in contradiction with the "only if" part of your question. (By the way, I got this number because it is the lowest Carmichael number, and I checked the non-coprime moduli myself.)

dan964 said:
Prove by induction for n rather than p is a bit easier.

I never said induction in p, that would be insane/impossible because p goes over the primes. I meant induction in n, which is straightforward because

$(n+1)^p-(n+1)=(n^p-n)+ \sum_{k=1}^{p-1}\binom{p}{k}n^k.$

The first RHS term is divisible by p because of the inductive assumption, and each binomial coefficient in the second is divisible by p for the reason I described in my previous post. So the whole thing is divisible by p.

RealiseNothing · Sep 16, 2014

Re: HSC 2014 4U Marathon - Advanced Level

dan964 said:
read the question "absolutely every n" is the key phrase. Sure it may work for non-prime p for certain n, but for all.
If you think I am bluffing, Q15b is a reworking of Fermat's theorem.

FLT is not IFF, glittergal is right.

dan964 · Sep 17, 2014

Re: HSC 2014 4U Marathon - Advanced Level

fine then a small edit:

Restriction: Provided that (6m+1), (12m+1), (18m+1) are not prime factors; if p is composite.
i.e. Carmichael numbers.
**The point of the question is the "only if" to see if you can

If you divide both sides in Q15b by the 'n' then the expression no longer works for Carmichael Numbers or when p=n.
Which is probably the edit I am going to make.

glittergal96 · Sep 17, 2014

Re: HSC 2014 4U Marathon - Advanced Level

dan964 said:
fine then a small edit:

Restriction: Provided that (6m+1), (12m+1), (18m+1) are not prime factors; if p is composite.

Wait, so what is the full question then? I don't see how this fits in anywhere that makes sense.

wiliaamnguuyen · Sep 19, 2014

Re: HSC 2014 4U Marathon - Advanced Level

http://community.boredofstudies.org...1d1411026981-complex-numbers-help-photo-1.jpg

wiliaamnguuyen · Sep 19, 2014

Re: HSC 2014 4U Marathon - Advanced Level

Anyone wanna solve?

RealiseNothing · Sep 19, 2014

Re: HSC 2014 4U Marathon - Advanced Level

wiliaamnguuyen said:
http://community.boredofstudies.org...1d1411026981-complex-numbers-help-photo-1.jpg

Advanced

HSC 2014 MX2 Marathon ADVANCED (archive) (1 Viewer)

what

This too shall pass

what is that?It is Cowpea

what

what

This too shall pass

what is that?It is Cowpea

This too shall pass

Active Member

Active Member

what

Active Member

what

Active Member

what is that?It is Cowpea

what

Active Member

Member

Member

what is that?It is Cowpea

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