Scribd
Upload
12 views

Algorithms

The document discusses various examples of greedy algorithms and their proofs, including selecting numbers from a 2 × n array, finding an induced subgraph in a graph, and covering nonnegative integers with historic sets. It also explores invariants and monovariants with an example involving a chessboard and conditions for achieving zero in all squares. The proofs demonstrate the underlying principles and conditions necessary for the algorithms to function correctly.

Uploaded by

วีรวัฒน์ พรเรืองทรัพย์
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views

Algorithms

The document discusses various examples of greedy algorithms and their proofs, including selecting numbers from a 2 × n array, finding an induced subgraph in a graph, and covering nonnegative integers with historic sets. It also explores invariants and monovariants with an example involving a chessboard and conditions for achieving zero in all squares. The proofs demonstrate the underlying principles and conditions necessary for the algorithms to function correctly.

Uploaded by

วีรวัฒน์ พรเรืองทรัพย์
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Algorithms

W EERAWAT P.
23 January 2025

§1 Greedy Algorithms

Example 1.1 (Russia 2005, France 2006, India TST 2012)


In a 2 × n array we have positive reals s.t. the sum of the numbers in each of the n columns
is 1. Show that we can select a number in each column s.t. the sum of the selected numbers
in each row is at most n+1
4 .

Proof. Let the numbers in the top row in non-decreasing order be a1 , a2 , . . . , an and let b1 , b2 , . . . , bn
be the corresponding numbers in the bottom row. Note that b1 ≥ b2 ≥ . . . ≥ bn . To have the desired
conclusion, select a1 , a2 , . . . , ak such that a1 + a2 + . . . + ak ≤ n+1 n+1
4 but a1 + a2 + . . . + ak+1 > 4 .
Consider the inequality
n+1
bk+1 + bk+2 + . . . + bn ≤
4
3n − 4k − 1
⇐⇒ ak+1 + ak+2 + . . . + an ≥
4
n+1 (n+1)(n−k)
Note that an ≥ an−1 ≥ . . . ≥ ak+1 > 4(k+1) . Thus, ak+1 + ak+2 + . . . + an > 4(k+1) . It suffices
to prove that
(n + 1)(n − k) 3n − 4k − 1
≥
4(k + 1) 4
⇐⇒ (n − 2k − 1)2 ≥ 0

which is true.

Example 1.2
In a graph G with V vertices and E edges, show that there exists an induced subgraph H
with each vertex having degree at least VE . (In other words, a graph with average degree d
has an induced subgraph with minimum degree at least d2 .)

Proof. Label the vertices “bad” if their degree is less than VE . To get the induced subgraph H,
delete any of the bad vertex of G, one at a time. We claim that the induced subgraph H is
guaranteed. This is because the ratio of edges and vertices after deleting n bad vertex is greater
E− nE
than V −nV = VE . Therefore, it is impossible to reach a stage when only 1 vertex is remaining
where the ratio of edges and vertices is zero. Hence, at some point, the algorithm will terminate,
leaving us with our desired induced subgraph H.

1
Weerawat P. — 23 January 2025 Algorithms

Example 1.3 (IMO Shortlist 2001, C4)


A set of three nonnegative integers {x, y, z} with x < y < z satisfying
{z − y, y − x} = {1776, 2001} is called a historic set. Show that the set of all nonnegative
integers can be written as a union of pairwise disjoint historic sets.

Proof. Let a = 1776 and b = 2001. A historic set is either of the form {x, x + a, x + a + b} or
{x, x + b, x + a + b}. Call these sets small sets and big sets respectively. We reframe the problem
as follows: Let the set of all nonnegative integers be written on a line. In each move, choose a
historic set and cover the corresponding numbers on the number line. We wish to show that all
numbers on the line could be covered where there are no repetitions. To do so, in each turn, we
cover the smallest number (which is also the smallest number in the set) that is not yet covered.
Use the small set if possible. Otherwise, use the big set. It suffices to show that this algorithm
can run indefinitely. Assume the contrary that there exists a move which terminates the algorithm.
Suppose it fails in the nth step where either the big set or the small set would cover the numbers
that has already been covered. Denote the smallest number covered in the ith turn by xi . We have
that xn + b = xi + a + b for some i. That is, xi = xn − a. This means that the number xn should
have been covered in the ith move, a contradiction.

§2 Invariants and Monovariants

Example 2.1 (IMO Shortlist 1989)


A natural number is written in each square of an m × n chess board. The allowed move is to
add an integer k to each of two adjacent numbers in such a way that non-negative numbers
are obtained. (Two squares are adjacent if they have a common side.) Find a necessary and
sufficient condition for it to be possible for all the numbers to be zero after finitely many
operations.

Proof. We color the board black and white alternately, starting from black in the first cell (first
row and column), where every adjacent cells are of different colors. Denote the sum of numbers
on black and white squares Sb and Sw respectively. In each move, we add the same number on
two squares, one of which is white and one is black. Thus, Sb − Sw is an invariant. At the end,
Sb − Sw = 0, that means Sb = Sw at the beginning as well. Therefore, this is a necessary condition.
Next, we prove that this is a sufficient condition.

You might also like