Solving the hardest question of a British Mathematical Olympiad
Вставка
- Опубліковано 28 вер 2024
- Thanks to Nahian for the suggestion! This is a difficult factorial problem.
British Mathematical Olympiad 2002-2003 problem 5
bmos.ukmt.org....
A Mathematical Olympiad Primer Paperback - 1 Aug. 2011
www.amazon.co....
Math Forum post
mathforum.org/l...
Math StackExchange post
math.stackexch...
Subscribe: www.youtube.co...
Send me suggestions by email (address in video). I consider all ideas though can't always reply!
Like many UA-camrs I use popular software to prepare my videos. You can search for animation software tutorials on UA-cam to learn how to make videos. Be prepared--animation is time consuming and software can be expensive!
Why are there comments before the video is published? Get early access and support the channel on Patreon
/ mindyourdecisions
If you buy from the links below I may receive a commission for sales. (As an Amazon Associate I earn from qualifying purchases.) This has no effect on the price for you.
Show your support! Get a mug, a t-shirt, and more at Teespring, the official site for Mind Your Decisions merchandise:
teespring.com/...
My Books (US links)
Mind Your Decisions: Five Book Compilation
amzn.to/2pbJ4wR
A collection of 5 books:
"The Joy of Game Theory" rated 4.2/5 stars on 105 reviews
amzn.to/1uQvA20
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" rated 3.6/5 stars on 10 reviews
amzn.to/1o3FaAg
"40 Paradoxes in Logic, Probability, and Game Theory" rated 4.1/5 stars on 20 reviews
amzn.to/1LOCI4U
"The Best Mental Math Tricks" rated 4.4/5 stars on 25 reviews
amzn.to/18maAdo
"Multiply Numbers By Drawing Lines" rated 4.5/5 stars on 16 reviews
amzn.to/XRm7M4
Mind Your Puzzles: Collection Of Volumes 1 To 3
amzn.to/2mMdrJr
A collection of 3 books:
"Math Puzzles Volume 1" rated 4.5/5 stars on 30 reviews
amzn.to/1GhUUSH
"Math Puzzles Volume 2" rated 4.5/5 stars on 10 reviews
amzn.to/1NKbyCs
"Math Puzzles Volume 3" rated 4.5/5 stars on 8 reviews
amzn.to/1NKbGlp
Connect with me
My Blog: mindyourdecisi...
Twitter: / preshtalwalkar
Newsletter (sent only for big news, like a new book release): eepurl.com/KvS0r
2017 Shorty Awards Nominee. Mind Your Decisions was nominated in the STEM category (Science, Technology, Engineering, and Math) along with eventual winner Bill Nye; finalists Adam Savage, Dr. Sandra Lee, Simone Giertz, Tim Peake, Unbox Therapy; and other nominees Elon Musk, Gizmoslip, Hope Jahren, Life Noggin, and Nerdwriter.
I am always excited and nervous when I post a video like this! One the one hand, I am thrilled to share a challenging mathematical proof. On the flip side, proofs require perfection and it is very challenging to make a video with no errors. You guys have great attention to detail, so if you see any mistakes, let me know! For major mistakes I will repost a corrected video; for minor mistakes/typos I will leave a note in a comment. Hope you enjoyed this problem!
Hy sir i wana talk to you
ily! and ur videos!!, they help me learn so much! (I have completed pre calc course and I'm in middle school lol)
You wanted solutions on the positive integers so you didnt have to check a=0 at the start of the video. Very minor mistake.
More challenging stuff like this please!
13a=13+a please help me for the solution
"Pause the video if you would like to give this problem a try"
Thanks for your concern, I'll just skip 10 seconds instead.
ua-cam.com/video/l8S0p-91h7A/v-deo.html
No need to pause.....the short interval provided was enough to put together the proof
😅😅😅
He should have said turn off your device for a week as you attempt to give this problem a try...
😂
Great proof, but how would one know they needed to prove that b
Probably with lots of previous experiences with similar "proof" questions that used this kind of boundary checking/contradiction tests.
You don't know that. The way he presents this is not the way you start thinking about the problem. I started out, trying a few easy values like 1 and 2 for a, b and c. You immediatly get a contradiction so you can keep that in the back of your mind. Sometimes this will come in helpfull later on and sometimes it wont. If you have some practice you will learn more tricks, that you can just kind of throw at the problem and see what happens.
Experience
I'm a GCSE student and these kinds of videos are always fun to watch. I love maths but never understood how people even know where to start with these questions. I lost track of what was going on like a minute into the video.
Hello, British Mathematical Olympiad here, thanks for reviewing this question. I did actually get this question right in the olympiad but there is a much more simple way!
Nice puzzle. I solved it kind of similarly but when I got to a
I did the same way that you do, and eventually you can get the conclusion that n=0 and m=1, just aplying that n! is even if n is equal or greater than 2
There is an easier way to show a contradiction. Once a < b < c, then b! divides a!*b!, b! divides b! and b! divides c!. But b! cannot divide a! Then c < b (that's not our case) or a = b.
how does anyone even come up with this
Drugs.
Lots of drugs.
For real, how would someone know what to prove at the start?
miracle, I guess.
@@nelser1160 So, when you solve so much of questions like these, it's easy to check these metods and get bounds.
@@rustemtehmezov9494 I wonder how many I have to solve to get that lol
And without using the Gougu theorem...
You are my favorite youtuber,
I never miss any of your videos
Cool
Me too as I have turned on the bell
actually amazing proof, i think u covered every possibility. i don't think i've ever seen contradiction used better than this before!
Halfway through i stopped listening and started reading comments.
same😂
This is one of the best math proofs, I have seen
The part showing a=b may be simplified (Time 4.44 to 7.44). Instead of dividing by a!, divide by b!. The left-hand side will be an integer a! and the right-hand-side of the equality will be a fraction a!/b! + 1 + c!/b! (since a
4:10 Proposing that we have not yet shown that b < c because we’ve yet to prove that a solution exists. I suppose, when including later steps that proceed similarly, the proof proceeds on the assumption that a solution exists.
Your definition of wonderful is WAY different than my definition of wonderful!
Power of belief, Dare to believe 👇
ua-cam.com/video/ygc-B_OHz9w/v-deo.html
You could’ve proven the fact that a=b much easier if you divided both sides of your equation by b! instead of a! at 4:53. This is because we already knew that a is less than or equal to b, so the case where they are not equal would mean aa (as previously shown), c!/a! is an integer, and 1 is obviously an integer, but since b>a, a!/b! is not an integer, thus a! isn’t an integer. And that’s a contradiction. It’s a lot simpler and quicker way to get to the same conclusion.
We immediately notice that the equation is invariant under a swap of a and b, so we may assume, without loss of generality, that b is at least a. Now, we don't know that c is at least b. We know that a! divides c! (reducing everything modulo a!). We would like to know that b! divides c! as well, which is equivalent to c is at least b. So consider. Note that since a is at most b, a! is at most b!, so a! + b! is at most 2b!. Suppose c < b. Then c! < b!, so a! + b! + c! is at most 3b! < a!b! once a > 2, so the only solutions with c < b have a = 1, 2. Suppose a = 1. Then b! = 1 + b! + c!, so c! = -1, a contradiction. So a is not 1. Suppose a = 2. Then 2b! = 2 + b! + c!, so b! = 2 + c!. Since we're assuming c < b, reducing modulo c shows that c divides 2, so c = 1, 2. But 2 + 1! = 3 and 2 + 2! = 4, neither of which are factorials. So there are no solutions with c < b, thus c is at least b.
Now at this point, we could do a more convoluted argument that I did first, but I realized a simplification to my argument as I type this up, so in the interest of my thumbs I will present this more streamlined argument*. Since c! is divisible by b!, reduce the original equation modulo b!. Then we get that a! = 0 (mod b!), so b! | a!. But then since a! | b!, a! and b! are associate, and since they're both positive integers, this means a! = b!. But then a = b. So we can reduce the original equation to a!² = 2a! + c!, and dividing everything by a!, we get a! = 2 + c!/a!.
Suppose for the moment that a > 2. Then 3 | a!, so reducing modulo 3, we see that c!/a! - 1 is divisible by 3. Thus c!/a! is not divisible by 3, and thus c = a, c = a + 1, or c = a + 2. c = a means that a! = 3, impossible. c = a + 1 means that a! = a + 3, leave that for now. c = a + 2 means that a! = a² + 3a + 4. Reducing modulo a, we see that a | 4, so a = 1, 2, or 4. Since we are supposing that a > 2, a = 4, but that. polynomial at 4 yields the value 32, which is not a factorial. So the only option is c = a + 1, which entails solving a! = a + 3. Now, for x > 3, we have the following inequalities of functions: x! > 2x > x + 3, and thus since we've assumed a > 2, our equation can only hold if a = 3. Indeed, 3! = 6 = 3 + 3, so (3, 3, 4) is a possible solution--indeed it is, 3!3! = 3! + 3! + 4!. This is thus the only solution for a > 2.
Finally, recall that if a = 1, we get a contradiction--we did not use the assumption c < b for that. So assume a = 2. Then we wish to solve b! = 2 + c! with no restrictions on b or c. Since we know there are no solutions when c < b, suppose not, and reduce modulo b. Then we see that b | 2, so b = 1, 2. If b = 1, we get c! = -1 again, impossible, and if b = 2, we get c! = 0, still impossible. Thus there are no solutions if a = 2 either, and the only solution in the positive integers is (3, 3, 4).
*In my original argument, I reduced modulo 2 instead of modulo b!, which shows quickly that b = a or b = a + 1. I then treated these cases separately (obviously, from the argument I have presented, the case b = a + 1 ended in contradiction). Some interesting stuff came up, but it's not as elegant as reducing modulo b! and showing directly that a = b.
I was so close to the answer
I bow down to you my lord.
Good
How close?
What did you do?
Once you establish 3
It is somewhat easier to prove that a=b, for if b>a, then a!=a!/b!+1+c!/b!. Here the 1st term on the rhs is 1/n < 1 and the last term is either integer (which wouldn't work) or 1/m. But then 1/n+1/m must be 1 so a=2 and 2b!=2+b!+c! or b!=c!+2 with no solution.
Fun fact: A prime number in russian is "простое число", which can mean simple number too,therefore, a prime number is the opposite of a complex number
_Prime number_ is the "opposite" of _composite number_ . A composite number is a (positive) integer that can be written as the product of two (positive) integers that are both not equal to 1 ; in other words, a composite number is _composed_ as the product of two (non-unit) integers.
(For example, 35 is a composite number because 35 = 5 * 7 . Another example: 9 is a composite number because 9 = 3 * 3 .)
The word _complex_ also means "composite"/"composed", but in a different way: a complex number is composed as the sum of a real number and an imaginary number. (Since the real number may be 0 and/or the imaginary number may be 0i, a complex number may also have just a real value, or just an imaginary value.)
Wlog a>=b and right from the start use b! - 1 = b!/a! + c!/a!, note that on the right are only integers or numbers >0 and = b = a - or a!=2, b!=c!=1 (which doesn't work). So a!^2 = 2 a! + c!, or: a! - 2 = c!/a!. In particular, the right hand side is positive, so a > 2. As (2a)!/a! > a!, we see c
it took him a little long to prove a=b, if you divide both sides to a, then rewrite the equation and divide both sides with b, the only solution would be a=b
Thumbnail: solve
Me : NO
Because I can't 😂😂😂
The numbers are small, so trial and error will take less than ten minutes.
Thumbnail : solve
Me : Yes
Brain : Can't
Me : No
Presh : HAH! I KNEW IT!
I didn't even try. I had to pause the video several times to digest the information. Wonderful indeed
The next-to-last step where you showed ca, we know c=a+1. Further, we can see that c itself is congruent to 1 mod 3.
This problem is even tougher when you’re still grappling with why 2 is less then 3
i find it amazing that people can derive this prove out of thin air
I have trouble following it even as I am watching the solution
and I wonder how can someone take the necessary steps and making the correct deduction without knowing what the solution / direction to the solution is
well done for having this problem, made my day
Let me think... (a!-1)(b!-1)=c!+1
However the function of factorial is extremely exponential. Just try to find the correct c!+1 to equal to the multiply result of a!-1 and b!-1.
function result of ! equals to 1,2,6,24,120,720,5040,40320,362880,3628800.
I've found out 5*5=25. a=3, b=3, c=4. Don't know if there are other answers.
It was hard enough to follow your explanation! Thank God I didn't even try to solve it myself!
Not sure, but maybe there is a faster way. Assuming that m=b!/a! is more than 1 and c >b, we get that m divides b! and should thus divide 1+m+c!/a!. Considering the fact that C!/b! is divisible by m. Thus 1 should be divisible by m. Hence m=1
Hello Presh, can you please add in the description of your videos the requirements of what math concepts we need to be familiar with to solve each problem??
I luv ur videos!
Keep up the great work!
This channel reinvigorates my interest in maths. Generally I can follow the solution but this one lost me. But still, it's fascinating to watch. 👏😄
Remind me why factorials are useful, besides math classes as an engineering student, I have never come across any situation where a “!” has been necessary. Maybe some CS fold can chime in with an application?
For example, calculating permutations and combinations and, with them, probabilities
Thank you so much for uploading this video. It is helping me to get through the pandemic!
Maths exam: Find all solutions in positive integers... Show your steps.
Me: Yes
That's a very nice solution, in most parts a bit simpler than mine. Nevertheless, I think this one could be simplified even further. When trying to prove that a = b by deriving a contradiction from b! = 1! + b! / a! + c! / a!, we could argue as follows: b divides b! (obviously), b divides b! / a! (since a < b) and b divides c! / a! (since a < b < c). Thus b would need to divide 1 as well, which cannot be for b > 3.
I actully solved this problem the same way you have but the part you proved a=b i did it in a way simpler way , i divided both sides by b!
1:48 "suppose A is either zero or one" -- why would I suppose that A could be equal to zero, when the problem clearly states that the values of A, B, and C are limited to positive integers?
For the sake of argument, I guess?
In some languages/cultures/education systems, 0 is considered positive (as well as negative). Presh was just being rigourous.
U dont need to check the case of a=0 since we're talking about positive integers, otherwise (2,2,0) would be also a solution
Simetrical equations in most cases lead into result that those variables are actually equal, as in this case.
Got it in first look
Obviously 😂
Please make a video on epicycles and fourier transformation
Finally a quality video from you. Was missing such videos ❤
What a backhanded compliment...
What a solution you are a Brilliant man, Maker of this problem must be a Genius.
I would solve in a different way, considering the number of zeros at the end of a!b!. This goes as (a*b)/16 more or less, and the number of zeros at the end of a!+b!+c! is around min(a,b,c)/4, therefore if the minimum is c you get easily a contradiction, if the minimum is a (or b), you get that b (or a) has to be less than < 5 to avoid having LHS >> RHS. You can make easy considerations for the case b=3 and b=4 and find the solution.
I don't see how considering c to be the minimum would give a contradiction. Why couldn't you have (a*b)/16 to be about the same as c/4 ?
No need to test a = b = 4, c = 6. Since c!/a! is not divisible by 3, c cannot be a multiple of 3. Additionally c = a + 2 only works if a is a multiple of 3, otherwise c!/a! will be divisible by 3.
We have a problem that is easy to check, but took several proofs-by-contradiction to solve.
Does this have any bearing on the famous P=NP problem?
Minor detail: You don't need to check the case a=0, since the description specifies positive integers.
I find the step after noticing the symmetry completely unobvious and statements to prove-arbitrary. Starting with divisibility for me is much more obvious.
At time 3:00, an alternative is to continue to let a=3, then c!=5b! - 6 = 4b! + (b! - 3!) > b! (Because b >=3), i.e., c > b.
This problem is based only on assumptions. a,b, and c are just any random numbers.
First
*What stops a from being any multiple of 3 (other than 0)? I agree that the solution is unique, but how would you prove that?*
I just plugged things in and hoped I was lucky.
At 1:37 I decided the hints would make it possible to solve by inspection. And ten seconds later, I did.
I randomly stumbled upon the thumbnail of this video and tried to solve it.
I did not find the solution yet, but I made some progress. I swear, I'll find it! And only then, I'll watch the video =D
Another way is show that
(a! - 1)*(b! - 1) = c! + 1
Once we have that, we know that (c! + 1) doesnt have any factor below the c.
So, we have that:
c = 1 -> c! + 1 = 2 -> there is no "a" that (a! - 1) = 2
c = 2 -> c! + 1 = 3 -> there is no "a" that (a! - 1) = 3
c = 3 -> c! + 1 = 7 -> there is no "a" that (a! - 1) = 7
c = 4 -> c! + 1 = 25 = 5*5 = (6-1)*(6-1) = (3!-1)*(3!-1) -> a = b = 3
c = 5 -> c! + 1 = 121 = 11*11 -> there are no "a" and "b"
c = 6 -> c! + 1 = 721 = 7*103 -> there are no "a" and "b"
...
Now that we have one solution, we have to verify if there are more solutions for "c > 6". And that I don't know how to do!
I figured out 3, 3, 4 quite quickly but I can't prove whether it is the only solution or not.
I found the unique solution at random assuming the case of a = b, then trying 0, 1, 2, 3, but couldn't prove it was the only case.
The logic in solving this question is awesome.
Very nicely done! Thank you for that!
This is my second time watching this. Alas, I still couldn't prove 3,3,4 was only solution, lol. Great video btw.
I think there is a logic error. Yes since 3
I have a problem dude : Take a semi circle.then a rectangle whose length is less than diameter of circle and its based upon diameter of that semicircle at down and ( let's consider a side supppse right) at right its lower vertex and corner of semi circle make up and end ( end there touching each other) rectangles upper face intersects circle tangentially at its max point vertically and a line drawn from prev.corner to rectangles and circles intersection( not tangential) = 10 cm find the rectangles area.
Answer is 50 cm² . The surprising thing is that the ratio (rectangle length)/(circle diameter) and/or the rectangle's aspect ratio (length:height) don't affect the answer.
Let
d = diameter of semi-circle
L = length of rectangle (along the base)
b = height of the (non-tangential) intersection between rectangle and semi-circle
c = length of line from intersection to left bottom vertex of semi-circle
α = angle between 10 cm line segment and base
The area T of the triangle with sides d, c and 10 (which is a right-angled triangle, due to _Thales's theorem_ ) is given by
T = b*d/2
but also by
T = 10*c/2
==> b*d = 10c [eq. 1]
Furthermore, note that
tan(α) = b/L = c/10
==> c = 10b/L [eq. 2]
Plugging this result into eq. 1 gives
b*d = 10*10b/L
d = 100/L
L*d = 100 [eq. 3]
Required is area of rectangle, which is
A = L * d/2 [eq. 4]
Plugging the result of eq. 3 into this, gives
A = 100/2 = 50 cm²
This was really hard, I didn't even know how to start.
Power of belief, Dare to believe 👇
ua-cam.com/video/ygc-B_OHz9w/v-deo.html
I understood all the steps and a very well done, but how am I supposed to do all of this in the first place
My brain crazy to solve this problem
This is like watching Sherlock Holmes solving a crime
70% through the video.
And I'm gonna go put my brain into a freezer then onto a vibrator before using it any further.
The solution was NP complete... Easy to understand the verification steps but difficult to identify the verification steps.
It’s not incredible.
It’s *magnificent*
I thought so
*french spy intensifies*
I have a different solution involving Wilson's theorem. Though it's easier to state the solution first before proving it.
Define n = min(a,b,c)
a, b >= 3 (look at the first part of the video)
Thus a!b!, a! and b! = 0 (mod 3), thus c! = 0 (mod 3). So c>=3, and n>=3
We know that there are only 2 values of a! mod (n+1)!, 0 and n!. And a!=0 mod (n+1)! iff a>=n+1. So
a!b! =a!+b!+c! (mod (n+1)!)
pn!n! = qn! (mod (n+1)!)
pn! = q (mod (n+1))
Where p = 1 if a=b=n, otherwise p=0
And q is how many between a, b, and c equals n.
According to Wilson's theorem, there are 3 situations to consider:
a. n=3. This corresponds to
2p=q (mod 4)
Only p=1 and q=2 satisfies the equation, so a=b=3, corresponding to 3! 3! = 3! + 3! + 4!
b. n+1 is composite >=6. This means q=n+1 (mod n+1). This means q>=n+1>=6, but there are only 3 variables
c. n+1 is prime. This means p+q = 0 (mod n+1). The maximum value of p+q is 4. This shows that n=3, and n=3 results in n+1=4 being composite.
Me before watching this video: You know, maybe if I work harder on Olympic maths I could actually qualify for my country’s Olympics!
Me after watching this video: Ummm...or not...
No but it actually was an incredible arithmetics problem!! Challenging to understand but SO FUN!!
This problem was also on the 2019 Portuguese Mathematical Olympiads
These mathematicians must be so cool
Isn’t there like a region of math dedicated to these types of problems, its called number theory or something like that. Correct me if I’m wrong
Great example of using contradiction!
I died half way through the video. I lost too many brain cells. May I rest in peace.
Has c!+1=0 got a solution in the complex plane? If not, we can define another type of numbers, something like complex factorial :D
I tooke me two hours, but I solved it on my own
1:19 Why would a be less than b, I don't get it.
because there is no loss of generality
I understand what he is doing but i would never in a milion years ever think about doing that
make more number theory problems like this
Amazing problem and amazing solution.
4:00 yes you showed that b >= c leads to a contradiction.
That does not prove b < c.
It proves that iff a solution exists at all then b < c.
In other words you ignore the possibility that there are no valid solutions. Later in the video you demonstrate that at least some solution exists; only then is it rigorous to assert b < c
7:45 same criticism. We still don't know a solution exists at all
What an incredible problem. I wonder how the Olympiad committee come up with these problems.
Since some people are providing easy proof for a=b assuming c >= b, I am providing a proof behind that assumption. But it's worth mentioning that we have to prove c>=b. Here is the whole solution according to me to prove a=b.
Let's denote original equation
a!b! = a! + b! + c! -------- (1)
a
This can easily be solved by first dividing by a! then by b!. By doing this we get a=b . Then make a quadratic and solve.
How bro? I don't quite understand. If u divide both sides by a! b! u get 1=1/a!+ 1/b!+ c !/a! b! . So even if u prove this video method halfway upto a=b and apply it the above equation u get 1=2/a!+ c! /a! ^2. How do u turn that into a quadratic?
@@sadkritx6200 multiplying your equation by a!^2 then using shree dhara charya formula you get a!=1+root (1+c!)
now keeping in mind c>a
put some values of c.
By putting 4 as the value of c we get a!=6, hence a=3.
@@sadkritx6200 I did not say divide by a!b!. I said first divide by a! then separately divide by b! in another equation. From there we get that b!>=a! and a!>=b! . The inequalities can be true iff a=b.
I can understand every single steps in this proof, but how and who found it?
Anyway, contradiction is powerful. I just recognized it in another minesweeper video.
Power of programming 😂🎉:-
import math
for a in range(0,10):
for b in range(0,10):
for c in range(0,10):
if math.factorial(a)*math.factorial(b)==math.factorial(a)+math.factorial(b)+math.factorial(c):
print(a,",",b,",",c)
Python programme for the question 😂😂
Is it correct?
@@harshitvarma7867 yups
What an amazing problem. I wonder who comes up with these mathematical jewels.
"...But two does not divide fi-"
Amazing problem!
In what this can be used in life, if you are not math professor?
I wasn't born when this problem came in Olympiad
Moye moye same 5:32
At around 7:00... Why do all the terms need to be divisible by a+1 ?
I understood this much 🤏
Why does a>=3 and a|4 imply a=4? a could also be 8, 12, 16, 20, or any other number greater than 3 and divisible by 4.
a|4 means "a is a divisor of 4" (or equivalently: "4 is divisible by a"). So a cannot be 8, 12, 16, 20, because 4 is not divisible by 8, 12, 16, 20 (the division would result in a fraction).