Report problems, Design and Analysis of Information Systems'00

Problem 1.

We have a set of segments in a plane such that M pairs of them intersect each other at M points. Prove that we can color each segment red or blue such that the number of same-colored intersecting pairs is at most M/2.

Problem 2.

Alis and Bob play coin tossing game. Alis and Bob has N cents in the biginning, and at each round, the loser pays 1 cent to the winner. The game ends when one of them loses all the money. Prove that the game continues （N/log N)^2 rounds with a high probability. (Use Chernoff's theorem).

Problem 3.

In the above game, prove that the probability that game ends before 100N^2 rounds is at least 1/2.
Original idea is better (do not use the result of Problem 4 without mathematically proving it), but you may follow the steps below:

(1) Use Stirling's formula (see textbooks or handbooks in mathematics) to show that
the combination number of choosing 50N^2 from 100N^2 50N^2 is approximately (\pi/2)^{-1/2} 2^{100N^2+1} (10N)^{-1}　
(2) Prove that the probability that the game continues at 100N^2-th round is smaller than the number obtained by multiplying 2N/2^{100N^2} to the above combination number.
(3) Prove the statement by using (1) and (2)

Problem 4

In the coin toss game, the expected number of the rounds is N^2 (Shown in section 6 of Motowani-Raghavan, but not yet introduced in the course). Certify (or disprove?!) this by using a simulation program.

Problem 5

We want to open a door of a room of a wizard. There are 20 switches, and we need to on/off each of them to set every switch to the "correct position". The following statement is written on the door: " Until the door opens, a pair of switches is indicated such that at least one of them is in the wrong position." Do you think how many numbers of operations are required to open the door?

Hint: You can use the expectation number of coin toss game of Problem 5. Think that you get 1 cent if you set a switch to a correct poisiton, and lose 1 cent if you set to a wrong position.

Problem 6 （Unsolved Research　Problem, so you need not solve it before the deadline)

What happens if the statement is " Until the door opens, a triple of switches is indicated such that at least one of them is in the wrong position."

Problem 7

　 We have n pairs of line segments in a plane (hence, 2n segments in total). We want to select a suitable segment from each pair to have a set of n nonintersecting segments. Design an algorithm to decide whether such a selection exists or not with a high probability.
Hint: Use problem 5. A little difficult.

　Problem 8

Explain a problem (in computer science) that you are now interested in, so that Tokuyama can understand easily.