A classic problem from the 1982 Soviet Mathematical Olympiad

[@michel_dutch]

In Soviet Russia, expression takes logarithm of you

[@DatBoi_TheGudBIAS]

@Simon Hayes hey, dunno if u a bot or ure just copying a bot to troll, but anyways, shut up, u were right, no one cares

[@DatBoi_TheGudBIAS]

@Dwayne Luka and u other bot or troll shut up too

[@problemsolver3254]

@@DatBoi_TheGudBIAS it’s just a funny slitly dumb comment

[@andy-kg5fb]

2 of the replies shot themselves in the back of the head 25 times and jumped down a cliff

[@arpitdas4263]

This is the first ever Olympiad problem I've seen that requires such a rigorous use of Calculus. Great stuff

[@leonardocosta3024]

Calculus certainly helped motivate the solution but you don't actually need to do calculus to find this solution. The video's solution only consists on double-counting points such that xln y ≤ ln n. Tbh, I agree, it's a really nice solution.

[@Manuel-pd9kf]

@@leonardocosta3024 could you use an induction proof? That was my first instinct

[@drpkmath12345]

Leonardo Costa I agree with you~ Thats what I was supposed to say~

[@mahdipourahmad3995]

That means you haven't seen many.

[@luckabuse]

In Soviet Union we didn't have Calculus. We called it Mathematical Analysis and it starts in 9th grade(out of 11). So most of the math problems require the knowledge of "Calculus".

[@mstarsup]

there's a "-1" missing in the integral for the computation of the area A with the first version of the computation. The area should stop at 1 on the vertical axis, not at 0. It doesn't change much about the intuition part though.

[@peterdecupis8296]

You are right: the correct integrand is (n^(1/x)-1); anyhow this would affect only the area under the continuous curve, but not the number of the integral point with y >=1 that has to be computed in order to verify the equality of the two discrete summations

[@nicholasleclerc1583]

@Peter De Cupis And another mistake, my good sir, haha : It’s *INTEGER points, not “integral” points

[@RobsMiscellania]

One of my most loved books is a now decades-old copy of The USSR Olympiad Problem Book: Selected Problems and Theorems of Elementary Mathematics. I have come to peace with the fact that I may never solve all of the book's 320 very difficult but rewarding problems. To me, it was an enigma, all problems my 15 year old mind could comprehend but could scarcely approach only the lowest hanging fruit. Decades later, it is clear to me that this book is part of those responsible for setting alight my passion for exploratory mathematics, and doing math for its own sake, as a means of exploring the creative and analytical methods behind the concepts.

[@moonlightcocktail]

* One of OUR most loved books

[@shambosaha9727]

@@moonlightcocktail Yes comrade

[@dickson3725]

Thankyou I had read that book but skipped floor part :v

[@edmundwoolliams1240]

We’re you born in the USSR?

[@justinnitoi3227]

I have that exact same book and am 15 right now!

[@lt97235]

another great solution is to consider A = { x, y integers such that , x>1, y >0 and x^y< or = n} and count it in two ways

[@yueyangzhang6219]

Thank you for putting such great education material on board. I am thrilled to watch.

[@taopaille-paille4992]

Man thank you for all these videos. You have amazing presentation skills and great maths skills. Your channel is an extremely useful source for doing great maths

[@willyh.r.1216]

As a math teacher, I'm very impressed with your ability to solve strange math problems. Can you share with us your method? Thank you.

[@newkid9807]

Q- Existence ur subbed to ayn rand institute u wouldn’t understand anything he shares

[@Djorgal]

I'd say looking up the solution on the internet. This is a great way to solve many maths problems.

[@8ball437]

@@Djorgal You are not wrong though, reading and understanding solutions and asking yourself "why is it true?" is i think a good way to learn and explore mathematics.

[@moonlightcocktail]

@@Djorgal Ah, I see you're a *college* *student* as well.

[@Djorgal]

@@moonlightcocktail Nope, I'm a teacher :)

[@bhoenix3213]

