IMO 2024 Problem 5 - most *TROLL* problem in IMO history?
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- #mathematics #olympiad #math
International Mathematical Olympiad (IMO) 2024 Day 2
Solutions and discussion of problem 5
65th International Mathematical Olympiad Bath UK
Problem 5 - Combinatorics
There is an easier solution:
Spend 1 attempt finding the monster on the first row. If it is not at the end, then you can guarantee to sneak under it in at most 2 more attempts.
If it is at the end, go to the opposite end of the second row, and explore up to 2 squares before the monster. If you find another monster, then you can sneak under the first row monster, otherwise do something similar for the third row etc, creating a kind of staircase pattern. If no monsters are found, then at the end, the staircase will reach the bottom row.
Oh you are right! I can just apply the logic of my second half of the board from the start! 😅 It was closer in logic for me to go down the double-staircases first
That was what I was saying when I said a alternate solution. I couldn't frame my answer, thanks for writing😄
@@saraswatasadhu5611 Great job both on coming up with the easier solution!
@@polyquadratus5304 yeah, what I came up after trying to work around the staircase (literally) for 20 minutes though
Sorry, but could you elaborate more about the part of doing the same thing to the third row?
I initially thought we could do binary search and so that way we get log(2023) base 2 = 11 but realised it was wrong. Nice solution!
It was a good guess, it did cross my mind at some point as well
had the same intuition, but the solution presented is super clean :D
I thought that too seems like we are spoiled with university 😅
@@dovletovlyagulyyev4667 I also thought like that at some moment. But unf. after realising that answer is not related to log, I tried to prove that answer is related to N\2, which was a wrong idea, so unf. I end up with not solving it. Answer=7 in my opinion
There's actually a solution that is log_2(n), and I had thought it's the best one, before I checked the answer. The idea is that even in the staircase pattern worst case scenario there will be a column without a monster, you're trying to find this column by initially finding the leftmost and rightmost column monsters, then the mid one, then you compare the difference between rows and take the two that are closer, so if their monsters are at rows 100, 300, 350 respectively, then you take mid and right cols. Then you take the middle between them and recursively continue. This will at least halve the distance difference each time. When the row distance reaches 1, the columns will be more than 1 column apart, so you can travel down the column with the furthest down monster until right before it, then travel sideways until you reach the side of the other column's monster, then travel down once, then travel siddeways once to end up below the monster, then go straight down.
If this appears as P4, everyone solves it.
Psychological trolling!
maybe because I wasted time proving log2 recursion works
This also happened in my countries junior olympiad. I left the 5th problem (there were 5 in one day) not knowing that they made it maybe on purpose the easiest, so I lost all my qualifying chances for the Jbmo
@@krstev29 Never believe the rated question difficulty - UNLESS you are a completely average contestant.
If you are well prepared contestant, there will be some topics for which you will be exceptionally well prepared - any question on those topics, regardless of their number and estimated difficulty, are in your wheelhouse.
For an example, look up question A5 of the 1974 Putnam. I knew the answer almost before I had finished reading the question, as I was exceptionally well prepared on the conic sections and projective geometry. Proving it took some time; but most contestants found that question difficult.
Some consider this a troll problem because the answer is wayyy smaller than what some contestants may expect. What do you think of this problem? Regardless of your views, I think we can all agree that it's a pretty fun problem!
I saw the problem and immediately thought 3 would be the answer. Seems like a normal ish IMO problem
i can't believe why south korea team score is only 7 in this problem.
I personally thought it was very easy for a P5, would make more sense as P1 or P4 but it's probably to psych out the participants idk.
I think this is a very reasonable problem, and it is very natural to think that the answer will be quite small, which turns out to be the case. It would only be a troll problem if the solution turns out very different from your expectations. Regarding the 2010 problem 5, there one might say that the end result seems so outrageously large, they would not ask it that way if there would be a "normal" upper bound on the number of coins one can get in the last box. So the answer must be yes, and one needs to find a way to get it.
Of course, everyone may box him- or herself into a wrong answer, and it is very difficult to get out of that, especially during the competition.
That thumbnail is perfect
As someone who participated in some of the hong kong TST this year, I can say that I can definitely see some of our trainers trolling us, but I definitely didnt see this problem being selected for P5 xdd
No such thing as too little trolling :p
Well, they probably expected it as a P1 or P4
Congrats for 100th video
Thank you! I didn't even realised it!
In the motivation part you read my thinking process as a book 😭 (until 5:42)
Fun problem. I enjoyed solving it, with the single staircase. Thank you.
However, here's my two cents: I placed consistently in the top 10% nationally in both high school contests and then Putnam. But "top 10%, barely" results also mean I am nowhere near Olympiad level either now or when I was younger. If I can solve this problem in about 15 minutes, as I did, the question is not whether this problem is too hard for Olympiad; but rather whether it is too easy. Especially for a Problem 5, I would expect the difficulty to be such as to require me to spend at least 60 minutes to solve.
Do stay till the end of the video to hear some cool stories about this problem. I hope you enjoyed the little bit of story-telling!
Is Question 6 cooked?
@@saraswatasadhu5611 Yes! It will be up tomorrow! It will be good
@@dedekindcuts3589 I have got one idea to procced but don't know if it's correct. Too excited to check lol...
Nice solution! The official solution involves walking in a staircase pattern instead, but seems like it is a more ingenious construction compared to the one shown in the video, does anyone know what's the motivation behind it?
Also, is there a solution where you can guarantee 3 attempts without exploring the second row much? Seems like knowing where the uppermost monster is a must.
I show the motivation behind that idea on my channel 😉
After seeing polyquadratus' comment which I pinned, I realised that the staircase pattern is basically the same as the second half of my solution (which can be applied from the beginning). I agree it is not as easy to land on that solution directly...!
This was pretty similar to the last year's P5!
i don't understand the win in 3
how this could work for the case like this:
1,2,3,4,5,6,7,8
1⬇🟢🟢🟢🟢🟢⬇
2❌🟢🟢🟢🟢🟢⬇
3⬜❌🟢🟢🟢🟢🟢
4⬜⬜⬜⬜⬜⬜❌
5⬜⬜⬜⬜⬜❌⬜
…
green is "known safe to explore" fields after 2 failed tries of checking the sides: (1,2) and (8,3).
We still can be catched by the monster from the row 4, wherever we try to explore next.
For your example, at the first attempt, the snail meets monster at (1,2). At the second attempt, she manages to go to the end of row 2. If monster is at (8,3), she can take the third attempt to move from (1,1) to (2,1) to (2,2) to (2,3) to (1,3) to (1,4) and …to (1,n) Remembering that each column/row has at most 1 monster. If monster is not at (8,3) she continues to check monster at (8,4) and apply the same strategy.
there's no need to burn the second attempt on the monster at (3,2). Explore up until (3,3). If still green, you already know the monster is in (3,2). Instead, go back to the far right and try (4,8). If you get a monster, then you have a direct path to get to column 1 on your 3rd attempt. If no monster, keep going left on row 4 until (4,4). If there's a monster at any point up until (4,4), you similarly have a path to column 1 for your 3rd attempt. If not, you know now that the monster must be in (4,3). Don't burn the attempt, instead you go back to the far right and try (5,8) etc.
brilliant question
I love ur vids and effort-keep up the work❤
Thank you so much!
I am curious if it's really the placement of the problem or the overestimation of difficulty that caused it to be poorly solved, or are there other factors?
It's possible. If this were placed as P4, more people might try to find an O(1) solution. Knowing the solution is a small constant makes the problem quite a bit simpler. But actually I think if I give someone this problem by itself without context, it does match the difficulty level of other P5
@@dedekindcuts3589 when you look at the statistics, the average points scored is 2.2/7 among contestant which is a typical p5 not too low not high
@@dedekindcuts3589 also the top 5 countries average low in P5 when compared to what they normally score in P5, they got an average similar to top 30 countries which is funny
love from INDIA, GREAT WORK.
This is a beautiful problem, in my opinion! ❤
Spent an hour or two on it, but finally cracked it
Great job!
my strategy:
wherever you start (unless it's the first or last column, then move to another one) go down until you find a monster
1. if you don't you managed in one try.
2. if you do then next attempt rego down the same column and arrived at the row before the monster go to the right and down,
3. if you don't find a monster, go to point 5.
4. if you do find a monster, you are guaranteed that there's no monster on the cell two on the left of where you are then on the third attempt you can move to the left and then down instead of right and shouldn't find a monster
5. go just under the monster that you first found by going one right (or left if you skipped point 4.) and you are guaranteed not to find any other monster in that column, so you will finish
This unfortunately doesn't work. You've forgotten to consider the situation where you hit a mine (say, at coordinate (100,100)), and there are two other mines that create a diagonal line of three (either at both (99,99) and (101,101), or at both (99,101) and (101,99). So you're not sure whether you're allowed to go right or not, and you're not sure whether you're allowed to go down or not, and you can't afford to be unsure about two things.
@@veno2195 you're right, forget I said anything, I'm stupid
Alright i know i am little annoying but can you explain the hungry goat problem btw love your channel ioqm aspirant here.
Thanks for your support! It's ok to request as long as you understand that I won't be able to cover most of them
I am also a ioqm aspirant best of luck for your exam 👍 I covered only number theory😢
Turbo the Snail should have been replaced with a troll 😁
idk, this is very easy problem, but at the same time its P5!?
ive solved p1,p2,p4,p5 and 1 point for p3 -> gold medal
what i can say about problem? its beautiful.😊
It's a fun problem. I think it's easier than usual P5 if you already expect some troll or someone tell you the answer is O(1). It's a lot harder going in fresh without any prior information. The stats show that this got lower average and #7 than P2.
So 28 poinst is silver and 29 is gold, this 1 point is a game-changer
@@timanishchuk Yes, I knew that 28 points was clearly not enough for gold, because obviously many people scored 28 points and therefore I tried to get 1 point :>
Bravo 👏🏻. What do you think of this year problems? Also it must feel really good to have a gold on the IMO, congrats.
Can you tell me how much time you spent on every problem?
@@krstev29Honestly, I didn’t like the IMO 2024 problems, I was preparing for the geometry problems, and also P5, it’s something strange to put a 7th grade problem on the IMO.
P1 -> 20-30 min
P2 -> 1h30 min
P3 -> the rest of the time
P4 -> 5 min (easy)
P5 -> 20 min (also easy)
the rest of the time I tried to solve P6 but it didn’t work XD
I have an alternate idea for this. Can you please check...
easiest P5 in modern IMO history
True
Numsolves and other stats say otherwise
it wasn't easy, contestants averaged 2.2/7 which is about average or little bit below average for P5
About half of the contestants in the top 5 countries didn't solve it. But many contestants from the top 30 did solve it, so it made all contestants have a more equal chance of solving it
2022 C7 STRIKES AGAIN
Combi always strikes
@@dedekindcuts3589 nah the joke is that 2022 C7 also had the same troll answer of s = 3 💀💀💀
@@whitemountain4851 celestia 7?
no but i feel like this one is actually not hard to solve if you get your head over the fact that "it's p5 surely it's hard" and play around with the problem but c7 is actually like a legitimately hard problem to show optimality
>n=1, impossible
>n=2, hell no, wtf
>CP people calling the problem "trivial enough to solve in 10s"
>came up with the n=3 solution for the trivial case (the monster in row 2 is not in col 1/2023) OR there exist 2 consecutive easily determinable row where the distance between the 2 monsters is at least 2
>double checks, finds the construction messy with the "stair" case, stuck for 15 minutes
>realizes that one can just check from the other side until a "trivial" case is found OR determine that it is still a staircase OR it is the 2023-rd row already, at which point the solution is trivial
TBH, regardless of how easy this problem actually was, it is, indeed, VERY troll:
- One can, and will probably end up stuck with trying to find a valid construction for either N=2022, N = 1011 or N = 11, which would be.....very haha funny
- on the Vietnamese Olympiad in Informatics community (where I heard about this problem being easy), it seems like it is VERY EASY to miss the staircase, even after one have correctly guessed that N=3. Still, having looked at the problem as if it was a Codeforces Div2D/E, the "algorithm" for proving the solution comes quite naturally. Still a good bait though
If this is presented in codeforces Div 2D/E, it will trick many people to think of the binary search solution first :p also troll
@@dedekindcuts3589 tbh I wouldn't say that it'd trick many people into thinking about binary search (unlike last year's P5) as there's......no real way to binsearch? Like....there's literally no point in binary searching the amount of rows between 2...2023 that you must clear to find a valid path (at that point, a probabilistic approach looks reasonable, but then you'll find the construction for n=3 in a minute anyways. Still a fun problem to "code" though - the way to prove is literally just describing the algorithm used if this was a Div2D interactive in text form, so there's that
~~it's only a matter of time until someone inevitably stole this thing for the local ICPC contest lmao~~
2:27 2:27
Are u Lim Jeck?
No I'm not, Lim Jeck is way stronger than me
codeforces ahh problem
Many combi problems have CP flavour and vice versa!
why
It wasn’t this problem
Just a comment on the video content quality. Your way of speaking is too lengthy. It might be helpful to edit out some unnecessary parts or write a script and shorten it with ChatGPT.
i don't understand the win in 3
how this could work for the case like this:
1,2,3,4,5,6,7,8
1⬇🟢🟢🟢🟢🟢⬇
2❌🟢🟢🟢🟢🟢⬇
3⬜❌🟢🟢🟢🟢🟢
4⬜⬜⬜⬜⬜⬜❌
5⬜⬜⬜⬜⬜❌⬜
…
green is "known safe to explore" fields after 2 failed tries of checking the sides: (1,2) and (8,3).
We still can be catched by the monster from the row 4, wherever we try to explore next.
The moment you encounter the monster on row 4 on the other end, you immediately know, there are no more monsters on row 4.
So, you can just take the adjacent column down onto row 4, move left to the start and just go down. (you're already encountered the monster on column 1)