Интересно (если, конечно, я прав): я поспешил и решил задачу неправильно, но ответ мой, по-моему, всё-таки правильный: капитан дает по одной монете старшим n/2 пиратам.
На самом деле просто произвольным n/2. Потому что больше одной монеты всё равно никому не получить, так что все получившие проголосуют за.