This is interesting because it seems to also prove the same thing for: floor(f(1)) + floor(f(2)) + ... + floor(f(n)) = floor(f^-1(1)) + floor(f^-1(2)) + ... + floor(f^-1(n)) Where f is an invertible positive function (where 1

[@bhoenix3213]

@@Idaniv You right. I'm real rusty lmao

[@nahidhkurdi6740]

That is essentially (without the details) the idea that struck me two minutes after I finished this vedio. The interesting part may be to investigate further through concrete trials to see what interesting formulae could be derived.

[@tylerantony7399]

Yep. You could call it something like the "Integer Lattice Counting Theorem" since that is what is basically being done.

[@MK-13337]

There is an easier way to prove a more general statement. _For any set of points in R^2 a reflection through the line y=x conserves the number of integer points_ A quick proof: Let (n, m) be an integer point (meaning n and m are integers) in set S. After the reflection this point will be the point (m, n), which will be in the set S' (the reflected set) by definition. Now you need to prove that you don't lose or gain any integers, but that should be easy enough remembering that this reflection is multiplying the vector (x, y) by the matrix [0 1; 1 0]. So what would it mean for (x, y) to be a non integer point and (y, x) to be an integer point(?) (left as an excercise) This proves this point counting for any set in R^2. Notice that talking the inverse of a function is a reflection through x=y. There is a more complicated proof for any set in R^n reflected through any (n-1) dimensional hyperplane. Notice also that rotations and translations wont preserve integer points. For example if you do x->x+0.1 you might lose or gain a ton of integer points.

[@chronyx685]

@@MK-13337 your last line, those properties sound like something an eigenfunction would satisfy

[@senco445]

Such an interesting solution, thank you for this!

[@dominikstepien2000]

I see no point in doing these integrals, just counting the points does the job. Very hard problem and interesting solution nevertheless.

[@MichaelPennMath]

You don't "need" the integrals for a solution. My goal was to build intuition for the solution by looking at a continuous version of the problem.

[@ahmadkalaoun3473]

+ i think this equality holds for any fonction f(x) if its inverse f⁻¹(x) exist on [1;n] Don't you think so?

[@vishakp89]

@@MichaelPennMath great intuition building. Thank you

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

Michael Penn don't listen to him... you are right

[@egillandersson1780]

@@MichaelPennMath Yes, you are right ! This comparison between continuous and "discrete integral" is a very good teaching system. It helps to understand the "reasons why"

[@mili3212]

Dude your channel is incredible, please don’t stop making videos.

[@EquuleusPictor]

I'm very surprised by this equation, as it's known that the log increases much slower than the root function, yet when floored and averaged from 2 to n it yields the same result ! That's fantastic really !

[@JM-us3fr]

It's because you're varying the kinds of roots and logarithms you're taking. The fact about logs growing slower than roots is true when you vary the input of the log and the base of the root, rather than the base of the log and the exponent of the root.

[@trueriver1950]

An intuitive way to overcome that surprise is to notice that you are comparing a tall thin shape with a short wide one.

[@mehdisi9194]

Excellent intuitive proof. Thank you so much.

[@peterdecupis8296]

Cool example! And we can easy build a generalized theorem on this method in order to state the equality between the discrete summation of lowerint[f(k)] and the discrete summation of lowerint[inversef[(h)], when f (and its inverse) is a monotonic continuous function, provided that the summation ranges are suitably matched

[@oremilak]

The floor of Log base y of n is the number of digits it takes to write n in base y. The same goes for floor of y th root of n when written in base y. Remember how you do the digit grouping when you find the square or cubic root...

[@oremilak]

It is not obvious you are right. I think we can prove that these sums are actually a sum of the type p+p+p+...+m+m+m+...2+2+2...+1+1+1...and the recurrences of Ps and Ms are equal in each formula is due to the bijection in [N from one function to another.

[@disguisedhell]

There seems something incorrect in the integral 1 to n of (n^1/x)dx. It also calculates the additional area of n-1( the rectangular box) that you missed shading in area

[@aymanenouhail5241]

yep I was also confused about that

[@GregBakker]

I have a Mir book somewhere that touched on lattice point counting, have to see if I can find it. Wonder if the authors knew each other. Fascinating problem and exposition, thanks.

[@pawebielinski4903]

What a great problem. I like it a lot, thank you for your work!

[@C00Cker]

You can easily solve this by expressing each side by two nested for loops of increments of items of an infinite array where each item represents the value of the corresponding side for the respective n.

[@msli4882]

It seems that the area discussion with integration is unnecessary, because the key is the counting of the integer points in two ways, each corresponding to one side of the equation.

[@sahilbaori9052]

This was a question which was quite hard which is x raise to y +y raise to x = 32 where x it smaller then y. Find the possible values for x and y

[@otakurocklee]

Best math channel imo. Great problem!

[@LouisEmery]

I think I knew what the L shaped symbol was, but it was only mentioned at 9:26. Going through the integral of the continuous function was important for visualizing the situation.

[@PaulHobbs23]

Very intuitive solution! With my first look at the problem, it seemed like the problem statement was wrong, because n^1/2 grows so much faster than log_2(n), so to have a very simple and obvious solution to the problem was nice to see.

[@Оеркс]

In 3:30 you said, that integral from 1 to n is equal area, that was hatched previously, which is captured by our graph, x=1, x=n and y=1. But when we integrate, it should be captured by our graph, x=1, x=n and y=0, not with y=1? Maybe I'm missing out something

[@timotheal2871]

This Can actually be resolved using... Counting ! It's actually the number of perfect square

[@MichaelRothwell1]

Brilliant, I love the way you gave a meaning to these numbers. I had to think for a few moments to see how the logs count this too, but of course Michael's diagram helped.

[@MichaelGrantPhD]

I'm not sure I'd add floor(n^1) to the sum when comparing it to the continuous version. After all, a rectangular approximation of that integral with dx=1 would only have n-1 rectangles: (1,2], (2,3], ... (n-1,n]

[@roman_roman_roman]

What was the reason to find explicit forms of integrals and equality btwn them? Is it not enough to find y(x) and x(y) and then count integers?

[@comliword]

I don't understand why to use calculus. If you just count the amount of pairs (a, b) of natural numbers smaller than n so that a^b

[@Massu1004]

Shouldnt we have shown that when verticle counting there are no points to the right in the unshaded area? When I argued through it I think it comes down to log2n < n

[@arnoldbiggins9570]

Good point. The condition is equivalent to showing x

[@vizart2045]

Great using the inverse function for calculating the area as motivation, though its not strictly necessary.

[@MrAhYo]

Great approach to solving this problem. This video has inspired me to ask you for more combinatorics problems 😀

[@pandas896]

Yes please

[@tajabdullah.malaysia]

Appreciate those who can do mathematical studies and their role in scientific discoveries and going to moon and Mars or Jupiter

[@darkseid856]

You chose your shirt very cleverly . 🤣👌

[@kraftykoder280]

yeah, supporting Soviet !! 🤣

[@Devkumar-eo9gv]

Hail communism

[@juliap.5375]

@@kraftykoder280 *nerd mode on* Soviet translated as Council. Council is literally form of “direct democracy” which arrived among Russians independently from communists/socialists/etc. Such councils voted for any aspect of live and it’s how they accepted decisions. Soviets arrived everywhere, as example on factories, houses, army, etc. and they often elected someone as own manager/leader/director/etc. And because communists were incredible popular, in most Soviets elections won communists. Communists also liked such structure (direct democracy, total equality), that’s why when communists came to power, they preserved Soviets and Soviets became backbone of state. But, Soviets have nothing common with red color. Red color - it is about communism :) While Soviets - form of democracy, direct democracy. During so-called Cold War, nobody translated word Soviet to prevent explanation of system to own people, kind of propaganda (soviet system represent far more democratic system than had/have any modern capitalistic country, that’s why oligarchy never explained such aspects to own people). But after dissolve of USSR, Soviets not gone. As example Russian Senate officialy is called “Soviet Federation” 😂 But again, for propaganda purposes, nowadays in West they already translated word Soviet and now it sound as “Federation Council” 😂

[@affineline]

Both sums are counting sum of "number kth powers" less than n... for all k between 1 to n...

[@sergiysidenko]

I looked over the problems from all Soviet Math Olympiads up to 1987, and I haven't found this problem at all. However, it looks very familiar to me, and I did see it before. I'll try to dig some more.

[@fariasmaia]

Beautiful problem!

[@hindigente]

Very interesting problem. I like how you built intuition for the solution.

[@kaiyi1218]

At 11:59 I think you need to prove that n^(1/n) < 2. If this were not true, the right hand curve would be n instead of the desired one.

[@jacemandt]

I see what you mean, but 2^(1/2)=sqrt(2) is already less than 2, and we agreed earlier in the proof that n^(1/n)-->1 as n-->infinity, so that expression will stay less than 2 for sure.

[@kaiyi1218]

@@jacemandt Agreed. At the least it should be asserted, though

[@otakurocklee]

Yes, I agree. He assumes this but it is not obvious. If you take the ln of both sides, we need to prove (1/x)ln(x) < ln(2). You can show that (1/x)ln(x) has a max of 1/e which is less than ln(2)

[@otakurocklee]

@Katharsis At 5:48, he draws that rectangular box inside A. The sides of the rectangle are x goes from 1 to n. and y goes from 1 to 1/n. He should prove that this box has no integer points within its area. He assumes this but doesn't prove it.

[@noway2831]

neat. the horisontal versus vertical counting to convert exponents to logarithms is very nice.

[@yuzhe6054]

Great vid as always.

[@yahav897]

Great! Thanks for these videos :)

[@mustafaemrebasaran7701]

That is brilliant. Thanks for sharing!

[@tcoren1]

6:11 shouldn't the lower bound be 0?? Like the x integral ingrates the function proper, not the function minus 1, hence the y integral should start at 0. You've missed a section with an area of n-1

[@pantognost]

Hi! Just came across this. I have a question. This process is intuitive and passes the point of the theorem to the viewer. However is it a formal axiomatic proof of the theorem? I am wondering if it is because I want to know if this intuitive integer counting that you do in the end can be derived in a more formalistic way than the “we understand that...” method. Very good explanation of the problem though! Really passes the “why” to the viewer!

[@caesarinchina]

Same... I would guess it takes a few extra steps to be rigorous but I don't know how I'd do it 😅

[@chunchen3450]

Definitely provide more insights on calculating integral from y variable instead of conventional x variable. Maybe Michael can give a a more general case of doing integrals like this next time, and some assumptions, thanks

[@bhanwarlalnehra7830]

Your videos are very intuitive. Please make videos on iit jee problems you will find them interesting

[@gupta-pw5xb]

This is *OUR* problem.

[@ayoubsbai6339]

You beat me to it lmao

[@marshallnoel2045]

This is an incredible solution.

[@miksurankaviita]

The counting argument is quite cool. When I solved the problem, I just wrote an indictive proof.. If the equality holds for n, then any term in the sum that increases for n+1, will have a corresponding term that increases in the other sum😁

[@blazesedzikowski1071]

Nice .... BUT ... for n=2 left side = sqr(2) and right side = 1. Isn't it ?

[@rish5827]

You’re applying the floor function to every term. Which means you round down to the nearest integer. So root(2) ~ 1.4 which rounds down to 1

[@sam08g16]

A classic problem from OUR maths olympics

[@JanPBtest]

Isn't the first integrand for A equal to n^{1/x} - 1, not n^{1/x} ? Or, equivalently, the lower bound of the first integral in the second expression for A equal to 0, not 1 ?

[@risingsun9064]

Nice video, but I think you didn't need the integral for the counting argument.

[@bscutajar]

My instinct would've been to try an inductive proof, but no idea if it's even possible

[@digxx]

You can also prove it algebraically. Since floor(log(n)/log(k))=m iff n^{1/(m+1)} < k =n. Choosing m=n is simplest though. Splitting the sum and reindexing m->m-1 in the second sum, then canceling common terms, it is readily found to be sum( floor(n^{1/m}) , m=2..n).

[@SeyseDK]

Wow excellent. Tried an hour, used the same integral even. Never occured to me, using int points

[@PalmerPaul]

Interesting example of a combinatorial proof!

[@maxhaibara8828]

I'm glad we all can solve this

[@modolief]

Great content, thanks!!!

[@dc99999]

I'm struggling to understand how the equation even holds for n=2 (or n=3). Don't we end up with sqrt2 = 1?

[@Тестканал-н7ю]

sqrt(2) is approximately 1.42, thus floor of sqrt(2) equals to 1. 1=1. The same thing with 3, i believe.

[@Тестканал-н7ю]

I hope that is the floor function and I'm not confusing the names again...

[@dc99999]

@@Тестканал-н7ю Oh of course... I didn't realize that was the floor symbol. thanks!

[@mathissupereasy]

What does [ ] in the question stand for?

[@joaozin003]

n^1/x is xthroot(n)

[@noninvasive_rectal_probe8990]

Wait, how you can give this hunky guy. I would spent all time in class for fantasizing dreams of him and me.

[@noninvasive_rectal_probe8990]

@@newkid9807 keep throwing out this big words for nothing, destroying your reality

[@nournote]

You lost me at 3:15. What does it even mean to have a continuous version of a sum of integers?

[@indeedhid380]

He meant it as an analogue. Instead of summing f(n) where n is an integer, we "sum" infinitely many f(x).

[@VaradMahashabde]

@@indeedhid380 multiplied by the Edith of the small difference between each x

[@timurpryadilin8830]

My teacher gave me that exact problem recently, and I solved it without integration. In Russia it is uncommon to use calculus on olympiads

[@redkino]

Is it High School level olympiad? AFAIK you can solve most of olympiad problem without calculus.

[@MichaelPennMath]

You don't "need" the integrals for a solution. My goal was to build intuition for the solution by looking at a continuous version of the problem.

[@joshyman221]

Michael Penn I agree it was a nice first step. It’s not like you actually did the integrals!

[@timurpryadilin8830]

@@redkino I did some research about Russian Olympiads of that time, but I couldn't find this one. The problem can be that there were several steps in the olympiad (Soviet, Republican , etc.). Tgere is also a famous Moscow Math Olympiad and others. I couldn't find the source

[@newkid9807]

Timur Pryadilin tgere was niche at most, you’re over exaggerating

[@weishanlei8682]

You did not say that n is a positive integer.

[@nahidhkurdi6740]

There was no need to mention integrals, I think. Very cute counting argument, though.

[@athysw.e.9562]

You should try the 2005 Putnam A6 question, very nice solution for this problem BTW

[@utkarshverma9636]

Did you give the Penn-rose equation ?

[@linggamusroji227]

In Soviet olympiad, you can see other participant's answer because their answer are OUR answer

[@shambosaha9727]

In Soviet Olympiad, the answer writes you.

[@donaastor]

why calculus and integrals??? this some counts the number of perfect powers right? actually not that, but rather the number of expressions of form a^b whose value is less than n. the first one groups thses by the power and the second by the base. QED

[@donaastor]

ah sorry, you already said. you wanted to build intuition...

[@byronwatkins2565]

Why did we need the calculus?

[@davidmeijer1645]

Ok, great. That’s an understatement

[@ラー油美味しいチャーシューめん]

Depending on the difficulty of manipulating all the logs in different bases, this looks like a useful identity for floor functions. So being lazy, it seems there would be a similar relation for ceilings.

[@jogeshgupta7583]

Hey Michael.....mind blowing question like every time....remember my name “Snehel “

[@lordzuzu6437]

You had me at Soviet.

[@juanixzx]

I don't know why you paint A from 1 to n in the Y axis, shouldn't it be from 0 to n, as the definition of an definite integral, the area bounded by X axis and a curve?

[@charliebaker1427]

cause n^1/0 cant exist or is undefined rather thus 1 is the minimum

[@juanixzx]

@@charliebaker1427 yes, but the area behind a curve doesn't depend of the asymptotes of the curve. I take an example with Wolfram, choosing an n = 3, and clearly shows that area goes from y = 0 (the X axis) and the curve n^(1/x). www.wolframalpha.com/input/?i=Integral+of+3%5E%281%2Fx%29+from+1+to+3

[@juanixzx]

@@charliebaker1427 I saw that area for y = 0 to 1 is not important for the discrete reasoning he does, because both sides of the equation (curve respect x and respect y) the number of discrete points behind 1 is the same, and can be missed, but it's not rigorous for me.

[@johnfox2483]

Is this problem supposed to be solved this way, or there are another, simpler methods ?

[@shalvagang951]

BUT THAT COUNTING OF INTEGER SOLUTION WAS SOMETHING DIFFRENT

[@SheevPalpatine660]

Wow, i understood you explanation about this task, though i do not very well English language and mathematics

[@IoT_]

Вероятно, что-то в математике ты понимаешь)

