MathDB

2

Part of 2023 Tuymaada Olympiad

Problems(2)

Magic trick on flipping a binary string

Source: Tuymaada 2023 Junior P2

7/12/2023
Serge and Tanya want to show Masha a magic trick. Serge leaves the room. Masha writes down a sequence (a1,a2,…,an)(a_1, a_2, \ldots , a_n), where all aka_k equal 00 or 11. After that Tanya writes down a sequence (b1,b2,…,bn)(b_1, b_2, \ldots , b_n), where all bkb_k also equal 00 or 11. Then Masha either does nothing or says “Mutabor” and replaces both sequences: her own sequence by (an,an−1,…,a1)(a_n, a_{n-1}, \ldots , a_1), and Tanya’s sequence by (1−bn,1−bn−1,…,1−b1)(1 - b_n, 1 - b_{n-1}, \ldots , 1 - b_1). Masha’s sequence is covered by a napkin, and Serge is invited to the room. Serge should look at Tanya’s sequence and tell the sequence covered by the napkin. For what nn Serge and Tanya can prepare and show such a trick? Serge does not have to determine whether the word “Mutabor” has been pronounced.
combinatoricsJuniorBinaryTuymaada
Weird identity for a graph

Source: Tuymaada 2023 Senior P2

7/7/2023
In a graph with nn vertices every two vertices are connected by a unique path. For each two vertices uu and vv, let d(u,v)d(u, v) denote the distance between uu and vv, i.e. the number of edges in the path connecting these two vertices, and deg⁡(u)\deg(u) denote the degree of a vertex uu. Let WW be the sum of pairwise distances between the vertices, and DD the sum of weighted pairwise distances: ∑{u,v}(deg⁡(u)+deg⁡(v))d(u,v)\sum_{\{u, v\}}(\deg(u)+\deg(v))d(u, v). Prove that D=4W−n(n−1)D=4W-n(n-1).
combinatorics