Placing marbles

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Placing marbles

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 Vietnam National Olympiad - Problem 5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

301 posts

#1 h Dec 26, 2024, 5:13 AM

Y by

Consider a $3k \times 3k$ square grid (where $k$ is a positive integer), the cells in the grid are coordinated in terms of columns and rows: Cell $(i, j)$ is at the $i^{\text{th}}$ column from left to right and the $j^{\text{th}}$ row from bottom up. We want to place $4k$ marbles in the cells of the grid, with each cell containing at most one marble, such that
- Each row and each column has at least one marble
- For each marble, there is another marble placed on the same row or column with that marble.
a) Assume $k=1$ . Determine the number of ways to place the marbles to satisfy the above conditions (Two ways to place marbles are different if there is a cell $(i, j)$ having a marble placed in one way but not in the other way).
b) Assume $k \geq 1$ . Find the largest positive integer $N$ such that if we mark any $N$ cells on the board, there is always a way to place $4k$ marbles satisfying the above conditions such that none of the marbles are placed on any of the marked cells.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

30 posts

#2 h Dec 26, 2024, 7:56 AM • 1 Y

Y by VIATON

Very nice problem! Here is a sketch of the solution:
Let $G$ be a graph on $4k$ vertices such that each show a marble and we connect two vertices if those two marbles are located in the same row or column.
Take a connected component of $G$ like $H$ . By modeling $H$ using BFS algorithm, we get that the set of the rows and columns that vertices in $H$ are located in, has at most $\vert H\vert +1$ elements. Note that each connected component has at least $2$ vertices. Thus with $4k$ marbles, we can cover at most $2k\times 3$ rows and columns. Note that the equality holds if each connected component of $G$ has exactly $2$ vertices. In the problem statement, the equality in holding, thus we have placed $k$ vertical dominos and $k$ horizontal dominos. Using this, you can get that for part a the answer is $\boxed{9}$ .
For part b, I will show that the maximum $N$ is $\boxed{N=3k-1}$ by inducting on $k$ .
Note that $N<3k$ since we can just mark all cells of the first row. The base $k=1$ of our induction can be checked easily. Now assume that we've proved the statement for $k=1,2,\cdots ,t$ . Let's prove it for $k+1$ . You should prove that we can place a horizontal domino and a vertical domino of marbles such that in the three rows and three columns that they are in, we have at least $3$ marked cells. then we can remove those three rows and three columns and use induction, since we have a $3k-3\times 3k-3$ table with less that $3k-1-3<3(k-1)$ marked cells. Finding those two dominos is not hard and can be done by picking the first domino such that in has at least two marked cells in its rows and column.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

phungthienphuoc

95 posts

phungthienphuoc

#3 h Dec 26, 2024, 9:44 AM

Y by

Part a
Consider a bipartite graph $G=(A,B,E)$ , where:
- $A=\{a_1,a_2,\ldots,a_{3k}\}$ are the vertices corresponding to the rows of the grid.
- $B=\{b_1,b_2,\ldots,b_{3k}\}$ are the vertices corresponding to the columns of the grid.
- For all $1\le i,j\le 3k$ , $(a_i,b_j)\in E$ if and only if we are able to put a marble in the cell at row $i$ , column $j$ .

For every placement of marble, let $F$ be a subgraph of $G$ containing only the edges corresponding to the cells having marbles.
Notice that:
- There is no isolated vertex in $F$ .
- For all $e=(u,v)\in E$ , there exists $e'\in E$ such that $e'$ is incident to either $u$ or $v$ .
Those two statements above are equivalent to the fact that every connected component of $F$ has at least 2 edges.

Let $C_1,C_2,\ldots,C_m$ be all the connected components of $F$ .
We have:
$\bullet$ $\displaystyle 4k=\left|E(F)\right|=\sum_{1\le i\le m}{\left|E(C_i)\right|}\ge 2m\Leftrightarrow m\le 2k$
$\bullet$ $\displaystyle 4k=\left|E(F)\right|=\sum_{1\le i\le m}{\left|E(C_i)\right|}\ge\sum_{1\le i\le m}{\left(\left|V(C_i)\right|-1\right)}=\left|V(F)\right|-m=6k-m\Leftrightarrow m\ge2k$
Therefore, $m=2k$ , which means, each connected component has exactly 2 edges.

For $k=1$ , we have 3 vertices in each part. To form a subgraph $F$ , we can choose 2 vertices from $A$ and a vertex from $B$ for the first connected component, and the rest will form the second connected component. The number of such graphs is: $\binom{3}{2}\binom{3}{1}=9$ .

