Видео

Having just seen the problem statement, here's my approach: - First I observed that you can colour 4n-1 cells red by colouring r1c12, r2c23, r3c34, and so on. Also, this appears to be maximal: adding any one more red cell allows us to form an orthogonal cycle through the red cells, and colouring the corners of the cycle blue must then colour an even number of cells blue on each row and column. - Thinking more about that cycle observation, it doesn't matter where we enter each row or column, so we can rephrase the problem as: we have a bipartite graph with 2n nodes on each side (representing the rows and columns). How many edges can we add to the graph (red cells) such that the graph remains acyclic? - It's easy to see that an acyclic undirected graph with k vertices has at most k-1 edges, so my original 4n-1 answer is indeed the best you can do.

Idk the math was cool and all, but still don't see why this theorem is fundamental to arithmetic. What does fundamental even mean in math

So wait, the answer is not that this is not possible, just that you have to deal with partly imaginary side lengths 😅 That would be interesting to represent visually 😂

If Odette can get ahold of some blue color, then she can paint the entire square red except leave the very last column empty and then just put an odd number of blue squares in the last row.

My guess is 11, trying to be odette and avoid making “rectangles” like the one at 2:10 I’m expecting to be wrong but I’m excited to find out! Edit: Sorry I was looking at the 6x6 when I paused, general idea n + n - 1 ok back to watching

This is a great problem and some interesting solutions, but you jump from one idea to another so quickly and oftentimes briefly mention relevant information or use so much previously defined variables without reminding the viewer what they were, that closer to the end of the video it became unwatchable.

20:47 where the hell does that implication come from?!

14:11 what allows us to (or why do we) replace alpha with alpha-dash?

0:30 I legit thought "this video looks like it's gonna start out with 'this video is sponsored by Brilliant!' " It's not a bad thing, it means Brilliant knows their audience

HOW ARE U DOING THIS AT AGE 17 😭😭😭😭, i cant even find time to do what I want with my high school classes at age 16, with less then a hour of distractions with 8 hours of work time. ?????

"Odette hates even numbers but enjoys painting, so she paints some of the squares of the grid." *paints 8 squares including even indices*

These unnaturals don't even have addition. Take the alien world where numbers wrap around after 6. 1 and 5 are the units. 4 is prime (multiples of 4 are 0, 2, and 4). But it's also reducible, being 2 x 2. The irreducibles are non-existant in this world.

Rectangular 4 × 4 [area: 4×4 = 16squn, perimeter: 4+4+4+4 = 16un]

I know a lot of discreet mathematic problems use framing devices, but in this case, framing the nodes as criminals just seem odd to me. the art galley guard problem has a better framing.

Incredibly upsetting that the nodes of airports at 6:36 are roughly geographically accurate, except STN and LTN should be swapped

why are these criminals that are watching each other? it could just as well be plumbers or left-handers

5:11 my guess at this point as to the reasoning behind 4n (if it’s correct) is related to the perimeter of a square with side length n. If you were to cut a 1x1 square chunk out of the corner of this square, creating an additional 2 sides and reducing the area of the shape, you’ll notice that the perimeter actually doesn’t change, as you can just move the indented sides back outwards and they reconnect to form the square again. This will only fail in a certain circumstance, but I’ll come back to it. The parallel here would be that the whole board is the square, and any removed chunks are the red squares. Thinking about it in this way reveals the problem. What if you remove 1x1 squares ALL THE WAY along two sides of the perimeter of the square? Obviously then you can’t just move all the sides out and reconnect them to have a larger square, the remaining line segments on the border of the resulting square are physically shorter, and this happens when you remove 2n-1 or more squares, but the perimeter decreases by TWO if you take squares off ALL the sides, which adds up to 4(n-1) squares

not only removing elements from natural number set but adding some new ones could also hinder the uniqueness of factorization...it seem like set of natural number is the chosen 1 :)

My proof: for that to happend either one row or one collumn has to have less than 2 cells. All the others have 2 because it's maximum number, that that one has 1 for the same reason. Just like that, you know the max value is 4k-1. Really, tha heck

