International Math Olympiad | 1960 Q1 

My way to find the two cases was a little bit easier: Our three digit number 100x+10y+z must be divisible by 11. So we reduce it mod 11: 100x+10y+z = x-y+z =0 (mod 11) x,y and z are between 0 and 9, so x-y+z is between -9 and 18. In this intervall we have only two numbers divisivle by 11: 0 and 11. We have our to cases! Case 1: x-y+z=0 ⟹ y=x+z Case 2: x-y+z=11 ⟹ y=x+z-11

I love how he's not automatic when it comes to 64+9 hahaha. I see this with Math profs all the time: they're mathematicians, not calculators.

Doing this in competition, you'd probably want to completely solve for x in terms of z using the quadratic formula, then plug in the different values of z one by one. It would also be quicker to check whether the discriminant was a perfect square or not for different values of z, which rules out a lot of cases.

Me, an intellectual: brute forces from 110 all the way to 990

From Indochina, I'm preparing for the Math Olympics and your videos help me so much. Thank you Mr. Penn!

If you are ready to some calculations you can avoid the "check" part. Case y = x + z : Expand the equation x² + (x + z)² + z² = 10x + z. It gives 2x² + 2z² + 2xz = 10x + z and see immediatly that z is even. One can see this equation as a quadratic in x writing 2x² + (2z - 10)x + (2z² - z) = 0. Compute the discriminant D(z) and find D(z) = -4z² - 32z + 100 = 4(25 - (z² + 8z)). Since the solution x must be an integer, the discriminant must be a perfect square. But for z ≥ 3 we have z² + 8z > 25 and then D(z) < 0. Since z is even, the only possibility are z = 0 and z = 2. But D(2) = 20 is not a perfect square. Thus z = 0 and the quadratic equation becomes 2x² - 10x = 0. It leads to x = 0 (impossible) or x = 5 (so y = 5 and N = 550). Case y = x + z - 11 : Expand the more tiedous equation x² + (x + z - 11)² + z² = 10(x - 1) + z. It gives 2x² + 2z² + 121 + 2xz - 22x - 22z = 10x - 10 + z. Reducing this equation modulo 2, one can see that z is congruent to 121, so z is odd. One can also see this equation as a quadratic in x writing 2x² + (2z - 32)x + (2z² - 23z + 131) = 0. Compute the discriminant D(z) and find D(z) = -12z² + 56z - 24 = 4(z(14 - 3z) - 6). But for z ≥ 5 we have 14 - 3z < 0 and then D(z) < 0. Since z is odd, the only possibility are z = 1 and z = 3. But D(1) = 20 is not a perfect square. Thus z = 3 and solving the quadratic equation we get x = 5 or x = 8. But y = x + z - 11, so x = 5 leads to y = -3 (impossible) and x = 8 leads to y = 0 (so N = 803).

Here is a way of cutting down the number of cases to check: First it is easy to show that with x = 0 there are no solutions, y = 0 the only solution is 803, and z = 0 the only solution is 550. Then with x,y,z >= 1: Case 1: y = x + z Expand out x^2 + (x+z)^2+z^2 = 10x + z to get 2(x^2 + xz + z^2) = 10x + z Collect terms to get 2x(x + z - 5) = z(1-2z) If z > 0 then the RHS is negative and so must be the LHS, so x + z < 5 or x + z 0 and z is even, then the only possible cases are when z = 2, and so the only numbers you need to check are 132 and 242, neither of which work. Case 2: y + 11 = x + z We can put some bounds on the allowables values for x, y, and z. Since x, y, z >= 1, 12

In case 2, z=1 doesn't work as y=x+z-11 which is negative. Love the vid, as always!

I remember the trick to find the remainder of a number when divided by 11. You add up the digits in the odd positions and subtract from this the sum of digits in the even positions. That gives you the remainder. For example 567. 5+7 = 12. 12 - 6 = 6. 567 divided by 11 gives you a remainder of 6.

Now I'm traumatised because he said "so that's a good place to stop" instead of "and that's a good place to stop"

I love this problem. Even though I could not solve it and got stumped, I found the result very interesting.

Thank you for the nice solution. It is also not so hard to calculate this more directly by hand. There are 81 three digit numbers N that are divisible by 11. For a lot of them, the sum of the squares of the digits is clearly bigger than N/11 (for example 132 has this property, which eliminates the need to check the other numbers between 132 and 200).

I actually worked this out. Thank you, professor. (I did try the backflip and almost killed myself.)

Thanks for the video! I really enjoyed it! My solution is a bit different but still quite similar, I also start with the case N=100a + 10(a + b) + b, then I consider two cases: Case 1: a + b < 10, so x = a, y = a + b, z = b and Case 2: a + b >= 10, so x = a + 1, y = a + b - 10, z = b For both cases I consider polynomial equations (parentheses to reflect dependence) 10a + b = 100 * x(a) + 10 * y(a, b) + b and 2 parametric (wrt a and b) quadratic equations for each. The quadratic equations have to have a non-negative discriminant, so that is how you can get ranges for both a and b. In particular Case 1: quadratic equation wrt a with parameter b immediately has a non-negative discriminant only for b in {0, 1}, so that is how we get the 550 solution. Case 2: we get that a is in {4, 5, 6, 7} and b is in {1, 2, 3, 4} which results in only 3 cases possible (a + b >= 10), that is (a, b) is in {(6, 4), (7, 3), (7, 4)}. Only (7, 3) solves the equation, so we get the second solution 803. P.S. to eliminate the number of discriminant sign checks in non-obvious identities we could use a binary search. :)

