Algorithmic Puzzles @algopuzzles

Problems in graph theory, combinatorics and algorithms. Contests are held on Algo Muse website. algomuse.net Joined April 2009

Tweets

227
Followers

4K
Following

7
Likes

130

Algorithmic Puzzles @algopuzzles

a year ago

Prove that any convex polygon of area 1 sq. unit can be covered with a rectangle of area 2 sq. units.

1 0 7 386 1

Algorithmic Puzzles @algopuzzles

a year ago

Let S be a subset of [n]:={1,2,...,n} such that no three numbers in S are in arithmetic progression. Prove that |S| < 0.98n, using only elementary arguments.

0 0 3 340 2

Algorithmic Puzzles @algopuzzles

3 years ago

Show that a map formed on a plane by finitely many circles is 2-colourable.

3 0 8 2K 3

Download Image

Algorithmic Puzzles @algopuzzles

3 years ago

Prove that a graph with n nodes either has a path of length k or has O(kn) edges.

1 0 4 0 0

Algorithmic Puzzles @algopuzzles

3 years ago

Consider the set of n vertices of a convex polygon. Count the number of non-crossing paths that visit all the vertices. [Src: 11011110, David Eppstein] #exportober

2 1 13 0 6

Download Image

Algorithmic Puzzles @algopuzzles

3 years ago

You are given an array A[1..n] in which each element is at most k positions away from the position it would have been in if A was sorted. You don't know the value of k. Design an algorithm to sort the array in O(n log k) time. #exportober

3 1 27 0 8

Algorithmic Puzzles @algopuzzles

3 years ago

A tiling problem with wireframes. [Source: Micheal Brand]. #exportober

3 2 7 0 3

Download Image

Some theorems @CihanPostsThms

3 years ago

Consider the following variant of chess: In the first move only, white can opt in to make a single chess move or two consecutive chess moves; after that it is usual chess. Let's call this variant mhess. Theorem: In mhess, white can always force at least a draw.

4 26 192 0 20

utpal chattopadhyay @uc59

3 years ago

Take an nxn grid. Colour each square white or black in such a way that each 2x2 grid has exactly 2 white and 2 black squares. How many ways can this be done? Like I said, it is accessible to high school students and teachers. Of course counting options one by one is suicidal.

2 2 1 0 1

Dave Richeson @divbyzero

3 years ago

Tricky math puzzle: Suppose we have a disk of diameter 20 and strips of width 1 and length 20. We can cover the disk using 20 strips by laying them side-by-side. Can we do it with 19? No cutting is allowed. My next tweet is the answer/solution. 1/6

6 48 238 0 53

Download Image

Algorithmic Puzzles @algopuzzles

4 years ago

Suppose A is the adjacency matrix of an undirected graph. Prove that the absolute value of any eigenvalue of A is less than the max. degree of the graph. #exportober

3 0 0 0 0

Algorithmic Puzzles @algopuzzles

4 years ago

On an nxn grid a few nodes are set on fire at t=0. The fire spreads like this: if at least two neighboring nodes of node x are lit, then node x will also catch fire in the next time step. What's the minimum number of nodes that have to be lit to burn the entire grid? #exportober

5 0 5 0 0

Algorithmic Puzzles @algopuzzles

4 years ago

#exportober

1 0 5 0 0

Download Image

Algorithmic Puzzles @algopuzzles

4 years ago

We are given as input the vertices of a polygon P. Determine in near-linear time if P is a star. Specifically, determine if there is a point q inside P such that for every point p on the boundary of P, the line segment pq lies in the interior of P. (Src: David Mount) #exportober

2 0 3 0 0

Download Image

Algorithmic Puzzles @algopuzzles

4 years ago

We have a campus in the shape of a perfect disk of radius 1 km. We need to open 7 coffee shops so as to minimize the farthest distance anybody has to travel to get coffee. Where should we open the shops? [Src: Puzzle Toad] #exportober

0 1 8 0 0

Algorithmic Puzzles @algopuzzles

4 years ago

In a directed graph, a king is defined as a node from which all the other nodes are reachable in at most two steps. A tournament is a directed graph that has exactly one edge between any distinct pair of vertices. Prove that every tournament has a king. #exportober