Jian Li's Interesting Problem Collection

(some of them are interesting puzzles, some are little maths problems, some are algorithms problems, and some are just exercises which I am interested in)

For part of these problems, I attach my (rough, even possibly wrong) sketch of solutions.

*: recommended

---------------------------

*1.Rotate Vector

ENG:

There are fixed positive integers N and K, each at least 2. We have an unknown vector V of length N of integers between 0 and K-1 inclusive. During each move, we propose another vector W of length N, of integers between 0 and K-1. A genie selects a secret integer J between 0 and N-1 and rotates W by J positions: Rot(W,J) is the last N-J entries of W, followed by the first J entries of W. The genie then replaces V by (V + Rot(W,J))(mod K). If the new value of V is all 0, we win; otherwise we continue to play.

Part 1 :
For what pairs of integers (N,K) is there a fixed finite sequence of moves (a sequence of vectors W) such that if we apply this sequence in order, we are guaranteed to win by the time the sequence is finished? Prove that these pairs admit such a sequence, and that no other pairs do.
　

(My draft of Solution)(eng)

Part 2 :
Fix K=2. For each N, there is a largest integer M such that we can produce a sequence of vectors W and guarantee that if we apply this sequence in order, we will guarantee that on one of the moves, at least M elements of V are zero. (So we have a more relaxed definition of "winning".) What can you say about the relation between N and M?