14:25 Quick question from Putnam 1990. As usual, solution in the comments. Let S be the set of 2 x 2 matrices each of whose elements is one of the 15 squares 0, 1, 4, ... , 196. Prove that if we select more than 15^4 - 15^2 - 15 + 2 matrices from S, then two of those selected must commute.

7:57 Using x=0 here actually gives you a one-digit number, namely zero itself.

First case, expand it out, we get 2x^2 + 2xz + 2z^2 = 10x + z. As noted, everything is a multiple of 2, except that single z at the end. Hence z must be even. Substitute z = 2k. 2x^2 + 4kx + 8k^2 = 10x + 2k. Divide by 2, we get x^2 + 2kx + 4k^2 = 5x + k => x^2 - 5x + 2kx + 4k^2 = k. Since x^2 - 5x is always even, this means that k is even. So, k is always even, and therefore, z is divisible by 4. Hence, z can be from {0, 4, 8}.

Did some modulo analysis and came up with some relationships, but then just went to brute force, because the pattern was to use the 11*(digit)^2 and then subtract digit*100,10, and 1 depending on position(9x4 table, 3 columns were just simple subtractions). because only the highest digit gives a negative value, you could easily look at the table to see where the sums of the other entries would equal that. Wasn't entirely satisfied with my brute force, but I think actually it took less calculation than constantly working quadratics.

The way he uses chalk is virtually Pennmanship!

Wonderfully explained.

For the 2nd case you can use x + z Greater or equal to 11 and reduce the checks so z = 1 is out for z = 3 x can be 8 or 9 .

Prof Michael Can you check this problem out from 1992 AIME Problems/Problem 15 ? It's a great problem indeed The problem states that Define a positive integer $n$ to be a factorial tail if there is some positive integer $m$ such that the decimal representation of $m!$ ends with exactly $n$ zeroes. How many positive integers less than $1992$ are not factorial tails? One of my fav AIME problems :)

I manually checked all 81 cases from 10*11 to 90*11

In second case when you say x=5 not working, you mean that 5+3-11 < 0. Thus, this is not valid representation of number.

y = x + z or y = x + z - 11 is another way of saying x - y + z = 0 mod 11 (which is the divisibility criterion for a three digit multiple of 11)

It can also be done like this (100x+10y+z)/11 = x²+y²+z² => 100x+10y+z = 11x²+11y²+11z² (equation 1) Also , by divisibility rule of 11 , x +z - y = 11 or x+z-y =0(largest difference cannot be more than 18 , which is in case of 909) Taking case 1 , x+z=y+11, Substituting in equation 1, 99x+10y+y+11=11(x²+y²+z²) => 99x+11y+11= 11(x²+y²+z²) => 9x+y+1 = x²+y²+z² => 9x+y+1= x²+y²+(y+11-x)² => 2x²+2y²+120+21y-31x-2xy =0 Whole number solutions are 8 and 0 Hence no. is 803 Taking case 2 , and solving it the same way , the other solution is 550 Hope it helps

Dang, I was trying to solve this before watching the video, but missed the restriction that N was a 3-digit number.

When in doubt, just gather data. So it was obvious that the number had to be divisible by 11. So I wrote down all the numbers from 10 to 90, then their 11th multiple, then the sum of squares. The first two were aided by an editor macro, but the last one I had to do by hand. And so I noticed that the sum of squares would very quickly outpace the first column - until an overflow happened and all the digits got lower again. So then I only sampled the sum of squares at all the places where an overflow had happened, and then every place afterwards until the sum of squares exceeded the first column again. And I did that for all the numbers and got the result that 550 and 803 are the only solutions. Maybe not elegant, but it works.

Case 2: y=x+z-11, x,z=>2; x^2+y^2+z^2=10x+z-10 implies (x-5)^2+y^2+z^2=z+15 implies z

Lol I did it by the divisibility rule by 11: Something is divisible by 11, if the alternating sum of the digits is divisible 11. Example: we have the number 2728, so we do 2-7+2-8=-11, and -11 is divisible by 11. By this, we can write our problem as "11|(100x+10y+z) -> 11|(x-y+z)" and then write that as "x-y+z=0(mod11)". Now we draw a table and try out every single combination of numbers x,y,z, where x-y+z=0 or x-y+z=11 . There would be really many combinations theoretically, but you get some kind of intuition after doing it a few minutes. I got both solutions after guessing for about 10 minutes...

There are no more solutions for numbers of any other length. 5-digit number can give you at most 5*81 = 405 as a sum of squared digits, but 10000/11 ~ 909. And for 4-digit numbers there is no solutions.

