Quantitative Aptitude :: Permutation and Combination - Discussion

The answer should be 12 because we want the smallest set such that the remaining persons that are not in set must have shaken hands with at least one person in the set. Handshakes are in circular fashion i.e. {a1, a2}, {a2, a3}, ..., {a35, a36}, {a36, a1}, hence if we take a1 into set then we don't need to take a36 and a2 in the set, and the next element we should take in set is a4 (not a3 because a3 must have shaken hands with a4, also a5 must have shaken hand with a4). So the overall set becomes {a1, a4, a7, a10, a13, a16, a19, a22, a25, a28, a31, a34} i.e 12 elements or simply perform 36/3 = 12.