IMO 2024 Problem 3 - *MONSTER* combinatorics - how many will get 7?
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- #mathematics #olympiad #math
International Mathematical Olympiad (IMO) 2024 Day 1
Solutions and discussion of problem 3
65th International Mathematical Olympiad Bath UK
Problem 3 - Combinatorics
![[UNCUT] "เสรีพิศุทธ์" แฉยับ! งัดหลักฐานใหม่ชั้น 14 ได้นอนคุกสมใจแน่!! I คนดังนั่งเคลียร์ I 2 ก.ย.67](http://i.ytimg.com/vi/O1SSg4p9Izs/mqdefault.jpg)
![🎤 จับฉลากร้องเพลง x P’ #XXSIVK [EP.1] (2/2) เพื่อนจับได้คำไหน..ต้องร้องคำนั้น เริ่ม! 💓🎶 #MXFRUIT](http://i.ytimg.com/vi/1bJvMJXmeS4/mqdefault.jpg)
Wow, what a great problem and solution. Even understanding the solution is huge for me haha
cant wait for day 2
Great job! I agree the solution is not easy to understand!
@dedekindcuts3589 thank you for making these videos they're so useful and interesting
Beautiful solution. I was confused as to why claim 4 would be useful, but the usage of finitely many frontier shapes is just beautiful.
Claim 4 is needed to conclude that the number of possible frontier shapes is finite!
using the histogram for bookkeeping is pretty elegant
This year's IMO would have been perfect for me lol(as a person who hates geo but is decent at algebra and nt) unfortunately I was one year too young to qualify for the national IMO team
Hopefully next year's problem set is favourable for you too!
Same bro same
@@MariusGjikaare you the albanian guy who won silver in JBMO?
@@dijarademi133yes that’s me
@@dijarademi133were you in jbmo?
you have no idea how underrated you are.
thank you!
Combinatorics for P3 or P6 is always tough! What do you think of this problem and the chances of people getting a full 7 on it?
100% people get 7 on this. Day 1 P1 and P2 are lightwork for trained students and they definitely have the time to solve P3.
True, I feel that the stronger students will have more time to tackle P3 this year. However, P3 is a pain to write up during contest and I suspect many may accidentally claimed certain steps as intuitively obvious and lose points. There will certainly be people who end up getting 7 though!
@@dedekindcuts3589 turns out marking scheme is also quite rough. Only 2 partials for getting to the part with 1,2,…,c repeat infinitely many times and alternating between large/small Numbers.
@@quite_unknown_1 Wow! That is real rough!
I managed to figure this one out on my own! It took way more than the 4.5 competition hours but i got all the way to proving claim 3 within competition time (i am not a competitor, i do them for fun but measure myself) and then i got stuck looking for permutation based solutions. After sleeping though i realised permutations are way stricter than the claim of periodicity and then i proved claim 4 (along with a more rigorous proof of "frontier shapes" by using induction to show that any translation on the small number column with the same starter results in the same tail afterwards).
Great work, it's a good start
love your channel, thank you! waiting for the others
Glad you like them!
will you upload the other problems this week?
I havent attempted P6 yet, minimally P4 and P5 will be up this week!
great 非常感谢您的频道和快速解决问题的能力 🙏
gosh darn, you solved all 3 problems on the IMO. Out of curiosity, were you an IMO participant or a Putnam HM in the past?
Yes, both IMO participant and Putnam HM before (but only once!) That said, I have unlimited time and no contest pressure, which makes a gigantic difference. I spent many, many hours on this P3.
WE GOT THE EXACT SAME SOLUTION TO P3! I also drew this grid and got the same bound. I didn’t take the contest though, I just mocked it at home and got 777.
Amazing! That's real impressive!
Waiting for your solution to P5!!
Shefs of Problem Solving uploaded a solution to that problem. Also a cool competitive math channel 😉
really cool! I'd have gold if i had got full marks on this one (22-> 29)
Good job nonetheless. P.S. getting full marks on this one is quite tough, I think those who do should deserve gold!
I wonder about something since i can't seem to come up with counter examples: is there any frontier shape/initial set up that will yield a period that is not just a single permutation of the set {1,..,c}?
It turns out that the period is always c and the repeated pattern is always a permutation of {1,...,c}
extremely low solve rate on this one, surprised i actually got it
Ur thinking level is soo high how can u think to solve these things
It takes practice! There are stronger students than me!
Amazing!!! ...as a side simpler problem, is there a way to prove that for N=1, when a₁ is odd, a₂a₄a₆a₈... is the only one eventually periodic and when is even then a₁a₃a₅a₇a₉... is the only one eventually periodic?
When N=1, c=a_1, and the square of side c in the bottom left corner is filled first. The (c^2 + 1)st entry is c and is the first entry in the periodic sequence. So the eventually periodic sequence is the even (odd) one when a_1=c is odd (even)
24:32 moment for Tetris
Insane solution, makes a lot of sense why AlphaProof was unable to solve this problem. It makes you think whether any type of machine could solve this kind of problems at all.
Not yet... But probably at some point in the future.
give it 2-3 years
it is a bit confusing as sometimes the i in term h_t(i) means the index of the sequence, and sometimes it means to be the number a_i in the sequence itself (like when you refer to h_t(M)).
h_t(i) is defined as height of i at timestamp t. So i was never used to mean the index of the sequence
@@dedekindcuts3589 Then the reduction to j = i+1 at 10:46 is a bit problematic, as it assumes that the element next to i is i+1 which is only true if the height of i at that time is exactly i+1. It could be that the height of i at sometime t > M is already greater than i+1 and thus this assumption does not hold. So you cannot repeatedly apply this argument to get to any j > i.
There is no assumption made that the element next to i in the sequence is i+1. The proof of that section is as follows. Consider an appearance of i+1, and let the number before immediately before that be z. Then z has i+1 appearance, which means it had i appearances earlier, and when that happened, the number i appears in the sequence. So each i+1 can be mapped injectively to an appearance of i.
@@dedekindcuts3589 I just look at it again and see it now. I got a wrong impression from the picture that i appears just right before i+1. Thank you for the clarification.
Np!
While experimenting with these sequences it seems that the period on the small
numbers always happens to be precisely equal to c
Which is not a trivial consequence of the proof
And it adds (if its true of course) a interesting information on the behaviour of these sequence
Anyone could proove this ??????????
Well, I have only experimented by hand not with à computer
Hence only very simple exemples
Hence maybe m'y remark is false.....
Actually it is true. The solution report commented the following (k is the c in our proof): "the sequence of small numbers has period k. The repeating part of the sequence of small numbers is thus a permutation of the integers from 1 to k. It can be shown that every permutation of the integers from 1 to k is attainable" We can wait for the IMO webpage to publish the solutions
Imo 2011 problem 2 day one please 🙏 🙂
you can find it on 3Blue1Brown's channel
Yup, 3blue1brown already has a beautiful video on it!
I love you❤
Do you think it's good to learn on your own or to have someone teach you to advance faster?
Having someone to guide you can help a lot, but you will still need to complement that with self-learning!
そもそも問題文の意味がわかりません😭😭😭
English issues
If P3 is a monster then P5 is a harmless microscopic bacteria😂
The sarcasm is strong in this one 😂
Only people listening to audio could here you ask to listen to it, so it was kinda pointless
dedekind buts