Hopefully this works:

AnonymousBunny wrote: Hopefully this works: so it suffices to pick two numbers from each color such that the average of the numbers chosen is $(4n+1)/2$. We shall choose a subset of numbers such that the following is satisfied: $a$ is chosen if and only if $4n+1-a$ is chosen. This ensures that the average of the chosen numbers will be $(4n+1)/2$. How do you choose from the small example for $n=2$ And Red for $\{1,2,4,5\}$ and Blue for $\{3,6,7,8\}$

@mszew: Red: 1,2, Blue: 7,8

This seemed... easy?

The solution that is different from other ones posted (maybe I can't see the isomorphism?), sketch:

This problem is fairly similar to a problem I set in a Codeforces contest two weeks ago here. I hear some contestants were able to draw inspiration from it to solve this P3, so you're welcome Let's consider all the pairs of pebbles that have a total weight of $4n + 1$. There are exactly $2n$ such pairs. Consider a graph on $n$ vertices and add an edge between vertices $x$ and $y$ if some pair contains pebbles of those colors. We allow loops and multiple edges. Consider a connected component of the graph with $k$ vertices, then all vertices have degree $4$, so the component has $2k$ edges and admits a eulerian circuit. [asy][asy] unitsize(1cm); real v_rad = 0.3; void vertex(real x, real y, pen p, string s) { filldraw(circle((x, y), v_rad), p); label(s, (x, y)); } pen RED = rgb(1, 0.5, 0.5); pen BLUE = rgb(0.5, 0.5, 1); pen GREEN = rgb(0.5, 1, 0.5); pen epen = linewidth(1.5); vertex(1, 0, RED, "$1$"); vertex(2, 0, BLUE, "$2$"); vertex(3, 0, RED, "$3$"); vertex(4, 0, BLUE, "$4$"); vertex(5, 0, BLUE, "$5$"); vertex(6, 0, GREEN, "$6$"); vertex(7, 0, BLUE, "$7$"); vertex(8, 0, GREEN, "$8$"); vertex(9, 0, GREEN, "$9$"); vertex(10, 0, GREEN, "$10$"); vertex(11, 0, RED, "$11$"); vertex(12, 0, RED, "$12$"); pair redv = (6.5, -2); pair bluev = redv - 3*dir(60); pair greenv = redv - 3*dir(120); draw(redv .. redv + (0, 1.2) .. cycle, epen); draw(redv--bluev, epen+gray(0.5)); draw(bluev .. (bluev+greenv)/2 + (0, 0.5) .. greenv, epen); draw(bluev--greenv, epen); draw(bluev .. (bluev+greenv)/2 + (0, -0.5) .. greenv, epen+gray(0.5)); draw(greenv--redv, epen+gray(0.5)); filldraw(circle(redv, 0.5), RED); filldraw(circle(greenv, 0.5), GREEN); filldraw(circle(bluev, 0.5), BLUE); [/asy][/asy] Color the edges alternately black and white (possible since there's an even number of them), so every vertex has black degree $2$ and white degree $2$. Finally, repeat in every component, and send all pebbles in a white pair to one side, and all pebbles in a black pair to the other. Each side contains $n$ pairs of pebbles with sum of weights $4n + 1$, so they both have the same weight.

Probably similar to others?

Just a quick question. When are results coming out?

How about??? There are $4n$ pebbles of weights $1, 2, 3, \dots, 4n.$ Each pebble is coloured in one of $n$ colours and there are four pebbles of each colour. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied: The total weights of both piles have difference for each number $\{0,2,\cdots,4n\}$. Each pile contains two pebbles of each colour.

immediacyprinciple wrote: Wow this blogger is fast. https://how-did-i-get-here.com/20q3/ Looks like the same solution as previously posted. Bro, ngl this is a pretty cringey way to try to push your blog

Consider the bipartite graph (colours,pebbles). Identify each pair of pebbles whose weights sum up to 4n+1. Suppress every 2-vertex. Apply the simplest case of Petersen 2-factor theorem (the 4-regular graph case) on the obtained 4-regular pseudograph.

Similar to the other solutions:

I also did it the way in the solutions above which seems like the cleanest approach, but for the sake of trying to find another solution here's an attempt at something different.

Here is a solution that doesn't use eulerian circuit . As above we need to pick exactly $n$ of the pairs $(1,4n),(2,4n-1),(3,4n-2),...,(2n,2n+1)$. According to the colors ( $1,2,3,...$or $n$) of $(i,4n+1-i)$ draw an edge between these colors and construct a multigraph $G$ with $n$ vertices (veritces represent colors) that every vertex has degree $4$ (self-edges and multiple edges between two vertices are allowed, there are $2n$ edges in total). We need to paint each edge red or blue such that each vertex has an equal number of blue and red edges. (then we are done cause we picked exactly $n$ blue and $n$ red edges). Consider the maximal coloring of some of the edges complying to the above , suppose that not every edge is colored. If the subgraph, the uncolored edges form, has either of the following then we can get a larger coloring: An even cycle:

There are two odd cycles with uncolored edges that have a common vertex (not common edges )or there is a vertex $V_1$ in the first cycle and one $V_2$ in the second such that there is an alternating blue red path between them.

The subgraph of uncolored vertices has even degrees therefore is a union of some cycles. From the above we deduce that it should be the union of some disjoint odd cycles such that there is no alternating red blue path between any of them. Note that there is an even number of such odd cycles (a vertex with a self-edge is a $1-$cycle) because there is an equal number of red and blue edges , an even number of colored vertices and the total number of edges is $2n$ even. Call a vertex full if all $4$ of it's edges have been colored. Consider an odd uncolored cycle $c$ and the subgraph $A_c$ such that any edge or vertex can be reached through an alternating blue red path starting from $c$. $A_c$ should only contain the cycle $c$ and some full vertices . $A_c$ is connected in $G$

Above we showed that there cannot be a connected component in this graph with exactly one odd cycle therefore we arrived at a contradiction and conclude that a maximal coloring should contain all edges of $G$ and we are done.

mszew wrote: How about??? There are $4n$ pebbles of weights $1, 2, 3, \dots, 4n.$ Each pebble is coloured in one of $n$ colours and there are four pebbles of each colour. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied: The total weights of both piles have difference for each number $\{0,2,\cdots,4n\}$. Each pile contains two pebbles of each colour. bump! Another question: is there any different solution using induction?

I think that this is different solutions from all of the above. Outline We pair numbers k and 4n+1-k. Then arrange colours and start algorithm that will put rocks in the groups, starting from uppermost colour to the bottom one. Consider that we can't suitably divide rocks from the xth colour. I will construct algorithm that will enable us to do so for the xth colour too. Solution Let us arrange colours so that those having some pairs in it are going before the other colours. We firstly put all the pairs in the left group, and others from those colours in the right one. (If in some colour are two pairs, put one in left and one in right group). If we put some rock in one group, we also put its pair. Our algorithm is going that way, trying to find grouping, colour by colour. Consider moment when we can't group rocks from one colour, say red. Let us define graph on the rocks, (only on those that are from solved colours and the red one). Paired rocks are connected and also for every colour we randomly connect every rock with exactly one from the different group. We are considering paths starting from red, and because every rock from the solved colours is connecting with exactly two other rocks, our path can't have cycle and can end only in red or some unsolved colour. When we find suitable path, we will change the group of every rock in the pair, and in every solved colour there will remain 2 rocks in the first and 2 in the second group. We can start path from the rock of the red that is in the group with more than 1 rock from red (call that + group). If path ends in below (unsolved) colours we reduced difference by one and can procede with algorithm. If we finish in the red in the rock from + group, we reduce difference by 2. If we finish in the rock from - group that means that there is already 1 of - group. Only remaining case is when there are 3 rocks in +group and 1 rock in - group, and there is no path from any of +group rocks to the below colours. Consider some rock from solved colour (call it blue) that is connected with some below rocks. Let it be rock a, while rock d is in the same group and b and c are in different group. I claim that none of the blue rocks is connected with paths from 3 + group rocks. Consider path going through some of them. If it goes firstly from b or c, we can and than goes to d, we can change the edge and connect it with a instead, and path will finish in colours below. So path goes firstly through d, and then to b or c, and finishes in the our colour. Consider paths through d, going through b and also going through c instead b. Those two paths can't intersect, so can't finish in the same point. So one of the paths finishes with the rock from +group, and this means that from that rock when tracing back, there is a path that is firstly going through b or c and than to d. Switch d to a and go to colours below. So if one rock has connections outside solved colours none of the rocks from that colour can be in path. By this procedure, we end up with group of colours that are only connected with each other. Now we can apply inductive hypothesis that will solve us the case. Only when we can't solve by induction is that it is the whole set of colours, and we stopped in the last colour. But than remember sorting of colours (those with pairs are before). If the last one is with pair in colour, then all previous are, so just put all pairs in one group, and all other rocks in another group. (If two pairs in one colour, put one to one group and another pair to another) If the last colour is without pairs, that means that all of them are assigned to some group. So, we have done assignment to groups 2n times. As every assignment is changing difference of the rocks in one group and another by 2 mod 4, final difference is 0 mod 4, so either all 4 rocks are in one group, or 2 are in one, and two are in another. If 4 rocks are in one group, start the path from one of them, and it must finish in another from last colour, and we get 2 rocks in one group, and 2 rocks in another, and we are done.

We will show it is possible to find a subset \(S\) of the pebbles such that \(S\) contains two pebbles of each color, and for each \(i\le2n\), the pebble of weight \(i\) is in \(S\) if and only if \((4n+1)-i\) is in \(S\). Consider a (not necessarily simple) graph \(G\) on \(n\) vertices, each representing one of the \(n\) colors. For each \(i\le2n\), if the pebble of weight \(i\) has color \(a\) and the pebble of weight \((4n+1)-i\) has color \(b\), draw an edge from \(a\) to \(b\). Thus, each \(i\le2n\) represents an edge of \(G\). Then \(G\) is a 4-regular graph, so by taking alternating edges of Eulerian circuits of each connected component, there is a 2-regular subgraph \(G'\) with the same vertex set as \(G\). If we let \(S\) contain each edge that is present in \(G'\), then \(S\) obeys the desired conditions. End proof.

Sorry, my question was because i didn't understand this part: Quote: Consider $\alpha_j>0$ the least natural such that $j \in T_l$ and $j \notin T_k$. Of course there is such $j$, as $S_{T_l}>S_{T_k}$. Why there is such natural? Maybe there is some negative in $T_k$ and not in $T_l$ and this is why $S_{T_l}>S_{T_k}$? (If i understood correctly, in your solution the partition is to groups of $(a_i,d_i) \text{ and } (b_i,c_i)$ except when $\alpha_i=0$? If the answer is yes, how your solution will divide the stones in my example? $(1,2,3,18)$ $(4,16,17,19)$ $(5,7,11,12)$ $(6,8,10,13)$ $(9,14,15,20)$

IMO 2020 Problem 3 wrote: There are $4n$ pebbles of weights $1, 2, 3, \dots, 4n.$ Each pebble is coloured in one of $n$ colours and there are four pebbles of each colour. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied: The total weights of both piles are the same. Each pile contains two pebbles of each colour. Proposed by Milan Haiman, Hungary and Carl Schildkraut, USA

A slightly different solution: Make a bipartite graph $G$, where one partition has $n$ vertices representing the colors, and the other has $2n$ vertices representing the weights modulo $2n$. Make an edge from a color-vertex to a weight-vertex iff a pebble of that color has that weight modulo $2n$. On the edge, write a $+$ if the weight of the pebble in question is $>2n$ and a $-$ otherwise. Obviously, every vertex has an even degree, so there's an Eulerian cycle. We now want to choose a single edge incident to every color vertex, and put the matching pebble in the left pile. The rest goes to the right pile. Obviously, both the piles will have two pebbles of each color, so we are done if both the piles have the same number of $+$ edges. This part is rather easy, here's one of the possible approaches. Say a color-vertex is balanced if it's two neighboring edges in the cycle are of opposite sign. The parity of the number of balanced edges matches the parity of $+$ signed edges, which is $2n$, so it's even. Then put a half of those $+$ edges in each pile, so we're done $\blacksquare$ EDIT: This doesn't really work

A bit easy for an IMO 3 Consider the pairs $(1,4n), (2,4n-1), \cdots (2n, 2n+1)$. Now, construct a graph in the following way: denote vertex $i$ as the ith color, and connect vertices $i, j$ with an edge for each pair $(a,4n+1-a)$ such that $a$ is colored with color $i$ and $4n+1-a$ is colored with color $j$ (where multiple edges and self-loops are okay). Observe that each vertex has degree $4$. Now, for each of the connected components, consider an euler cycle. Each connected component must have one since the degree is $4$ for each vertex. In each euler cycle, since there are an even number of edges per connected component, we can split the edges into two groups such that no two adjacent edges in the euler cycle are in the same group. Since each edge represents a different pair $(a, 4n+1-a)$, this corresponds to putting $a, 4n+1-a$ in the same group. Furthermore, each color is represented twice in each group. This is because two adjacent edges will put two numbers colored $i$ in different groups. Finally, observe that since each edge that gets put in a group adds $4n+1$ to the sum, and there are equal number of edges in both groups, the sum of the numbers in each group is the same. We conclude that this construction works.

Deez. So basicaly i make a graph $G$ with $n$ vertices which represent the $n$ colors. Now call a pair of pebbles opposite if their weights add up to $4n+1$, on the graph if a pair of opposite pebbles have colors $a,b$ then we match $a,b$ by an edge on the graph. Now lets do strong induction, for $n=1$ the problem obviously holds hence now if we assume that it holds for all less or equal than $n-1$ ,we will prove it for $n$. If there was $4k$ pebbles of the same colors such that we can divide them into $2k$ pairs of pebbles such that they add up to $4n+1$ then we can just put one pair on one side and the other pair in the other side and then apply inductive hypotesis. Now if there was nothing of that we would have that counting loops every vertex on the graph $G$ has degree $4$ hence there exists an eulerian cycle passing through all the vertices of $G$ which means that taking that there exists a subset $\mathcal S$ of $2n$ pebbles such that there are $2$ pebbles of each color and their weights add up to $n(4n+1)$ and now if u consider the rest of the pebbles since the total sum of weights is $2n(4n+1)$ and that there are also $2$ pebbles of each color there we are done by taking $\mathcal S$ and taking the rest of the pebbles.

Aryan-23 wrote: There are $4n$ pebbles of weights $1, 2, 3, \dots, 4n.$ Each pebble is coloured in one of $n$ colours and there are four pebbles of each colour. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied: The total weights of both piles are the same. Each pile contains two pebbles of each colour. Proposed by Milan Haiman, Hungary and Carl Schildkraut, USA Amazing problem!!! Let \(\mathcal{G}\) be the graph with \(n\) vertices representing the \(n\) colors, and we connect two nodes \(i\) and \(j\) if for some positive integer \(a\), \(a\) has color \(i\) and \(4n+1-i\) has color \(j\). Note that the degree of each vertex is \(4\). This implies that the number of edges on a connected component is even, and therefore there exists an Eulerian circuit. I am now done, because I will make two sets \(A\) and \(B\) and put \(a\) in \(A\) and \(4n+1-a\) in \(B\) if \(a\)'s color is \(v_i\) and \(4n+1-a\)'s color is \(v_{i+1}\), where \(v_1\hdots v_n\) is our Eulerian circuit, which means we get equal number of colors on both sets. So \(2\) on each side, and thus we are done. Note, if we have 4 self loops, then \(a,b,4n+1-a,4n+1-b\) are all colored \(C\). Then just put \(a\) in set \(A\), \(4n+1-a\) in set \(B\), \(b\) in set \(A\) and \(4n+1-b\) in set \(B\). If you have \(k\) such self loops, apply this formula and for the remaining vertices we have a circuit, so we're done.

Cool problem! This idea of trying to prove that an Eulerian Circuit is also used on ISL 2011/N8. The lesson is that is way easier to prove that an Eulerian Circuit exists than proving that a Hamiltonian cycle exists. Consider the pairs $(1,4n),(2,4n-1),...,(2n,2n+1)$ that have equal sum. Let the colors be $c_1,c_2,...,c_n$. Consider the possibly multigraph $G$ with vertices on $c_1,c_2,...,c_n$. We connect $c_i$ to $c_j$ if and only if there is a pair of the form $(k,4n+1-k)$ containing both colors. Observe that $|E(G)|=2n$ and $deg(v)=4$ for all $v \in G$, so if we find an Eulerian Circuit in $G$, we can place any two consecutive edges (pebbles) on different piles, and since each pair has sum $4n+1$, each vertex has even degree , then each pile will have $2$ pebbles of each color. Thus, it is enough to find an Eulerian Circuit in $G$. $\quad (\star)$ Nevertheless, it is enough to find an Eulerian Circuit in each connected component of $G$ (due to $(\star)$). Moreover, since each connected component is connected and each vertex in it has even degree, each connected component indeed has an Eulerian Circuit, so from $(\star)$, we are done. $\blacksquare$

This is going to be the first IMO combinatorics problem that I'll solve. To my benefit, I far better off with graph theory rather than the mainstream combinatorics methods. Anyway would someone kindly give me some hints to get started?

Consider $2n$ pairs of coins with weights $(1,4n),(2,4n-1),...,(2n,2n+1);$ it's suffice to prove that there is a partition of these pairs onto two piles, with $n$ pairs in both, satisfying the second condition. Consider a multi-graph (allowing loops) where colors of pebbles are represented as vertices and pairs including pebbles of two colors are represented as edges; our goal is to paint all edges black and white in such way, that every vertex incident with exactly $2$ black edges. Every component of graph contains only vertices of degree $4$ and so has an Euler circuit - paint edges alternately going on direction of this circuit. This clearly works, as the number of edges in each component is even.

Construct multigraph $G$ on $1, \ldots, n$ where for each $a$ and $b$ in $\{1, \ldots, 4n\}$ with $a+b=4n+1$, an edge between the color $x$ of the pebble with weight $a$ and the color $y$ of the pebble with weight $b$ is appended to $G$. We observe that since there are $4$ pebbles of each color, every vertex of $G$ has degree $4$. Since every vertex of $G$ has even degree, $G$ has an Eulerian circuit. Construct set $E$ of edges of $G$ by taking alternate edges in the Eulerian circuit. Thus, each edge is chosen exactly twice in $E$, and since they were chosen alternately in the Eulerian circuit, $E$ has $n$ distinct elements and the sum of the weights corresponding to the edges in $E$ is $n(4n+1)$. Hence, we can let $X$ be the set of pebble weights corresponding to the edges in $E$ and $Y$ be the set of remaining pebble weights, and $X$ and $Y$ meet the requirements for the piles, as desired. Remark. The motivation behind taking alternate edges in the Eulerian circuit is due to the construction in Petersen's proof of the $k=2$ case of Petersen's $2$-factor theorem.

Let $1 , 2 , .. , n$ be a colors of the pebbles. According to the colors $(1 , 2 , .. , n)$ of $(i , 4n + 1 - i)$ draw an edge between these colors and construct a multigraph $G$ with $n$ vertices. (vertices represent colors) It is clear that every vertex has degree 4 (loop and multiple edges between two vertices are allowed). Therefore $G$ contains Eulerian circuit, so by taking alternating edges of Eulerian circuits of each connected component , there is a $2$ regular subgraph $H$ with the same vertex as $G$. By taking each edge of $H$, this set obeys the desired conditions.

In order to get the two piles to have the same sum of weights, the total weight of each pile must be $n(4n+1)$. We'll split the $4n$ pebbles into the two piles such that each pile consists of $n$ pairs of sum $4n+1$. $~$ Consider a graph on $n$ vertices, and consider each one as a color. The graph can have loops and double edges. For each pair of numbers that sum to $4n+1$, we draw a vertex between the vertices whose color the numbers are in. Note that each vertex has degree $4$ exactly. Consider any connected component in this graph. Since all vertices have even degree, there is an Eulerian Cycle. Since each vertex has degree $4$, the number of edges in this cycle is even. Thus, we can, going along the cycle, alternately put edges of this cycle into the two piles. In this way, each vertex will be connected to equally many edges in one pile as the other, so each pile will have two of each color, as desired.

hi k=2 case of two-factor theorem and euler stuf (first time EVER encountering this, wow!) also thanks to ming @above for providing like the massive hint of pairs. oops Consider pairs $(1,4n),\dots,(2n,2n+1)$. It turns out it's enough to just consider adding these pairs to the piles (!). In hindsight, this should have been obvious---the condition that sum is even holds if $n\equiv 3\pmod 4$ as well, so it makes sense that something stronger would hold. Since the number of pairs is exactly $2n$ (hence each pile has $n$ pairs), well, that's perfect. At this point, I was trying to induct downwards. It turns out that the main issue comes with having a pair $CC$. One of the specific cases is \[CC, CA, CA\]and in this case we can keep going to get a cycle like \[CC, CA, CA, AB, AB, \dots\]and at this point it clicked that I should probably use a graph here. Each vertex (corresponding to one of the $n$ colors) has degree $4$, multiple edges and self-loops are allowed (self-loops contribute degree $2$), and we need a subgraph where each vertex has degree $2$. By Petersen's 2-factor theorem this is trivial---it's exactly the statement for $k=2$. The proof of that subcase is the crux of the problem then. Consider an Eulerian path which visits every edge exactly once. (Never used this before, how did I not know about this in Olympiad!?!??! I guess it's rare that you encounter scenarios where the graph has even degrees)

so apparently self-loops allowed is accounted for. above was essentially a way to locally modify the path so that it would be fine, but since it's well known we breeze past. yay!

Let the colors be $\mathcal{C} = \{c_1,\dots,c_n\}$. Let $c(k)$ be the color of $k$. Let $G$ be a multigraph with loops on $C$ such that the edges are \[\{c(1), c(4n)\}, \{c(2), c(4n-1)\},\dots, \{c(2n), c(2n+1)\}.\] Claim: We can delete edges from a $4$-regular multigraph $H$ with loops to make it $2$-regular. (We consider loops to count twice toward a vertex's degree.) Proof: Assume WLOG $H$ is connected. Then, $H$ has a Hamiltonian cycle. Because $H$ has an even number of edges, we can delete every other edge of the Hamiltonian cycle. This will cut the degree of each vertex in half. $\blacksquare$ So, some subset $S\subseteq E(G)$ contains each color exactly twice within its edges. Let $S = \{\{c(s_1), c(4n+1-s_1)\},\dots,\{c(s_n), c(4n+1-s_n)\}\}$. Then, one of the piles can be $s_1, \dots, s_n, 4n+1-s_1, \dots, 4n+1-s_n$ and the other pile can be the remaining pebbles. This pile has total weight $n(4n+1)$, which is half of the total sum, and it contains two pebbles of each color.

Create a graph with each of the $n$ colours being a vertex and connect two vertices of colour $c_i$ and $c_j$ if there exists a pair of values $x, y$ such that $x+y=4n+1$ and the colours of $x$ and $y$ are $c_i$ and $c_j$. Thus we get a graph where every vertex has degree $4$. Thus an eulerian cycle exists thus take every second edge for one group and all remaining edges for the other which clearly works.