Edges in a Table

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

Edges in a Table

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iran TST 2015, exam 1, day 2 problem 2

The post below has been deleted. Click to close.

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

97 posts

#1 h May 11, 2015, 2:33 PM • 2 Y

Y by Adventure10, Mango247

Let $A$ be a subset of the edges of an $n\times n$ table. Let $V(A)$ be the set of vertices from the table which are connected to at least on edge from $A$ and $j(A)$ be the number of the connected components of graph $G$ which it's vertices are the set $V(A)$ and it's edges are the set $A$ . Prove that for every natural number $l$ :
$\frac{l}{2}\leq min_{|A|\geq l}(|V(A)|-j(A)) \leq \frac{l}{2}+\sqrt{\frac{l}{2}}+1$

This post has been edited 1 time. Last edited by TheOverlord, May 11, 2015, 2:33 PM

Z K Y

The post below has been deleted. Click to close.

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

314 posts

#2 h May 16, 2015, 4:24 PM • 2 Y

Y by Adventure10, Mango247

Here is an outline:
Lemma:Consider a connected graph with its vertices are some vertices of the table and edges some edges of the grid.Let $a$ be the number of vertices and $d$ the number of edges.Then $d \leq 2(a-\sqrt{a})$ .
Proof:Suppose this vertices lye in $x$ rows and $y$ rows.Now,denote $xi$ the number of vertices in $i$ -th row ,and $yi$ the number of vertices in $i$ -th column.Now,it is obvios that if we have $m$ vertices in some row/column,we can have at most $m-1$ edges that belong to that row,so sum this over all rows and columns and we obtain that we can have maximum $2a-x-y$ and since $xy>=a$ it means that $x+y$ is minimum $2\sqrt{a}$ (by $AM-GM$ ),so we proved our lemma.
Now,suppose we have $c$ connected components and that component $i$ has $ci$ edges.Just use the inequality from the above lemma, sum over all and we proved that the minimum is at least $l/2$ .Now,it remains to find an example which is easy from the above lemma( consider a grid $k*k$ or $k(k+1)$ and connect mostly all edges,I will write in detail if neccesary but it is easy).

This post has been edited 8 times. Last edited by junioragd, May 18, 2015, 4:32 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a