Only one person in the world solved this problem. (2023 Balkan MO P4)
HTML-код
- Опубликовано: 30 июн 2024
- Head to brilliant.org/PolyaMath/ for a free 30-day trial and 20% off the premium subscription!
______________________________________________________________________
Official Balkan MO 2023 Solution(s): bmo2023.tubitak.gov.tr/assets...
UK Team Leader Report - 2023 Balkan MO: www.imo-register.org.uk/2023-...
_______________________________________________________________________
PolyaMath Community Discord Server: Discord: / discord
Chapters:
0:00 Introduction
1:55 The Problem
4:07 A Related Simpler Problem
5:59 Solution - The "easy" part
7:20 Greedy Algorithms
8:55 Solution - The crux
16:55 Greedy Algorithms ... Again?
24:13 Conclusion (Sponsored by Brilliant)
_______________________________________________________________________
Music:
Music by Vincent Rubinetti
Download the music on Bandcamp:
vincerubinetti.bandcamp.com/a...
Stream the music on Spotify:
open.spotify.com/playlist/3zN...
There's Probably No Time by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 licence. creativecommons.org/licenses/...
Source: chriszabriskie.com/uvp/
Artist: chriszabriskie.com/
Undercover Vampire Policeman by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 licence. creativecommons.org/licenses/...
Source: chriszabriskie.com/uvp/
Artist: chriszabriskie.com/
Candlepower by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 licence. creativecommons.org/licenses/...
Source: chriszabriskie.com/divider/
Artist: chriszabriskie.com/
I’ve no problems in math in any placements: schools, universities, but I always been struggled at the olympiads. This questions wants some impossible thinking during short time, which requires that you knows these types of questions and know how they are solving, otherwise you’re just a genius, who can solve any sort of problems in few hours
That’s because they’re used to test the best young mathematicians in the world these problems aren’t meant to be easy and anyone who says they are is probably lying
@@ThoseInterestingStories i mean like the only hard problems are millennium problems and most of the time they do not even have a right answer let alone a proper solving technique known to current principles of mathematics
There are trainings for this type of problems
Math olympiads make no sense, they are the exact opposite of what math should be about
Fun fact:
The person who solved the problem entirely (got 10/10) is Romanian and he also got a max score in the IMO that year. Being Romanian too, I see this guy as the Romanian Jesus of Mathematics, you can show him any problem and he will solve it for.
Anyway, completely coincidentally, the author of the problem is also Romanian, and the original text used "n natural number" instead of "2023", but they changed it before the contest as it probably would have been an overkill.
I'm Romanian too and I completely agree lol
Currently at 7:08 and there is one more constraint on k. If k = 1, Alice can choose 1 or 2 for that one number, and Bob’s task is impossible. So 1 < k < 593
My thoughts after hearing the problem:
The logical limit would be bΔ = 2023Δ/2, where b = 2023 - k, giving k = 592 (rounded down)
If Alice takes the 592 largest numbers, Bob can take the rest (excluding numbers summing to 1916, to make it equal). If Alice takes the 593 largest numbers, the sum is greater than the sum of the remaining numbers, so Bob cannot make an equal sum.
Intuition says that there will always be plenty of small numbers for Bob to choose from to make the numbers equal, but I'll try to come up with a logical method:
Once Alice chooses her numbers, Bob chooses the remaining numbers from the largest down, until his sum exceeds Alice's sum. He then chooses one extra number, that is the negative of his excess (for example, if his chosen numbers go down to 61, and his sum is now 25 greater than Alice's sum, he adds the number -25 to his set, to even them out). He then reduces the smallest non-negative number to the next available number (e.g. 61 => 60), and then increases the negative number by the difference to keep it even. He then sends the new gap (now at 61 in the example) bubbling up his set, so he can increase the negative number into the positives, until it eventually meets the rest of his set (e.g. [-24, 60, 62, 63] => [-23, 60, 61, 63] => [-22, 60, 61, 62] => [-21, 59, 61, 62] etc).
In the case where Alice chooses the largest 592 numbers, there are ~60 legal spots for the floating number to end in. To prevent this method from working, Alice would have to have to occupy at least 60 of the first ~120 numbers (blocking spots where either the floating number or the bubble would want to be in each iteration). However, doing this would increase the number of Bob's unused numbers faster than she could block them (e.g. if she chooses the largest 591 numbers and then also 120, it would reduce the sum by ~1300, meaning Bob would only have to choose numbers down to ~80, so Alice would now have to block 80 of the first ~160 numbers).
Yes
Legend of the Problem 4
challenge: take a shot every time Mr Polyamath says the word greedy
,loi.hjjjjjjjjjjjjjjjjjjjjjjjko'p/;lko
Nice!
Loving the videos!
5:00 I solved this a different way: if there are more than 50 numbers in the subset, we know that they can't all be odd / can't all be even (since there are only 50 odds and 50 evens in the original set) - thus, there is at least one odd number and one even number, which we can add to get an odd number.
I feel like this is the natural way of doing it (I know I did). Also interestingly this is actually the same method. However, the lessons learned from the smaller problem stated in the video are from turning your proof into one of pairs and pigeonhole. But I wouldn’t have got the same “tooling” from your (and my own) explanation. Interesting how different interpretations lead to different progressions.
@@williamchurcher9645 for sure!
“you got a solution in a way we didn’t want so you lose points” is such bs 😭
they didn't lose points because of the way they solved it, the solution just didn't have enough details. see 17:23
Hi, I’m that guy who made a bunch of problems in the math problem channel in your discord server. Good vid
i love your videos
The way the problem is presented confused me at first since it didn’t say any k of the set just exactly k. Maybe it’s a standard that these problems are worst case scenarios but I assumed it was alice working to maximize k, in which case she would choose the smaller numbers over the larger.
Generally speaking, olympiad problems give you the absolute least amount of information to be 100% certain what the question is. If the question says "find the greatest integer k such that..." Then they do just mean the result holds at exactly k.
If they wanted it to hold for all values up to k they'd say "find the greatest k such that for all m ≤ k" the result holds.
Polyamath posted, hence I stop everything I am doing
I'll figure it out one day
0:15 excuse me sir, Hungary is not a Balkan country (on paper)
i love this video
Awesome video! Here is a nice question for the meticulous viewers: where does the proof fail for k=593?
[Spoiler]
16:20
God these are good
Nuts that you already got a sponsor lol
At 20:23 you say we have 2 edge cases with bi=1 or bi=2, but doesn't bi/2-2 imply another 2 edge cases in bi=3 and bi=4 ?
What do you use to make your videos, its very similar to veritasiums style
I would say it's very similar to 3blue1brown's style and that polyamath probably uses manim, 3b1b's video making python library
I actually don't use manim, I just use the Computer Modern font (which is standard). I use a mix of davinci resolve (in the fusion page) and after effects.
@@Polyamathematics oh, that's cool! you're able to get some very beautiful results with that. I associate with manim-produced videos even more because of the music :) great work!
Yes some of the music is used by too 3blue1brown!
To my own surprise I actually solved this one. So, what I did is in order for Bob to ALWAYS be able to add numbers to the be the same is Alice, his total of his selection must amount to greater than or equal to Alice's. In order for Alice to maximize her total using k numbers, she chooses the k largest numbers in that set. So basically, the maximum value for k arises when the sum of the last k numbers in a set of successive integers from 1 to n+k is less than the sum of the first n integers. We can set up an inequality where n(n+1)/2>((n+k)(n+k+1)-n(n+1))/2 and using our knowledge that k is equal to 2023-n, solve for n and round up using the quadratic formula. By doing this we get n is equal to 1431 and therefore k is 592 since k = 2023-n. With this you can generalize for any set of successive integers.
Edit: Just saw you covered this solution after skipping straight to the answer and that I did this for no reason :(
This doesn't prove yet that an actual sum exists, you only know that there doesn't exist counter example that sums up to impossible value
@@madghostek3026 well in a list of integers, if you have a set of consecutive integers which sums to be greater than another set of consecutive integers, you can subtract enough numbers needed from the larger set until you get equality with the smaller set. The maximum sum of any chosen integers in the first 1431 consecutive integers ranges from 1 to 1431(1432)/2. This is also the range of numbers we can subtract from the first 1431 numbers to get the next 592. Idk exactly how to rigorously prove this as I never do competition math but this was my loose justification.
@@instinx9154 Yeah this is basically the thing everybody struggled with, it's easy to show an upper bound for k by asking "where to split 1,2,...n so that lower half sums up to something more than higher half". But now we don't really know if you can actually pick out numbers in a way to make the sums equal, which is the problem they are asking about. Notice that Alice doesn't need to pick only the largest numbers, let's say she picks 2023, 2022, 2021 and 1. Can you always manage your way without the 1?
@@madghostek3026 oh I gotcha, considering all those edge-cases is what makes it difficult. I just solved it assuming I didn’t have to prove anything lol.
uhhhh i don't get it, why we're taking pairs of numbers and why k=51... i feel bad :C
Not sure what it is yet, but can't be more than 592. Otherwise Alice would pick the highest numbers and Bob would not be able to get a sum of equal size.
Lol, I got the 1 mark!
a pair of sum b, and a pairs of sum 2024.
Is it just me or is this the wrong answer. If k=1 and Alice colours just the number one then Bob can’t solve it. So the largest k is should be 0. This is a weird edge case but I can’t see why this shouldn’t be a solution. However I really enjoyed the video and the problem
The result isn't true for all integers up to 592, it's only true specifically at k = 592.
@@TheArizusok I see. Thank you!
4:51 Here's my proof: There are only 50 even and 50 odd numbers in the set, so there are an even number and an odd number in the subset, and their sum is odd
For me (an autist), it's easier, although it uses a fact that some people may not know (the oddity of a sum)
k=1011
alice colours 1-1011 red (1011)
bob colours 1012-2022 blue (1011)
it says some so there can be uncoloured numbers so 2023 remains as the only uncoloured one
1011=1011
proof: if k>1011 then
alice colours 1-1012 red (1012)
bob colours 1013-2023 blue (1011)
1012>1011
it says the sum of the coloured numbers must be equal, not the number of coloured numbers
Wouldnt you just sum all of the numbers and divide by 2 to find the maximum sum?
0.5(2023)^2 +0.5(2023) = 2047276
Work backwards to find how many numbers are needed to surpass 1023638 -----> bob needs 1431/2023 numbers, so K is 592. It is OBVIOUS there will always exist a number you can leave out to obtain the required sum. I think that is what students wrote but the graders had a stick up their ass
By this logic if 2023 was replaced by say 5
Then we're colouring numbers in the set {1,2,3,4,5}. This sums to 15 so 4+5 > 15/2 so here k=1.
Not only is it not "obvious" that Bob has a strategy, but it's straight up wrong
Edit: failed at reading comprehension, see replies
Counter example: Alice chooses the first 1428 integers, they will sum up to 1020306. then if Bob chooses the remaining integers they add up to 1026970. However Bob can remove 1664, 1665, 1667, and 1668 from his choices, making his sum 1020306 - same as Alice's. So k=592 is wrong
The problem is to find the largest interger k such that for *any* choice made by Alice of k numbers, Bob can choose some other numbers with the same sum.
What your counter example misses is that, although you provided *one* example where Alice chooses 1428 numbers and Bob is able to choose numbers accordingly, it's not true that Bob could do that for *all* choices of 1428 numbers that Alice could have made (easy to see that if Alice had chosen the last 1428 numbers that would be impossible).
@@samuelleite7488 Thank you, that's what I've been missing. I've re-read the problem statement many times and I still wouldn't read it as "for any choice of k integers", guess I'm bad at English
@@czarelius no problem, statements can be tricky. In this one, I guess the key to understand it is the word " *whenever* Alice colours exactly k numbers...". That would mean you have to account for any possible choice of k numbers.
@6:27 concerning the expression k² - 4027k + 2023×1012 ; is 4027 a typo? i expect 4047 = (2n+1) for n=2023
using the notation, for any a,b, n el Nat :
[ a ; b ] := { x el Nat | a