Part b
As a convention, we will call the pair of vertices in $E$ which does not have an edge connecting them as a "marked edge".

Firstly, we will show that $N\le3k-1$ .
Indeed, if $N\ge3k$ , we could mark all the cells in the first row, which, since then, violates the first criterion of the marble placement.
Now, we need to show that $N\le3k-1$ satisfies the problem using induction by $k$ .

For $k=1$ , there are two cases:
$\bullet$ Two marked edges are both incident to a vertices. WLOG, suppose that they are $(a_1,b_2),(a_1,b_3)$ . Then, we can construct $F$ from $(a_1,b_1),(b_1,a_2),(b_2,a_3),(a_3,b_3)$ .
$\bullet$ Two marked edges so not share a common vertex. WLOG, suppose that they are $(a_1,b_1),(a_2,b_2)$ . Then, we can construct $F$ from $(a_1,b_2),(b_2,a_3),(b_1,a_2),(a_2,b_3)$ .
The base case is done.

Suppose that the statement is true for $k=l-1$ ( $l\in\mathbb{Z}^+\setminus\{1\}$ ), we need to show that it is also true for $k=l$ .
WLOG, suppose that $a\in A$ is the vertex having smallest degree of $G$ .
For every vertex $v$ of $G$ , $3l-\deg{v}$ is the number of marked edges incident to $v$ .
Then, for every vertex $v$ different from $a$ , we have $(3l-\deg{v})+(3l-\deg{a})\le3k-1$
$\Rightarrow 3l+1\le\deg{a}+\deg{v}\le2\deg{v}\Rightarrow\deg{v}\ge\dfrac{3l+1}{2}\Rightarrow\deg{v}\ge 3$ (as $l\ge2$ ).
We have:
$\bullet$ $\exists b\in B:(a,b)\in E$ . Choose $b$ with smallest possible degree.
$\bullet$ $\exists a_1\in A:a_1\ne a, (a_1,b)\in E$ . Choose $a_1$ with smallest possible degree.
$\bullet$ $\exists b_1\in A:b_1\ne b, (a_1,b_1)\in E$ . Choose $b_1$ with smallest possible degree.
$\bullet$ $\deg{b_1}\ge3\Rightarrow\exists a_2\in A:a_2\ne a,a_2\ne a_1,(a_2,b_1)\in E$ . Choose $a_2$ with smallest possible degree.
$\bullet$ $\deg{a_2}\ge3\Rightarrow\exists b_2\in A:b_2\ne b,b_2\ne b_1,(a_2,b_2)\in E$ . Choose $b_2$ with smallest possible degree.

Choose $\{(a,b),(b,a_1)\}$ and $\{(b_1,a_2),(a_2,b_2)\}$ as 2 connected components of $F$ . It is sufficient to show that we can construct $2l-2$ more connected components of 2 edges from $G'=G\setminus\{a,b,a_1,b_1,a_2,b_2\}$ .

We have $(3l-\deg{a})+(3l-\deg{a_1})+(3l-\deg{a_2})=9k-(\deg{a}+\deg{a_1}+\deg{a_2})$ is the number of marked edges incidents to either $a$ , $a_1$ or $a_2$ .
Similarly, $9k-(\deg{b}+\deg{b_1}+\deg{b_2})$ is the number of marked edges incidents to either $b$ , $b_1$ or $b_2$ .
We will prove that $\max\{9k-(\deg{a}+\deg{a_1}+\deg{a_2}),9k-(\deg{b}+\deg{b_1}+\deg{b_2})\}\ge 3$ ,
or, $\min\{\deg{a}+\deg{a_1}+\deg{a_2},\deg{b}+\deg{b_1}+\deg{b_2}\}\le9l-3$ .
Indeed, for the sake of contradiction, suppose that $\min\{\deg{a}+\deg{a_1}+\deg{a_2},\deg{b}+\deg{b_1}+\deg{b_2}\}\ge9l-2$
$\Rightarrow \deg{a}=\deg{b}=3l-1$ .
That implies there is exactly one vertex of $B$ having degree of $3l$ , and it is either $b_1$ or $b_2$ . Back to how we chose $b_1$ and $b_2$ , we want to guarantee that they have minimum possible degree. However, as both $a_1$ and $a_2$ have degree $3l-1\ge5$ , we can choose other vertices in $B$ with degree less than $3l$ . Therefore, this contradicts our definition of $b_1$ and $b_2$ .
Thus, there are at least 3 marked edges incident to a vertex in $\{a,b,a_1,b_1,a_2,b_2\}$ .
Since then, in $G'$ , there are at most $N-3\le 3l-4$ marked edges. According to inductive hypothesis, $F$ can be successfully constructed.