Great video. (1) Revealing that the matrix can be viewed as an adjacency graph means that for k = 4n-1, Odette's winning strategies are exactly the trees. (2) Can have any rectangle sides m & n, not just 2n & 2n. (3) I was a little confused at the beginning. The words "game" and "strategy" normally suggest some alternation of play, but in fact Odette just picks a bunch of squares once. She only has one move. Her move *is* her entire strategy, so we don't get much mileage from the game metaphor, imho. But again it's great - thanks so much

maybe Im wrong but the lemma you proved isnt relevant for this case. the lemma refers to any graph and hence dictates that the upper limit is 4n^2, much more than the goal of 4n

My approach was a bit more straightforward: if we have n*m grid, assume we have a maximal red coloring which achieves the goal, then it still works after row switching and column switching. we will choose one red cell arbitrarily and move it to the upper left corner by row and column switching. then, we can find another cell in the same row as it and move it by column switching to be adjacent (if theres no such, we will try finding one at the same column, if none as well, we will move one to be diagonally adjacent to it), we will keep doing it to the next one, making a string of adjacent cells. next we discover these facts: 1. no cell can be found above the chain or the left of it, or else we could have walked the chain from corner to corner, jumped to that cell and jumped back to where we started, maintaining a loop of even number of cells in every row and column. 2. the longest chain possible goes from the upper left corner to the lower right one, having a length of n+m-1. QED

Can you plzz upload Combinatorics problems from Russian Olympiads? They always have some really nice and elegant combi problems!

Hi! I recently discovered your channel through a comment from a editing video tutorial (something with 3d glow lines) and even tho i have no tangents with the content you make, i still find it incredibly interesting! What i m very intrigued by is your editing: it is high quality, and on point all throughout the video!! How do you edit like this? And also, how do you find the ideas to make this content, to then edit the videos? Thanks for being such awesome content creator aaannd you ll very soon sky-rocket in popularity!

Evan and Odette seem like great friends

Thank You

0:28 odd

why is the side lenght even(2n), it seem to me that this would work also for grids with odd side lenght with the general limit of 2L-1 wherw L is the side lenght, for the same reasons

A game about coloring squares on a grid? Isnt that go?

hey man i haven't watched the video yet, but i have to say, that thumbnail is beautiful. sleek and nicely colored. good job

So for k at least 4n, Evan can always win, but can Odette always win for k at most 4n-1?

Unfortunately there's a horrible mistake in this video: You got Luton and Stansted the wrong way round. 😲

As is being pointed out by some comments this very easily generalises to an n x n or even m x n grid. The exact same argument shows that k = m + n - 1 is maximal since k = m + n leads to a cycle. (Not sure how I never realised this but this has no effect on the actual argument).

Why not a (more general) m x n grid?

Why did you pick 2n for the dimensions of the grid? n doesn't seem represent anything on its own, could you not have demonstrated this on an n by n grid instead?

There's a mobile game called 0hh1 which has a similar concept. So, for me, the video seemed logical.

Why does this person reminds be of the blob guy

I got a different solution. For a grid of 2n by 2n, Odette 4n^2-2n+1 squares. This is done by colouring every square red in every single column except for one, and then colouring a single square red in the last column. Evan can obviously colour every single row so it has a non-zero, even number of blues, but as there is only a single red in the last column, this cannot be achieved

Fun observation which is that the first thought of trying to prove that Evan can always make a rectangle is actually not too far off. Since what he is actually trying to do is find some combination of rectangles that he can add, with the caveat being that placing a corner atop another corner turns it red again. Adding a rectangle in this way always preserves the “parity” of blue squares on each row and column so it will always remain even. Not sure how this would relate to your proof but I noticed it and thought it was interesting.

These are really high quality. Please don't stop!

Just paint 0 squares in each row and column since 0 is even

oh damn that shift in perspective was really cool wow

I love puzzles about colo(u)ring squares on grids!!! :))))

I think the difference between math explanation videos and textbooks goes unappreciated. Even things as subtle as coloring Odette's name red and Evan's blue can make the problem much easier to understand.

5:13 an easy counter-example to Evan always needing to find a rectangle is one you gave earlier: a diagonal staircase plus one square. No rectangle present, but Evan can win.

Only 900 views?!?!?!

I hadn’t seen this trick before, representing a binary matrix as a graph whose rows and columns are vertices and whose edges are the true entries - and it’s immediately relevant to a projecteuler problem I’m working on :)

nice problem and great video

i'd like to know why this shift in prespective possible . the best i can think of is converting the table to an andjacency matrix.