Permutation Math Olympiad Question (Challenging)

March’s Problem of the Month was a tough one on permutations. Only six people solved it! (Site: http://www.fen.bilkent.edu.tr/~cvmath/Problem/problem.htm)

The question goes as follows:

In each step one can choose two indices $1\leq k,l\leq 100$ and transform the 100 tuple $(a_1, \cdots, a_k, \cdots, a_l, \cdots, a_{100})$ into the 100 tuple $(a_1, \cdots, \frac{a_k}{2}, \cdots, a_l+\frac{a_k}{2}, \cdots, a_{100})$ if $a_k$ is an even number. We say that a permutation $(a_1, \cdots, a_{100})$ of $(1, 2, \cdots, 100)$ is good if starting from $(1,2,\cdots, 100)$ one can obtain it after finite number of steps. Find the total number of distinct good permutations of $(1, 2, \cdots, 100)$ .

The official solution is beautiful and uses induction.

Personally, I used a more brute force technique to get the same answer using equivalence class theory which I learnt in my first year of undergraduate math! It is not so bad in this question, since n is only 100, but for higher values of n the approach in the official solution would be better.

If you are looking for recommended Math Olympiad books, check out this page. In particular, if you are looking for more Math Olympiad challenges, do check out this book Mathematical Olympiad Challenges. In fact, any book by Titu Andreescu is highly recommended as he is the legendary IMO (International Math Olympiad) coach that led the USA team to a perfect score!

Author: mathtuition88

Math and Education Blog View all posts by mathtuition88

3 thoughts on “Permutation Math Olympiad Question (Challenging)”

Haha, I would have also use the equivalence class theory to solve this question if I encountered it. But yeah, it would be ridiculously tedious to solve it if n is higher…

I’ll have a closer look to their official solution, it seems interesting.

LikeLiked by 1 person

mathtuition88 says:

April 4, 2015 at 12:18 am

Yeah, their official solution is awesome! It didn’t cross my mind to use the cyclic permutation, so I solved it using a more tedious way.
Thanks for commenting!

LikeLiked by 1 person

Reply
1. abyssbrain says:
  
  April 4, 2015 at 12:19 am
  
  Yeah, that approach was very nice indeed
  
  LikeLiked by 1 person

Share this:

Like this:

Related

Author: mathtuition88

3 thoughts on “Permutation Math Olympiad Question (Challenging)”

Leave a Reply Cancel reply