PUMaC 2021 · 组合（A 组） · 第 3 题

(3) (4) n − 1 n − 1 n − 1 4 } , C = { a | 1 ≤ i ≤ 4 } , and D = { a | 1 ≤ i ≤ 4 } . i i Let b , b , b , b be an arbitrary quadruple. We analyze this quadruple based on the sets 1 2 3 4 A, B, C, D in which b , b , b , b lie and split into cases. For example, if all b ∈ A , we denote 1 2 3 4 i this case as ( A, A, A, A ). Case 1: ( A, A, A, A ). In this case, the answer is f ( n − 1), inductively. Similarly, for all other cases ( B, B, B, B ), ( C, C, C, C ), ( D, D, D, D ) we have the same answer. Case 2: ( A, B, B, B ). As the induced graphs on A, B, C, D are isomorphic, fix an isomorphism φ taking B to C . Then, the idea is that exactly half of all quadruplets on the sets ( A, B, B, B ) or the sets ( A, C, C, C ) have an odd number of edges. Why is this? If a quadruple ( b , b , b , b ) ∈ 1 2 3 4 ( A, B, B, B ) has an odd number of edges, then ( b , φ ( b ) , φ ( b ) , φ ( b ) has an even number of 1 2 3 4 edges and vice versa. (This is because the existence of exactly three edges changed between the two quadruples, namely the edges between b and the rest). 1 One can apply the same argument to all other cases of the form ( A, D, D, D ), ( B, C, C, C ), etc, to get that exactly one half of all quadruples have an odd number of edges. Case 3: ( A, A, B, C ). The induced graph on A has exactly half of the edges of the complete graph on the same number of vertices. Therefore, by going through all pairs ( a , a ) for the 1 2 A -vertices, we get again that exactly half of all possible quadruples have an odd number of edges. Case 4: ( A, A, B, B ) similar to the previous one, by the same argument. 4( n − 1) Case 5: ( A, B, C, D ) - all quadruples of this type work, so we have 4 contribution. 4( n − 1) In total, we have 4 f ( n ) for the case 1, density 1 / 2 for cases 2 through 4 and 4 for case 5. Therefore the final recurrence is h i n n − 1 1 4 4 4( n − 1) 4( n − 1) f ( n ) = 4 f ( n − 1) + 4 + − 4 − 4 , 2 4 4 with the initial terms f (0) = 0 , f (1) = 1. 5