By the principle of induction, we finish our proof.

This post has been edited 1 time. Last edited by phungthienphuoc, Dec 26, 2024, 11:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

28 posts

#4 h Dec 26, 2024, 1:37 PM

Y by

Part a)
We can do a case bash to see that every configuration is equivalent (equivalent meaning we can change the order of the rows and the order of the columns to get this configuration) to
O O X
O O X
X X O
Now we can "repermutate" the rows and columns. Clearly the only difference in the permutations is the position of the 3rd column in this construction and the 1st row. There are 3 places for each hence there are 9 spots.
Here is a solution without induction for
Part b)
First we will solve for $k=1$ . We claim the answer is $N=2$ . It is easy to see that any 2 marked cells can be permutated to be one of these:
X X O X O O X O O
O O O X O O O X O
O O O O O O O O O
and the construction from a) works.
Now the bound: If $N\geq3k$ we can mark a whole row and we are done.
Now for the construction, again. We define a rook set of size $k$ to be $k$ rooks on a $k \times k$ square, s.t. every rook is at a different row and column from all other rooks.
Main lemma: If we have less than $k$ marked cells in a $k \times k$ area, we have a rook set of size $k$ there with no rook on a marked square.
Proof: We have $k$ disjoint rook sets (just take all the diagonals of the form $(i, j)$ , $(i+j)=m$ (mod $k$ ) for all $m$ ), and if we have less than $k$ marked cells in the $k \times k$ , there is some rook set with no marked cells in it.
Now divide the $3k \times 3k$ into $9$ $k \times k$ squares. If there is at most $3k-1$ marked cells there, there are at most $2$ $k \times k$ with at least $k$ marked cells in them. Now we can use the construction for $k=1$ and put rook sets on $4$ of the $9$ $k \times k$ s.t. the $4$ squares form a valid construction for $k=1$ and they all have less than $k$ marked cells in them. Now, for each $k \times k$ picked, we will put a valid rook set there, and that will finish the construction.

This post has been edited 1 time. Last edited by Davdav1232, Dec 26, 2024, 1:39 PM
Reason: added that my solution was better than the previous solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

13 posts

#5 h Mar 19, 2025, 1:48 AM

Y by

Solved with Unbounded and Vinícius (does not have aops account

)
I will solve only part b. I will use a generalization of Hall's Theorem, and no induction.

Let $G$ be a bipartite graph with vertices as the rows and columns, and connect one row and one column if we place a marble in the intersection cell of them. This graph satisfies the following:
$~~~~~\bullet$ $e(G) = 4k$ (there are $4k$ marbles);
$~~~~~\bullet$ every vertex has degree at least one (there is at least one marble in each row and column);
$~~~~~\bullet$ for each edge there is another edge with some common endpoint (for each marble, there is another marble placed on the same row or column of that marble).
We can simplify these information by saying that each connected component has at least $3$ vertices and that $e(G) = 4k$ . Hence, if $C_1,\ldots,C_M$ are the connected components, with $c_1,\ldots,c_M$ vertices each, we get that $C_i$ has at least $c_i - 1$ edges, so
$4k \geq \sum_{i = 1}^M c_i - 1 = 6k - M \Longrightarrow M \geq 2k.$ On the other hand, $|C_i| \geq 3$ , so, since there are $6k$ vertices, we have
$6k = \sum_{i = 1}^M |C_i| \geq 3M.$ so $M \leq 2k$ . Hence, we have exactly $2k$ connected components, each being a "cherry", that is, $3$ vertices and $2$ edges. We say that a vertex is fat if it has degree $2$ (each cherry has one fat vertex). Call the set of vertices that correspond to rows as $\mathcal{R}$ , and the set of vertices that correspond to columns as $\mathcal{C}$ . Then $|\mathcal{R}| = |\mathcal{C}| = 3k$ , and since $G$ is bipartite in $\mathcal{R}, \mathcal{C}$ , there are $k$ cherries with fat vertex in $\mathcal{R}$ and $k$ cherries with fat vertex in $\mathcal{C}$ . Let $A\subset\mathcal{R}, B\subset\mathcal{C}$ be the set of fat vertices (so $|A| = |B| = k$ ), and there is not edge connecting vertices of $A$ and $B$ . Hence, we have two double matchings in $G$ : one from the $A$ to $\mathcal{C}\setminus B$ and one from $B$ to $\mathcal{R}\setminus A$ . Just to make things clear, we make the following