Please make more written algebraic passages so that we can better understand. Thankful.

Seems like a pretty easy problem for an IMO...

I have a problem suggestion, Find all functions f:N-->N such that n!+f(n)+m divisible by f(n)!+f(m+n) for all m,n in N.(0 is not an Natural Number.)

A much (easier? ) Or maybe less brain using solution. There are only 90 multiples of 11 less than 1000. So sum of square has to be less than 90. Now we can do a casewise analysis from 100-200,200,300... as follows If there is such no. In 100-200 then there must be 1 in it( it is first digit) also aum of square has to from 10-18. Subtracting one, we now know sum of square for other 2 has to be from 9-17. Try out all values(just bash it). Do it for all categories 200-300 etc

This one can be brute forced in just a few minutes with pencil and paper. Only 81 numbers to check and most of the sums of squares are obviously too big. Writing down all the 3 digit multiples of 11 is a fast process. It was a fun puzzle.

Very elegant problem

At the beginning, you would never start a solution (much less a proof!) that way “Let N be ‘the number’” is meaningless - the examiner would be immediately put off. Rather, let N be a 3-digit number having 11 as a factor, or “Let N be a 3-digit multiple of 11.” Make far more sense. A small, but key for beginners, point.

Love from Nepal 😊❤

Those are Math biceps. 🌟💪

Sir please bring a video to the solution of the legend of problem 6 from 1988 IMO held in Australia .

This was a fun proof, but brute-forcing it is actually easier by quite a bit. You only have to check ~40 numbers and do no analysis or algebra, compared to checking 10 numbers and a lot of analysis and algebra.

Here we're gonna look at the easiest problem asked in IMO ever! Anyways nice video!

For the (a+b)>10 case he was able to move the 10 to (a+1) @3:42 because a+b can only possible range between 11 and 18. Values >20 are impossible. Let’s say we were dealing with a different scenario like N/13. This changes the (a+b) to (3a+b) leaving a range up 36. How would we proceed then?

Love from India

Case 1: Good place to stop Case 2: Bad place to stop

You are the GOAT

Would not be easier if we are going to check so many cases to say number is xyz where they are integers and then check for each case of x x is 9 mean first number is 902 to 990 and the sum will be between 82 and 90 902 will not work since the sum is 85 bigger than 82 every time we add 11 we will increase y and z by 1 so the sum will be 81+(0+a)square+(2+a)square=82 +a which we can solve and see no valid a value or see that when a goes more than 1 you will have 81+9 and bigger alone by this 2 which will go over 90 the max number we have for divide by 11 x is 8 mean 803 to 891 and the sum between 73 and 81 803 sum is 64+9=73 which gives as a solution do the same trick to make a quadratic and solve 64+(0+a)square+(3+a)square=73+a 2a^a+5a=0 a(2a-5)=0 so only solution is a is zero which yeld us the 803 solution x is 7 means 704 to 792 and sum between 64 and 72 49+(0+a)^2+(4+a)^2=64+a solve the equation or see that if zx is 49 then rest must sum up to 15 to 23 704 is already bigger in the sum and for for any value of a other than 0 either 0+a or 4+a will be bigger than 5 which will sent sum over and thus have no solution x=6 means 605 to 693 sum between 55 and 63 36+25=61 36+(0+a)^2+(5+a)^2=55+a for a 1 and bigger either y or z will be bigger than 6 and alone with x will go over 63 thus no solutions x=5 mean 506 to 594 sum 46 and 54 25+(0+a)^2+(6+a)^2=46+a 25+(9-a)^2+(4-a)^2=54-a this one solved give a is 4 valid solution and thus 550 a solution and so on will not be easier and faster? only 9 cases to search?

11:23 z=1: .... so where y = x - 10 ....

It is so pleasing to see someone using horseshoe math for once 10:04

Good

So good.

is "000" considered a 3 number digit, because that's also a solution?

Please do IMO 2020 Q3

* Question : Have you ever taken any International Math Olimpiad exam ? * Answer : I was not aware !!!

Love you from Pakistan dear sir

so... just try different values of x and see whether any y works?

Mathematics is a painting which is still being colouring by mathematicians likr you

loved it

I like the way the mathematicans think, so logical and clear, but most importantly is inspiration thought, which computer AI cant do, Am i right? Are they?Is there any possibility that computer AI can solve math problems in these way?

You didn't find 000 = 0²+0²+0²

Hey sir I think you should improve your tag

nice

Yeah there’s only like 80 or 90 possibilities to test lol

Why isn't anyone asking where he got that formula at 1:05 from? N equals 11 times a^2 + b^2 + c^2 NOT 11 times 10a + b..those are not the same.so where did he get that from? Not justified and so frustrating..

This actually screams for Python. :D

ok, so that's a good place to stop lmao

I would be a talent if i were born 40 years ago... This problem is so easy to solve in 15 mins

Jesus fricking Christ - can't even go ONE MINUTE without being interrupted by ads. Sorry, Michael, but I just can't concentrate on your content when the mid-roll ads keep jumping in.