MathDB
Operation on string

Source: STEMS 2021 CS Cat A Q5

January 23, 2021
combinatorics

Problem Statement

Given a string of length 2n2n, we perform the following operation:
[*]Place all the even indexed positions together, and then all the odd indexed positions next. Indexing is done starting from 00.[/*]
For example, say our string is ``abcdef''. Performing our operation yields ``abcdef'' →\to ``acebdf''. Performing the operation again yields ``acebdf'' →\to ``aedcbf''. Doing this repeatedly, we have:\\ ``abcdef'' →\to ``acebdf'' →\to ``aedcbf'' →\to ``adbecf'' →\to ``abcdef''.\\\\ You can assume that the characters in the string will be unique. It can be shown that, by performing the above operation a finite number of times we can get back our original string.\\\\ Given nn, you have to determine the minimum number of times the operation must be performed to get our original string of length 2n2n back.\\\\ In the example given above, 2n=62n = 6. The minimum steps required is 44.
Back to ProblemsView on AoPS