MathDB
Magic trick on flipping a binary string

Source: Tuymaada 2023 Junior P2

July 12, 2023
combinatoricsJuniorBinaryTuymaada

Problem Statement

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.
Back to ProblemsView on AoPS