Q: For every positive integer n, determine the number of permutations (a1, a2, . . . , an) of the

set {1, 2, . . . , n} with the following property:

2(a1 + a2 + · · · + ak) is divisible by k for k = 1, 2, . . . , n.

A: For each n, let Fn be the number of permutations with the said property and call them 'nice'. For n = 1,2,3 every permutation is nice, so F1 = 1, F2 = 2, F3 = 6.

Now if we take an n > 3 and consider any nice permutation (a1, a2, ... an) of {1, 2, ... n}, then n-1 must be a divisor of the number.

We now rewrite the property for k = n-1 not in terms of a1, a2, an-1 but as the sum of 1, 2 ..n  and subtracting an. This gives us
 n(n+1) - 2an = (n+2)(n-1) + (2-an)
The last part (2 - an) must be divisible by n-1, hence it must be equal to 0, n-1 or 2n-2.
Each of these implies an is either 1 or (n+1)/2 or n

Similarly if we assume an = (n+1)/2, the permutation is nice taking k = n - 2, we get  that n-2 has  to be a divisor of
 2(a1+a2 ...+an-2) = 2((1+2+...+n)-an-an-1) = n(n+1) - (n+1)-2an-1
= (n+2)(n-2) + (3 - 2(an-1))
Since the last component has to be divisible by n-2, it is equal to 0 or n-2 or 2n-4. 0 and 2n-4 are excluded because 2 an-1 -3 is odd. The remaining possibility 2(an-1 -3 = n -2) leads to an-1 = (n+1)/2 = an which cannot be true. This eliminates (n+1)/2 as a possible value of an.

From the above two we are left with either an = 1 or an = n

If an  = n, then (a1, a2, ..., an-1) is a nice permutation of {1, 2 ... n-1}. There are Fn-1 such permutations. Attaching n to any one of them in the end, creates a nice permutation of {1, 2, .. n}

If an = 1, then a1 - 1, a2 -1, ... an-1 - 1 is a permutation of 1,2 ... n-1  It is also nice because the number resulting from the property = 2(a1 + ...+ak) - 2k which is divisible by k for k <= n -1

Here too any one of the nice permutations of Fn-1 nice permutations (b1, b2 ... bn-1) of {1,2 ...n-1} gives rise to a nice permutation of {1,2 ...n} whose last term is 1.

These observations show that there are Fn-1 nice permutations of {1,2 . ... n} exist both with the last term as 1 and the last term as n. Therefore there is a recurrence of Fn = 2 Fn-1 With the base value F3 = 6, we get the formula Fn = 3.2 ^ (n-2) for n>=3.

#puzzle
A king has ten slaves. He receives 60000 bottles of wine from a neighboring king. His advisors inform him that one of the bottles is poisoned but the rest are clean.How can the king find the poisoned bottle ? Assume the poison is highly potent and no matter the dilution will be fatal.
Answer He labels each bottle with their binary representation. Each of the ten slaves is assigned a position from 0 to 9. Each of them drinks from a bottle only when the bit corresponding to their position in set The order in which the slaves die yields the label of the poisoned bottle.