Definition. A double matching from a set vertex $X$ to a set vertex $Y$ is a graph where each vertex of $X$ is connected with two vertices of $Y$ , and each vertex of $Y$ is connected with one vertex of $X$ . In particular, it is required that $|Y| = 2|X|$ .

So this is just a generalization of Hall (we want to marry every boy with two girls), we will find a necessary and sufficient condition in order that there exists a double matching in a bipartite graph from $X$ to $Y$ .

Lemma. Given a bipartite graph $G$ from vertex set $X$ to vertex set $Y$ with $|Y| = 2|X|$ , let $N(S)$ be the neighborhood of $S$ in $G$ . Then, there exists a double matching from $X$ to $Y$ iff $|N(S)| \geq 2|S|$ for all $S\subset X$ .
Proof. This condition is clearly necessary. We prove it is sufficient. But this is quite easy: for each vertex $v$ of $X$ , create a copy $v'$ of it,that is, a vertex with the same neighbors as $v$ in $G$ . Let $X'$ be the union of the set $X$ with all copies of the vertices of $X$ (so $|X'| = |X|$ ). One can check that Hall's condition holds for the bipartite graph from $X'$ to $Y$ , so there is a matching from $X'$ to $Y$ . Now, let $u,u'$ be the mathed vertices of $v,v'$ . Then our double matching is just $v\rightarrow\{u,u'\}$ .

Hence, what we want to do in the problem is the following: we start with the complete bipartite $K_{3k,3k}$ from rows to columns and we delete $N$ edges (which is the same as mark a cell). After that, we want to split $\mathcal{R}$ into $A,C$ and $\mathcal{C}$ into $B,D$ such that $|A| = |B| = k$ (the fat vertices), $|C| = |D| = 2k$ (the other vertices, each with degree $1$ ) in a way that there exists a double matching from $A$ to $D$ , as well as a double matching from $B$ to $C$ . We clearly have to delete at most $3k - 1$ edges, since if we delete all edges incident to one vertex such partitions do not exist. We will show that such partition always exists if we delete $3k - 1$ edges. For this, we need the following

Lemma. Given a complete bipartite graph $K_{n,2n}$ , if we delete $n - 1$ of its edges, then we can find a double matching on the resulting graph (note that this is not true if we can delete $n$ edges).
Proof. Let $X$ and $Y$ be vertex sets of the bipartite graph $K_{n,2n}$ , with $|Y| = 2|X| = 2n$ . Given some $A\subset X$ with $|A| = a$ and some $B\subset Y$ with $|B| = 2a - 1$ , we only have to show that there exists some edge with one endpoint in $A$ and the other endpoint in $Y\setminus B$ . We actually prove that the number of edges with some endpoint in $A$ is greater than the number of edges with some endpoint in $B$ . Indeed, there are at most $n\cdot(2a - 1)$ edges with one endpoint in $B$ (as the degree of each vertex in $B$ is $n$ in $K_{n,2n}$ ), while there are at least $2n\cdot a - (n - 1)$ edges with one endpoint in $A$ (as the degree of each vertex of $A$ is $2n$ in $K_{n,2n}$ and we delete $n - 1$ edges), and of course $n(2a - 1) < 2na - n + 1$ .

Hence, all we have to do is to split $\mathcal{R}$ and $\mathcal{C}$ into $A,C; B,D$ such that there are at most $k - 1$ removed edges between $A$ and $D$ , as well as at most $k - 1$ edges between $B$ and $C$ . But it is sufficient to guarantee that there are at least $2k$ removed edges between $C$ and $D$ , since we have $3k - 1 = 2k + (k - 1)$ deleted edges (and so there are at most $k - 1$ edges between $A,D$ and $B,C$ together, and so in each of the pairs). But it is quite easy now: choose $2k$ deleted edges and put its endpoints into $C\cup D$ , and this is possible as $|C| = |D| = 2k$ ( $2k$ edges have at most $2k$ endpoints in $\mathcal{R}$ as well as at most $2k$ endpoints in $\mathcal{C}$ ).

This post has been edited 2 times. Last edited by jonh_malkovich, Wednesday at 11:05 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#6 h Mar 19, 2025, 2:32 AM

Y by

Hexa greetings

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a