Let \(G\) be a graph with 100! vertices, with each vertex labelled by a…
2018
Let \(G\) be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, … , 100. There is an edge between vertices 𝑢 and 𝑣 if and only if the label of 𝑢 can be obtained by swapping two adjacent numbers in the label of 𝑣. Let 𝑦 denote the degree of a vertex in \(G\), and 𝑧 denote the number of connected components in \(G\). Then, 𝑦 + 10𝑧 = _____.
Attempted by 60 students.
Show answer & explanation
Correct answer: 109
Key ideas: count the possible adjacent swaps for the degree, and use the fact that adjacent swaps generate all permutations to get the number of components.
Degree y: Each permutation has 100 entries in a row, and an edge exists for every swap of two adjacent entries. There are 99 adjacent pairs, and swapping any such pair gives a different permutation (all entries are distinct), so y = 99.
Number of components z: Adjacent transpositions generate the entire symmetric group on 100 elements (for example, bubble sort expresses any permutation as a sequence of adjacent swaps). Thus any permutation can be reached from any other by a sequence of adjacent swaps, so the graph is connected and z = 1.
Combine: y + 10z = 99 + 10·1 = 109.