MathDB

7

Part of 2008 Ukraine Team Selection Test

Problems(1)

Graph

Source: Ukrainian TST 2008 Problem 7

2/12/2009
There is graph G0 G_0 on vertices A1,A2,…,An A_1, A_2, \ldots, A_n. Graph G_{n \plus{} 1} on vertices A1,A2,…,An A_1, A_2, \ldots, A_n is constructed by the rule: Ai A_i and Aj A_j are joined only if in graph Gn G_n there is a vertices Ak≠Ai,Aj A_k\neq A_i, A_j such that Ak A_k is joined with both Ai A_i and Aj A_j. Prove that the sequence {Gn}n∈N \{G_n\}_{n\in\mathbb{N}} is periodic after some term with period T≤2n T \le 2^n.
inductionpigeonhole principlenumber theorycombinatorics unsolvedcombinatorics