Головоломка - все на решение
 

Начальник тюрьмы от скуки придумал такую игру:

В тюрьме сидят N заключенных. Их разводят по камерам, на каждой номер от 1 до N. Заключенные не знают номера. Затем в каждую камеру заходят и спрашивают "угадай номер своей камеры". Когда зэк говорит Х и ошибается, ему называют имя того, кто сидит в камере Х. Заключенному дается N/2 попыток.
Если все угадывают - всех отпускают. Если кто-то ошибается - всех казнят. Перед разводом по камерам заключенные могут собраться и выработать стартегию.
Обход камер делается не обязательно по порядку. И если кто-то не угадал обход прекращается ;)

Понятно, что шанс выйти на свободу без стратегии это (1/2)^M . Помогите заключенным увеличить шансы выйти на свободу.