[@sumitprajapati821]

Mind Blown 🤯🤯

[@muhammadsarimmehdi]

4:26, why is ln(n)/ln(y) = logy(n)?

[@muslimabumuslimow5654]

He uses one of the logarithmic rules. Loga(b)=logc(b)/logc(a). In this case with the base e. Ln(a)=loge(a)

[@Djorgal]

c= log_b(a) ⇔ b^c = a ⇔ (e^ln(b))^c = a ⇔ e^(c ln(b)) = a ⇔ c ln(b) = ln(a) ⇔ c = ln(a)/ln(b) Thus, log_b(a)= ln(a)/ln(b)

[@Fun_maths]

Here in Soviet Russia, we don't use sums, we use integrals

[@ibouchoucha]

What's about the case n=2 !!!!! does it mean log2(2) = 2^1/2 ???? That's wrong right ?!

[@LordDark102]

Yeah log2(2)=1 and flor of 2^1/2=1

[@LordDark102]

Because flor of 1,4=1

[@pow3rofevil]

very nice 🤘🏻🤘🏻🤘🏻

[@sionelbaz9899]

LOG (OMEGA +1) = 2 LOG(OMEGA) HYPERZOLI

[@sionelbaz9899]

log (N^N)=Nlog(N) = N depuis cantor NxN de cardinal N

