Q.

In the game of dominoes we have a collection of domino tiles, which are rectangular tiles with two numbers on them, one on each end. An arrangement of the dominoes in a line isvalidif adjacent numbers are equal. For example, given dominos (0, 1), (0, 3), (0, 4), (1, 3), we can arrange them in a valid line (0, 1)(1, 3)(3, 0)(0, 4).

a) A (i,j) domino is a domino tile with numbersiandjon it. Given a set of 100 dominoes with numbersiandj, where1 i 10and11 j 20, show that it is possible to arrange all 100 dominoes in a valid line.

-> I think yes it can be done because all numbers from 1 to 20 has 10 each and can be paired up as (i,j) can be also denoted as (j, i)

i.e. (1,11)(11,2)(2,12)(12,3), ...., (20,1)

b) Suppose that one of these 100 dominos is missing. Show that it is still possible to arrange all of the remaining dominos in a valid line.

c) What if two dominos are missing? Can we still arrange the rest in a valid line? Prove your answer.