Croatian Mathematical Olympiad | 2005 Q11.1
ฝัง
- เผยแพร่เมื่อ 10 มิ.ย. 2024
- We solve a nice number theory problem from the 2005 Croatian Mathematical Olympiad.
Please Subscribe: th-cam.com/users/michaelpennma...
Personal Website: www.michael-penn.net
Randolph College Math: www.randolphcollege.edu/mathem...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchgate.net/profile/...
Google Scholar profile: scholar.google.com/citations?...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Books I like:
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu/ntic/
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/subjects/math
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
There are 2 little mistakes in the last board regarding the case that k=k.
2. When regarding the case of k=2 in the last line, you didn't plug it in correctly to the right hand side, the equation should be:
2l!=2+l!+m! => l!=m!+2, reducing that mod m, gives that 2 is congruent to 0 mod m which can only work for m=2, which is possible according to the first mistake.
Plugging m=k=2 into the original equation gives:
2l!=2+l!+2 => l!=4 but there is no solution here.
the first one is not really a mistake as m=k would give the same kind of equation that he got for the case k=l before.
@David Schmitz but you can still use the same argument. if m=k, then reducing the equation mod l+1 also gives either 0=2 or -1=2 mod l+1. neither of these give a new solution
@@demenion3521 yaa
@@demenion3521 actually, he would have to check the k=m
@@antoniopalacios8160 I think you are not right a little. As soon as k
2=0(mod m) ->
m=2
And k=2, k=m and it is possible on this stage. Now we must check the equation with this numbers, and find out that l! must be equal to 4...
When you procrastinate maths homework to watch more complicated maths 😎
The second part of Wilson's theorem has an extra case, which is n = p^2 for a prime p. That is proved by noting that 1 < p < 2p < p^2-1 (except for n = 2^2 = 4) and thus p^2 | 2p^2 | (p^2-1)!
17:10, it should actually be 2l!=2+l!+m!, which gives l! =m! +2, but this is impossible
No need to employ Wilson etc. By symmetry assume k=< l
For k=k. If m>k, then all terms except the addend 1 are divisible by k+1>1, a contradiction. So m=k and l!=2+l!/k! requiring k>1. Similarly to before, this yields the contradiction k+1>2 divides the addend 2.
Therefore, we must have k=l and get l!=2+m!/l! and therefore, l>2 and m>=l which yields m>l. Let d=min(m-l,l), then d! divides l! and m!/l! (note, that (m-l)! divides m!/l! using the binomial coefficient definition). So d! divides 2 and hence d=1 or d=2 smaller than l, so d=m-l.
d=1 gives l!=3+l. Division by l>2 requires l=3 and this yields a solution k=l=3, m=4.
d=2 gives l!=2+(l+1)(l+2)= l^2+3l+4. Division by l>2 yields l=4 which does not solve the equation.
Croat here, thanks for featuring my country :)
I am not a Croat, but I got annoyed when I saw Abramović misspelled :)
18:30 and by the way, how would you say “That’s a good place to stop” in Croatian ?
ok
the vid got 9 likes u got 5
@@birdbeakbeardneck3617 he does the work of god dude...
"To je dobro mjesto za stati."
greetings from Zagreb :)
Very elegant solution. Btw that problem is from Croatian state competition 2005, not from the Croatian Olympiad 2005.
Man, you are practically a Croat. And you make some very good videos... Greetings from Zagreb. :-)
The condition of n=p^2 for some odd prime p, also needs to be solved in the Wilson's thrm corollary.
if p>2, then p < p^2 and 2p< p^2, and thir multiplication gives 0 mod p^2
@@timurpryadilin8830 My comment was a suggestion for including this case. I know the proof and wasn't asking a question.
why.
Because numbers of the form n=p^2 don’t have two divisors a,b such that 2
Great video! I'd love to see a video where you talk about topics in your research area
Actually there is such a video. I guess it was done by redpenblackpen. That was a stream
Love your videos ❤
As Aviv Avital pointed out, m is not necessarily strictly larger than k. Also, the equation that results from dividing through by l!, which is k! = 1 + k!/l! + m!/l!, implies that 1 < k! < 3, since 0 < k!/l!
Im from Croatia! Its cool to know that youve been in my country lol
Oh he is from Croatia awesome
I'm from Dubrovnik, it's amazing that Michael visits us from time to time!
Cheers from Rijeka
Meni je drago da ima Hrvata na ovom kanalu ❤️
@@matejcataric2259 Treba širiti i naše znanje😄
Just an hour ago this is the fastest time evr that I've got ur video as recommendation
Thank you for this number theory proof!
Great teacher
You really don't need Wilson's theorem to prove that
k!=2+m!/k! has no solution (other than k=3,m=4).
If k>=3 and m>=k+3 then it has no solution because the left side is divisible by 3,
but the right side gives 2 as a residue mod 3.
That gives us few cases to check: k
Yes thats the way i did it too.
k!=2+(k+1)(k+2) or k!=2+(k+1)
This is for k>=3
Next put mod3 for both sides
In first case we gotta have (k+1)(k+2)=1(mod3) which is impossible
And next k!=k+3 for k=3
Which is the only solution
We can easily check for k=1 and k=2 which gives us no solutions
(I dont know wilsons theorem. If i had known maybe i would have used it. But this ques doesnt really require that)
@@Goku_is_my_idol me too!
4:35 this isn't possible if n is a square of a prime p, e.g. 9. the same idea does still work because p is necessarily greater than 2, so both p and 2p appear in (n - 1)! - which is the same reason 4 /doesn't/ work
9 is not prime
@@zeravam ...yes, it's the square of a prime
Lol, like a minute after he had explained that proof, it clicked for me that he missed that and I decided to scroll into the comments to find yours.
for k=l, m!/k! being whole means m>=k, not m>k. It turns out in both cases where he uses the fact it doesn't matter. The first was the k! l! < .. < k! l!, which was still proven. The other was for k=2, where m=1 is actually less than k.
One of the best olympiad question and solutions channels but just one thing at the end of this video , considering k = 2 makes that k!=2 not k!=1 that you wrote on ths right side ; but not such a big mistake because it gives that 2l!= 2 + l! + m! , so we have l! = 2 + m! That for l>=3 there is no solution because u can take left and right side congerate to each other module 6 but RHS will never be congerate to 0 module 6 so l is less than 3 and in that case we also have not any solutions .
From a high school student from iran who is in love with math 🙏🇮🇷
13:57 m does not have to be strictly bigger than k. It could be equal to k (and the proof still stays the same)
So much thanks from Indonesia 😇😇😇
7:30 This is also possible without Wilson's theorem.
Case m2k: m!>(2k)!>k!^2=2k!+m!, so 0>k!, which is a contradiction. (the only exception is m=1 and k=0, which isn't a solution)
Writing this as K!L!=K!(1 + L!/K!) + M! implies that L >= K and similar argument for K >= L, so K = L
oh I like this one. Seems a lot easier and quite intuitive.
@@angelmendez-rivera351 On second thought I'm not so sure. In fact I don't think it does.
@@angelmendez-rivera351 Because 1 + L! /K! then needs to be integer, etc...
@@angelmendez-rivera351 must have been sleeping
You forgot to address a case of Wilson's theorem, where if n = p^2 where p is an odd prime, then n divides p * 2p and both p and 2p are strictly between 1 and n.
When solving the case k=l, it might be easier to just take everything mod3.
If k
Thats the way i did it too! (I dont know wilson theorem yet. Still a student)
@@Goku_is_my_idol nice
I'm curious Michael why you chose to specialize in that area or branch or field of math..representation theory and vertex operator algebra and not any other?
exact same question came up in a British Mathematics Olympiad Paper!
The most famous board in the world :D
Mathematics are a way to dream... So thx Michael to keep us dreaming !
My experience is that Number Theory proofs are the longest.
Good
Please topology and more advanced differential geometry
Maybe it is trivial, but I don't see it: What about the case m=k if l>k? For then we would have l!=2+l!/m! = 2 + l*(l-1)*...*(m+1). Why doesn't have this a solution?
How can you say m!/l!
I think this is faster for the k 2, then m! =k! l! - k! - l! >= 6 l!-l!-l!=4 l!, so m > l, so k! = k! l! -l! -m! is a multiple of l!, which is absurd
15:05 why it can't be that k!/l! + m!/l! -> (k! + m!)/l! result in a integer?
I don't think your proof of wilson's theorem accounts for squares of primes, eg 9 cannot be decomposed into two distinct integers greater than 2.
This channel derseves more subscribers.
Didn't mindyourdecisions already cover this?
I don’t understand the entire Wilson’s theorem part. He says (n-1)! is identical to -1 mod n, but I don’t see how that can ever be right.
Diego Marra What is a multiplicative inverse? Apologies but I am a complete novice at group theory
I don't know a lot of Croatian , but does anyone else think that he looks like Rakitic
For a second I thought you just had to shout the letters
I don't understand, what's the multiplicative inverse Modula n?
Good question, I don’t get it too
Multiplicative inverse of "x" (mod n) , let's denote it "y", is a number with property x*y = 1 (mod n). This is my guess based on his explanation of Wilson's theorem.
For example, take mod 7. Inverse of zero is non existent, inverse of 1 is 1, inverse of 2 is 4 (because 2*4 =8 which is congruent to 1 mod 7), inverse of 3 is 5, and 6 is its own inverse. Same as in the video where he said for mod n, 1 and n-1 are their own inverses.
When examining whole numbers modulo some number n, the set colapses only to 1,2,3,...,(n-2),(n-1). Every number bigger than n is being represented modulo n by one of these integers 1,....,(n-1). There is a special rule when adding and multiplying these numbers so when adding/multiplying two numbers modulo n, you still remain in the same set modulo n. Knowing this, multiplying different numbers modulo n might result in these two numbers resulting 1 when multipliyed. That means that the first number is multiplicative inverse modulo n of the other and vice versa.
@@dariobarisic3502 thanks
@@3manthing I'd also add that if we deal with (mod p) where "p" is prime, than inverses are unique, at least for all n0), so there is "x" which gives z=1.
Drazen Adamovic is one of my professors, the world really is a tiny place
what if a=b?
let's go
13:37 "we know that one is a whole number" - do we? Prove it! :D
lol just use peano axioms
Very nice prob solving in this channel actually.......
Tho a lot of bashing involved
17:45 l>m doesn't always mean m divides l??
@@angelmendez-rivera351 He said that m divides l because l>m but its not always the case for example 5>2
@@angelmendez-rivera351 Ohh thanks a lot. I misunderstood it
What the hell is mod aha ?
You should make patreon
Ragusa Is beautiful
Didn't expect this. Wilson's theorem is overkill, you can solve this with basic arithmetic and using an even/odd parity argument.
Right did you just kind of plug and chug guessing starting with small integers?
You technically forgot to consider the case k=l=0, but that trivially yields no solutions.
EDIT: Misleading thumbnail.
It's been a long time since I took a math class but I'm pretty sure 0 isn't a positive integer. :P
@@vaxjoaberg9452 Oh sh!t. Misleading thumbnail.
@@thephysicistcuber175 unless he since changed the thumbnail, i dont see what's misleading about it. the set N conventionally does not include 0
@@nathanisbored uhm no? 0 is conventionally natural.
@@thephysicistcuber175 ok so i looked it up and apparently both conventions are commonly used. the way i learned it was
N = {1,2,3,...}
W = {0,1,2,3,...}
Z = {...,-3,-2,-1,0,1,2,3,...}
and if you want negatives only, i guess you would do:
Z- = {-1,-2,-3,...}
and Z+ would just be equal to N
it seems in some conventions, Z = W, which is even more confusing. But anyway, i think its safe to assume in the thumbnail (and most of his videos), he was using the convention that N = {1,2,3,...}
First
I was first
@@suryanshsharma2451 no, he actually WAS first, sadly
@@guntherklausen6891 idk why but your reply made me giggle