[@sionelbaz9899]

log (n^N) en base n log (n)=1 et on a donc la lasomme d'ensemble denombrable = N denombrable

[@williamnathanael412]

Why doesn't it hold for 1?

[@EquuleusPictor]

Cause log_1(n) doesn't exist.

[@RomaxSinergy]

*С первого раза не понял* В 1982 году олимпиады по математике были очень тяжелые. Стране тогда ещё была нужна наука и научные кадры.

[@ВалерийЖмышенко-г7й]

Вроде бы, олимпиады в России только усложняются.

[@AnuragSingh-mo5nb]

this is not soviet mathematical problem, this is OUR mathematical problem

[@NVDAbets]

I got lost at 6:48 min mark... Will watch again

[@professionalprocrastinator8103]

You decompose that area under the curve into a rectangle of sides n-1 and "?", and the rest. "?" is found by saying that it corresponds to the y-coordinate of the point on the curve where x = n. So by reinjecting inside y = n^{1/x}, you find that ? = n^{1/n}

[@tsarnature6587]

*LAUGHS IN CONFUSION AND TEARS*

[@guest_of_randomness]

so satisfying...

[@grisus7254]

You lost me somewhere in the middle

[@joysuryadutta2306]

in all sense u resemble Mycroft from BBC's Sherlock

[@roberttelarket4934]

Damn can't you get a larger blackboard and write larger?

[@wychan7574]

This is a false conjecture. When n=2，2^1/2 not equal to log 2 = 1.

[@Czeckie]

awesome