(I don't know how to solve it)

=============================================================

*2 two Cyclic String Problem:

ENG:

the first problem is that given 2 cyclic strings, both consisting n distinct
letter,namely a permuatation of 1 to n.
the problem is to find a rotation of one string that minimize the swap
distance.(i.e.the number of swaps of adjacent elements to bring one necklace to the other )

An O(n^2) algorithm is trivial.
can you give out a O(nlogn) algorithm?(not very hard)

-

second problem: (Godfried's cyclic swap distance problem)
given two 2-color necklaces of the same size and same number of 1's,
find the rotation that minimizes the swap distance, i.e., the number of swaps of
adjacent elements to bring one necklace to the other).

the O(n^2)algorithm is nontrivial ,but not very hard, Can you find one?
To find a o(n^2) algorithm seems to be very hard(at least i don't know how to do it).
　

Remark: It seems to be solved in a ESA 06 paper "Necklaces, Convolutions, and X+Y", although

I havent read that paper yet.

New remark: the paper is interesting.

=============================================================

3. An exercise of Graph Theory

CHS:
"设G是无向简单图，G的最小顶点度数大于等于3，证明G中各圈的长度的最大公约数
为1 或 2."

ENG:

"G is a undirected simple graph, and the minimum degree of G is at least 3.

Prove the greatest common divisor of the lengths of all cycles in G is either 1 or 2."

==============================================================

*4 Chessboard Coloring Problem

CHS:

: 一个n*n的棋盘，选取k格涂黑。如果一个格子有两个邻居是黑色的，就可以 : 把这个格
: 子涂黑。求证若要把整个棋盘涂黑，则开始至少要涂黑n个格子
　

ENG:

Problem:

A 2-D chessboard of size n*n. Initially, we choose k grids and color them black.

Then, if a grid has two or more neighbors(top,bottom,left,right) colored black

,we will color it black.

Prove, if we want to color all the grids into black, we should color at least n

grids initially.
　

My draft of solution(eng/chs)

================================================================

5 Travellers Patience

CHS:

: 13n张扑克，每堆n张，其他规则都一样
: 现在假设已经读入了输入，就是每堆有什么牌，和牌从上到下的顺序
: 找一个o(n)算法判断是不是能胜。
: 注意是o(n)不是O(n)!
　

: 有这样一个游戏?/span>travellers patience?#12290;52张扑克，A-K各4张
: 现在将这52张牌分成13堆，每堆4张，都是背面向上。
: 如此继续，直到我们不能继续。如果我们翻开所有的牌，我们就赢了。
: 问，如果牌的顺序是随机的 （既牌的分堆和每堆中牌的顺序），问我们赢的概率。
　

My draft of solution(chs)

==============================================================

*6 lonely runner problem

An open problem: lonely runner problem

Suppose there is a circular track with length 1. There are n runners on the
track, each running at different and constant speeds. At any given time, a
runner is lonely if the runner is 1/n or a greater arc distance away from
all other runners. The problem states that every runner is eventually
lonely for all n and for all combinations of speeds.

Can you prove a weaker result if we change the distance 1/n
to 1/(2n)?(easy)

Remark:
The assertion has been proved for n up to 5.
for n=2,3 you can easily check the conjecture is right.
for n=4,I dont know if there is a simple proof.
for general n, it is still open.
==============================================================

*7 2-D grid Guard Problem

CHS:

一个2维网格，边界可以是任意形状，现在要往网格中放一些guard，每个guard可以看到
水平方向和垂直方向的所有网格（但不能跨越边界）。现在要求放最少的guard，来观察
到所有的网格。

例：
            口
      口口口?#21475;
口口口?#21475;  口
      口    口
      口

ENG:

A simple connected(without holes) defined in the 2-d grid,  we want to place some guard in some grids. A guard can see all grids in horizontal and vertical direction (without crossing the boundary). The objective is to minimize the number of the guard to guarantee there is no grid that can not be seen by any guards.

Can you find a polynomial algorithm or prove it is np-hard?

eg:

               [ ]

   [ ]      [ ][*][ ][ ][ ][ ][ ]

[ ][*][ ][ ][ ][ ]

   [ ]         [ ]

               [ ]

Remark: to the best of my knowledge, it is unsolved.

============================================================

8 Chameleans Problem

At one point, a remote island's population of chameleons was divided as follows: 13 red chameleons, 15 green chameleons, 17 blue chameleons. Each time two different colored chameleons would meet, they would change their color to the third color. Is it ever possible for all chameleons to become the same color? Why or why not?

From http://www.ics.uci.edu/~dan/class/UniStu3

Remark: This is a easy one.

============================================================

*9 Rectangle cover Problem

Given N points in the unit square [0,1]x[0,1], including the origin (0,0) as one of the N points. Can you construct N rectangles, contained in the unit square, with sides parallel to the coordinate axes, pairwise non-intersecting, such that each of our N given points is the lower-left-hand corner of one of the rectangles, and such that the total area of the rectangles is at least 1/2?<\p>

For example, N=3 and the points are (0,0), (0.2,0.4) and (0.8,0.6). The three rectangles could be [0,1]x[0,0.39], [0.2,0.79]x[0.4,1], and [0.8,1]x[0.6,1]. Their areas are 0.39, 0.354 and 0.08, summing to 0.824, which is larger than 1/2.

(We allow degenerate rectangles -- a point or a line segment -- but still do not allow them to intersect with other rectangles, even in a single point.)

Your challenge: either prove that such a construction is always possible, or give a set of N points (including the origin) for which it is impossible. Caveat: To the best of our knowledge, the problem is unsolved.

From "IBM ponder this" 2004 June http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/June2004.html

Remark: This problem is very interesting, it seems easy. but it turns out hard...I and my colleagues try this problem many times but failed eventually...

============================================================

10. 100 hats.....

There are 100 persons. Each of them wears a hat. Each hat has a color chosen from 1 to 100. (one color can appear several times). Now every body can see others' hats except him\herselfs. Now, everybody has to guess the color of his\her own hat simultaneously. They can cooperate before wearing the hats, but after that they can not discuss any more. Give a strategy which guarantees at least one person's guess is right.

Remark: there is a simple tricky solution.

============================================================

11. 100 Cards.....

The names of 100 people (all names are different) are written on 100 cards. The 100 cards are taken to a closed room, randomly shuffled and put face down in a row. Each person in turn enters the room and turns over cards one after another until either he finds the card with his name or he has turned 50 of the 100 cards. After that he leaves the room, without communicating anything to the others, and the cards are all turned back face down before the next person comes in. How large can they make the probability that everyone will find the card with his name? (If everyone turns 50 cards at random, the probability will be (1/2)^100, which is about 8 * 10^(-31)). Notes: * They can coordinate before the game starts; there is no communication (neither explicit nor hidden - such as moving cards, etc.) during the game. * No need to find the precise maximum; just try to make the probability as large as you can. * What happens as the number of people increases?

Remark: From http://www.ma.huji.ac.il/~hart/puzzle/100.html

=============================================================

12. Euclidean spanning tree with degree constraint

CHS:

给出平面上n个点，以及这些点的权值，求出这些点的一棵生成树，边为直线段。要求每个点的度数正

好是对每个点给出的权值，以及平面上的边不能相交...
　

ENG:

given n points in the euclidean plane. For every point v, we associate it with a positive integer number

d(v). We want to compute a spanning tree of these point such that

(1) edges are straight lines.

(2) no edge crossing is allowed.

(3) For every v in the plane, the degree of v in the spanning tree equals to the given d(v).

Could you give a polynomial algorithm?

Remark: Some problem in ACM/ICPC. Nontrivial solution.

Solution

21. Ten Knights(2008-07-01)

22. Largest and Smallest Piece.(2008-07-01)

(a Asymptotic answer would suffice, for eg: \Omega(1/n))

Remark: From IBM Ponder This.