@algopuzzles profile picture
Algorithmic Puzzles @algopuzzles

Problems in graph theory, combinatorics and algorithms. Contests are held on Algo Muse website.

Joined April 2009
  • Tweets 227
  • Following 4
  • Followers 4,105
10 Photos and videos
Prove that any convex polygon of area 1 sq. unit can be covered with a rectangle of area 2 sq. units.
1
2
418
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.
3
371
Show that a map formed on a plane by finitely many circles is 2-colourable.
3
8
1,936
Prove that a graph with n nodes either has a path of length k or has O(kn) edges.
1
4
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
12
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
A tiling problem with wireframes. [Source: Micheal Brand]. #exportober
3
2
6
Algorithmic Puzzles retweeted
Some theorems@CihanPostsThms
4 Sep 2022
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
25
188
Algorithmic Puzzles retweeted
utpal chattopadhyay@uc59
21 Sep 2022
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
Algorithmic Puzzles retweeted
Dave Richeson@divbyzero
19 Aug 2022
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
51
233
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
We have an array of size n and want to pick the k smallest elements. Show that with const. probability this algo. works: 1. Color each element u.a.r with one of the k^2 colors. 2. Pick the minimum element of each color. Call this set S. 3. Pick the k smallest elements from S.
3
1
5
Context: The above algorithm runs in O(n k^2 log k) which is linear for small k. It adapts well if the elements in the array are seen in streaming fashion. #exportober
2
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
4
The integers on the number line are colored either white, black, or red. The coloring satisfies two conditions: 1. The negative of a black number must be white. 2. The sum of two black numbers (need not be distinct) must be white. Determine all possible colorings. #exportober
4
4
Correction: Rule 2 must be sum of two whites must be black.
#exportober
1
3
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
2
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
1
7
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
1
9
Load more