ZIO 2016 Question 3 (India)

The King of Zyorg has a cabinet with N ministers and they have assembled for a meeting. The King enters the meeting chamber to find that the ministers have arranged themselves so that friends sit with friends.

The seats are numbered 1 . . . N and we refer to the minister sitting on the i th seat in this initial arrangment as i. So, the initial arrangment is of the ministers is (1, 2, 3 . . . N).

The King orders the ministers to rearrange themselves and finds that some of the friends have just exchanged seats. The enraged King then orders that they must rearrange themselves so that for every k < N the set of ministers sitting in the first k chairs DOES NOT consist only of the ministers 1, 2, . . . k.

He then wonders if this is possible at all and quickly convinces himself that this is so. Then he wonders how many different ways can they rearrange themselves fulfilling his order.

For example, suppose N = 3. The initial arrangment is of course (1, 2, 3). If they rearrange themselves as (2, 1, 3) this will violate the King’s order because for k = 2 the ministers in positions 1 upto 2 are {1, 2}. On the other hand the arrangement (3, 1, 2) fulfils the requirement. For k = 1 we have {3}, for k = 2 we have {3, 1}. You can check that there are exactly 3 arrangments that comply with the King’s order. They are : (2, 3, 1),(3, 1, 2) and (3, 2, 1). So, for N = 3 the answer to this problem is 3.

Your task is to write out the answers for 3 values of N.

(a) N = 5

(b) N = 6

(c) N = 7

Read more…(305 words)

About the author:

TP

Tushar Patel

Loading…

Join the discussion. Add a reply…

Post

About the author

TP

Tushar Patel

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.