Australian Mathematical Olympiad 2018 Question 5

[@tracyh5751]

It's good to know the Astraulian olympiad is still going strong in the year 20,018. :p

[@shibuthomas2745]

Lmao I also noticed that

[@NStripleseven]

Yeah

[@LarryT88]

Australian you meant?

[@seanfraser3125]

Before watching the video: I was able to derive a closed form for n >= 2 a(n) = [n*n!]/2 = [n^2 * (n-1)!] / 2 which you can prove by induction. I derived it by first deriving a 1-step recursive formula, and from there just multiplying iteratively until things cancelled. From there it’s clear that n^2 divides a(n) for n > 2. Edit after watching: Looks like you derived the 1-step recurrence the same way I did, I just took it a step further by finding a closed form. But it was pretty clever how you used a basic fact from number theory to avoid finding a closed form. Also, looking forward to the use of exponential generating functions!

[@jonggwan25]

I guess this can be done much simpler: If n≥3, a[n] = n*(a[1]+ ... +a[n-1]) = n*{(a[1]+ ... +a[n-2])+(n-1)(a[1]+ ... +(a[n-2])} = n*{n*(a[1]+ ... +a[n-2])}=n^2 * (a[1]+...+a[n-2]). (* Note that every a[k]'s are integers, which can be easily shown with inductive logic.) Therefore, n^2 divides a[n] for any n greater than or equal to 3.

[@АбдаллахМуслим]

Jonggwan Lee the problem was too easy to make a video about it

[@jimschneider799]

A couple years late, but... I used the one step recurrence to postulate a closed form for a[n], and proved it by induction, showing that not only does n^2 divide a[n], for n > 2, but that a[1009] is the first a[n] that is divisible by 2018^2.

[@owenjordan5535]

You can also prove it without needing the lemma, by induction : suppose (n-1)^2 divides a_(n-1), then by the recursion relation it's easy to see that n^2 will divide a_n.

[@timurpryadilin8830]

assume n^2|a_n. Then a_(n+1) = (n+1)^2 *(a_n/n), the second multiple is an integer by our induction hypothesis, so (n)^2|a_(n) starting from n = 3

[@050138]

Nice problem! Let the nth term be denoted by a[n]. We have a[n + 1] = (n + 1)*( a[1] + a[2] + .... + a[n]) and a[n] = (n)*( a[1] + a[2] + .... + a[n - 1]) Multiplying first equation by 'n', and second equation by 'n + 1' and subtracting them yields n*a[n + 1] - (n + 1)*a[n] = n*(n + 1)*a[n] Or, n*a[n + 1] = (n + 1)^2*a[n], Or, a[n + 1] / a[n] = ((n + 1)^2) / n Using the above, we have.... a[2018] / a[2017] = (2018^2) / 2017 a[2017] / a[2016] = (2017^2) / 2016 ..... a[3] / a[2] = (3^2) / 2 This is only valid till the pair a[3] and a[2] or till n is 2, as when n is 1, there is no meaning for term a[n - 1] So a[2] / a[1] is simply 2 Multiplying all the equations yields a[2018] / a[1] = (2018^2)*2017*2016*2015*....*4*3 Hence (2018^2) divides a[2018] Edit: By this method, it is also easy to see that as a[n] / a[1] = (n^2)/(n - 1)*((n - 1)^2)/(n - 2)*....*(4^2)/3*(3^2)/2*2/1 the closed form of a[n] is, a[n] = (n^2)*(n - 1)*(n - 2)*....*4*3, or a[n] = (n/2)*(n!) for all n > 1

[@050138]

@Adam Romanov Thank you man 😊 I remember you from the comments on the other video....

[@compiling]

Instead of using the gcd lemma, you can use the fact that n divides a(n) by definition to get a(n+1) = (n+1)^2 * a(n)/n, where a(n)/n is an integer.

[@danielparra6902]

Thank you very much for your work! Competitive problems are nice but rare to see on KZbin in such an accesible way. I really love to flex the my math muscle on problems like this. Looking forward for the next video!

[@viratrobbie3259]

Hello professor penn, Great video as always! Using the recursive relation we derived, we can easily find a closed form for an: an = 0.5*n^2*(n-1)!. From here, we can clearly see an/n^2 = 0.5*(n-1)!, which is always an integer for n>2, so we can clearly see that n^2 divides an for n>2 .

[@xation6048]

50% of the comments are about 20018

[@Marcos11182]

I've just counted and actually they are 25%, nice try

[@kalpshah5088]

I actually counted and actually it's only 23.67 %

[@a_llama]

an AMO question from the year 20018 😍

[@amircanto5416]

Damn it, I was expecting to see the close form. You made the problem look very simple and straightforward.

[@MichaelPennMath]

Closed form video coming tomorrow. Warning though: I purposefully find the closed for in a very difficult way in order to show a certain technique.

[@saifalmarri1409]

Closed form is n*n! Divided by 2. For n greater than ore equal to 2.

[@saifalmarri1409]

I found the general form for the relation, a_n = (n * n!)/2, so a_n = (n^2 *(n-1)!)/2 so n^2 divides a_n in the general case.

[@stormixgaming8389]

is the '20' in 20018 to signify that this video was published on may 20th, 2020 right after the channel hit 20,000 subscribers??

[@nickmiller748]

a_n = n * (a_1 + a_2 + ... + a_(n-1)). Expanding on a_(n-1), a_n = n * (a_1 + a_2 + ... + a_(n-2) + (n-1)*(a_1+...+a_(n-2))). Thus, a_n = n^2*(a_1+...+a_(n-2)). Thus, outside of a_2, n^2 divides a_n. Thus, 2018^2 divides a_2018.

[@marcushendriksen8415]

Wait, now KZbin's "recommended" can transmit videos from the future?

[@biswarupsaha2495]

Great solution ,sir can I try to establish generating function of this recurrence relation because as per this solution we learn to form generating function

[@liberalaccidental]

Wouldn’t it be simpler to observe that an = (n^2) * (a1+a2+...+an-1) and since all the an’s are integers then n^2 necessarily divides an ?

[@joshyman221]

liberalaccidental yeah I’m thinking this. The problem looks so easy though (although the sum in your comment should be up to a_n-2 not a_n-1

[@federixiron345]

I think that you could also prove by induction that a_n = n!.n/2

[@subhendupradhan4636]

n^2 divides a_n for all n>=1 except n=2.

[@MathPapers]

Any recommendations on algebra books for the imo?

[@michaelempeigne3519]

I have seen that you did a video with a 3-piece piecewise function and made it into an explicit function , but how would you do it with four pieces such as : For example, consider the function of period 12 defined by the following equations in the interval - 6 < or = x < or = 6. F ( x ) = 0, - 6 < or = x < or = - 3 F ( x ) = x + 3, - 3 < x < or = 0 F ( x ) = 3 - x, 0 < x < or = 3 F ( x ) = 0, 3 < x < or = 6

[@zacharyjoseph5522]

Why does this not work for a2=2?

[@malawigw]

If gcd(b,n) = 1 it means that b and n have no common prime factors. In particular, n is not a prime factor of b. Now if n | ab, we have that ab = nq for some integer q. But because n is not a prime factor of b, we must have that n is a prime factor in a, thus n|a. No need of Bezout here I think.

[@shacharh5470]

Your solution is very convoluted. Here's a simpler one: a_n = n*sum(a_k) from k=1 to k=n-1 we want to show that n^2 divides a_n It's sufficient to show that n divides sum(a_k) from k=1 to k=n-1 this can be proven with induction. for n=1: 1 divides 1. now assume it holds for n-1 and prove for n: by assumption for some integer m we can denote sum(a_k) from k=1 to k=n-2 = m * (n-1) now the sum from k=1 to k=n-1 = m(n-1) + a_n-1 = m(n-1) + (n-1) * sum(a_k) from k=1 to k=n-2 = m(n-1) + (n-1) * m(n-1) = m(n-1) * [1 + (n-1)] = m(n-1) * n so it's divisible by n, q.e.d.

[@sabyasachinayak24]

a[n]/n = a[n-1]+a[n-2]+..+a[1] a[n-1]/(n-1) = a[n-2]+a[n-3]+..+a[1] Subtracting the latter from the former: a[n]/n - a[n-1]/(n-1) = a[n-1] Or a[n]/n = a[n-1]×(1+1/(n-1)) = a[n-1]×n/(n-1) Or a[n]/n² = a[n-1]/(n-1) = a[n-2]+a[n-3]+..+a[1] = integer. So a[n] is always divisible by n²

[@sabyasachinayak24]

Also, all a[k] are integers, since a[1] is an integer and subsequent ones are derived by repeated additions and multiplications only.

[@allanlago1]

Finding the closed form is overkill but oh well. a_n = n * sum(k=1, k=n-1, a_k) => sum(k=1, k=n-1, a_k) = a_n / n For n >2, a_n = sum(k=1, k=n-2, a_k) + a_(n-1) => a_n = a_(n-1)/(n-1) + a_(n-1) a_n = a_(n-1) * (1+1/(n-1)) => a_n = a_(n-1) * (n^2 / (n-1)) Extending that, a_n = a_2 * (3^2 /2) * (4^2 /3) * ... * (n^2 /(n-1)) From the original equation we find that a_2 = 2*1 = 2. a_n = 2* (3^2 /2 ) * (4^2 /3) *... * (n^2 /(n-1)) = 3*4*5*...*(n-1)*n *n a_n = n!/2 * n, for all n>1 For n=2018, a_2018=2018!/2 * 2018 = 2018^2 * 2017!/2. Clearly divisible by 2018^2.

[@zehaannaik6918]

Great explanation

[@Celicaw8]

6:06 How did we get (n+1)^2 a(n) ?

[@michaelcampbell6922]

(n+1)an +n(n+1)an =(n+1)(n+1)an =[(n+1)^2]an

[@1llum1nate]

Weird question, but where am i wrong in my proof? 1. a_n = a_(n-1) * n^2/(n-1). This is easy to prove. Since a_(n-1) = (n-1)(a_1 + ... + a_(n-2)) we get a_1 + ... + a_(n-2) = a_(n-1)/(n-1) Therefore a_n = n * (a_1 + ... + a_(n-2) + a_(n-1)) = n * (a_(n-1)/(n-1) + a_(n-1)) = n^2/(n-1) * a_(n-1). So we got a_n = n^2/(n-1) * a_(n-1). 2. Now, a_i are clearly natural numbers. Therefore, a_1 + ... +a_2016 is natural. a_2017 = 2017 (a_1+...+a_2016) is therefore divisible by 2017. And since a_2018 = 2018^2 * (a_2017 / 2017) and a_2017 is divisible by 2017, a_2018 is divisible by 2018^2.

[@sayanjitb]

How do you conclude that those are going to be natural number?

[@1llum1nate]

@@sayanjitb How do i conclude they are natural? You can technically prove that by induction but i believe that "obviously, they are natural" would be enough in any olymiad environment. a_1 is natural. Suppose a_1, ..., a_(n-1) is natural. a_n=n(a_1+...+a(n-1)) is a sum of natural numbers multiplied by n and is therefore natural.

[@050138]

Your solution is absolutely correct.... But you can present it better in a clearer way Since you proved a_n / a_n-1 = n^2/(n-1) Extending this idea, a_2018 / a_2017 = 2018^2/2017 a_2017 / a_2016 = 2017^2/2016 ..... a_3 / a_2 = 3^2/2 and a_2 / a_1 = 2, Multiplying all, you get a_2018 / a_1 = 2018^2*K (K some natural number), or a_2018 divisible by 2018^2

[@allanlago1]

Yep. Also, though not relevant to this problem, it is worth noting that the formula a_n = n^2/(n-1) * a_(n-1) only works for n>2 since your derivation relied on you being able to say a_1+...+a_(n-2) = a_(n-1)/(n-1) (aka isolating anything less than or equal to a_(n-2)) which is not defined for n

[@050138]

@@allanlago1 True, it is only for n > 2 that problem statement works.... The closed form n*n!/2 works for n > 1 onwards though....

[@alcachofamp3]

Maybe it's easier if you define s_n=a_1+a_2+...+a_n Then s_n=(n+1)!/2 and a_n=n!*n/2 so it's trivial

[@1llum1nate]

How do you prove s_n=(n+1)!/2 easily? Ive found a way but its not exactly easier than the alternative solution. Maybe im missing smth though.

[@warmpianist]

The formula of a_n fails for n=1. How do you derive from the given recursive function?

[@thejusdeau]

@@1llum1nate If s[n]=(n+1)!/2, s[n+1] = s[n]+a[n+1]= s[n]+(n+1)*s[n]=(n+2)*s[n]=(n+2)*n!/2 (by recursion) and so s[n+1]=(n+2)!/2. And since a[1]=1 and a[2]=2 so s[2]=3=6/2=(2+1)!/2 you have your proof.

[@050138]

@@warmpianist It is true for all n > 1 a_1 is simply 1.... For proof, see my solution in the comments!

[@lambdcalculus]

@@1llum1nate You can prove it by induction. Base case: s_1 = 1 = (1 + 1)!/2. Now, assume s_n = (n + 1)!/2 is true for some n, we will show s_[n+1] = ((n+1) + 1)!/2 to be true as well. s_[n+1] = s_n + a_[n+1] = s_n + (n + 1)*s_n = s_n(n + 1 + 1) = (n + 1)!(n+2)/2 = (n + 2)!/2 = ((n+1) + 1)!/2

[@050138]

Actually, it would have been a better question if they asked to show that a[2018] is divisible by (2018^3)

[@АбдаллахМуслим]

I didn't get the joke... isn't it too easy for a math Olympaid??????... if even they added that into the list of problems at their Olympiad, why you are showing it to us???

[@biswarupsaha2495]

Sir make video on combinatorics

[@tonygrace2735]

Where can i get those problems with the solutions?

[@saifalmarri1409]

What I found was that a_n = [(n^2)/(n-1)]*(a_n-1), so clearly 2018^2 divides a_2018.

[@xwtek3505]

Is this supposed to be an olympiad question?

[@asafcohen8991]

Couldn't we just plug in a_n in a_n+1 and take out n+1 out of the brackets?

[@lemousquetaire]

Just replace a(n) by his formula on a (n+1) you will obtain the same result with no need To proove gcd direct result

[@MichaelPennMath]

For sure, but my goal is not a quick solution but providing a solution along with some helpful tools and proofs of basic facts.

[@lemousquetaire]

@@MichaelPennMath for sure we always learn something Thanks a lot for all

[@ramk4004]

Great explanation. thank you.

[@txikitofandango]

I did it by writing a_n in terms of n only, which is (1/2)n*n!, and then it's obvious why 2018^2 divides (1/2)(2018)(2018!)

[@txikitofandango]

The thing is, I lack the formal rigor to explain how I got that formula. It's pretty clear though when you write out the first few terms

[@txikitofandango]

I'm glad I watched the video anyway because obviously there's a lot more going on than my silly inductions

[@saifalmarri1409]

@@txikitofandango you could do a simple proof by induction, the way you got the conjecture isn’t that important so long as you can prove it works.

[@050138]

actually 2018^3 divides a[2018]

[@kimmovillacorta7677]

I didn't get why bx+ny,=1

[@VincentiusErvinSantoso]

Diophantine Equation.

[@wesleydeng71]

for n>2 because an-1=(n-1)(a1+...+an-2), you have an = n*n*(a1+...+an-2). This problem is just too easy :)

[@НиколайШерстюк-ы7е]

0:16 n starts at "0"

[@davoodkarimi8634]

videos 10 and 11 on this list are copies

[@sharathpr42]

An = n². (n - 1)!

[@marios1962]

it can be solved much easier. let S(n) be the sum of the a(i) from1 to n. a(n)=n * S(n-1) = n * ( a(n-1) + S(n-2)) = n * ( (n-1)S(n-2) + S(n-2)) = n * n * S(n-2). so n*n divides a(n) continue with this you get a(n) = n*n*(n-1)S(n-3)=n*n*(n-1)(n-2)*S(n-4) = .... (finally) n* n * (n-1)(n-2)(n-3)...5*4*3 = n*n*(n-1)! / 2 = n * n! / 2 btw so we also proved that S(n) = (n+1)! / 2

[@anononymousarora9929]

00:00 - 00:12 video was blur Great video though !

[@spazbog123]

All I got from that was nay. At least i got almost 18 millennia to study it.

[@jhonchristianrozano4915]

year 20018 is so good

[@Davidamp]

Anyone else watching in 20020?

[@jha4197]

a_n = n*n!/2

[@muhammadumaribrahim7484]

PLEASE GIVE INDONESIAN SUBTITEL😭, i am indonesian

[@armanrasouli2779]

first