В темной комнате вам вручают колоду карт, в которой N карт лежат рубашкой вверх, а остальные — вниз. Вы не можете видеть карты. Как вы разделите колоду на две стопки, чтобы в каждой из них было одинаковое число карт, лежащих рубашкой вверх?

Эта головоломка в своё время была популярна в JP Morgan Chase. Понятное дело, оказавшись в темноте, вы просто достанете сотовый телефон и воспользуетесь экраном как фонариком. Однако эта задачка появилась до эпохи сотовых телефонов, и её можно решить, даже не видя карт. Вполне вероятно, вы начнете со следующих наблюдений.

• При произвольном делении колоды вряд ли в каждой стопке окажется равное количество карт рубашками вверх (такое возможно, только если вам улыбнулась удача). Более того, все карты, лежащие рубашкой вверх, могут оказаться в одной стопке.
• В вопросе не говорится, что обе стопки должны быть равными, а только о том, что в них должно быть одинаковое количество карт рубашками вверх.
• Вы можете переворачивать карты. Конечно, у вас нет способа, подсказывающего вам, переворачиваете вы карты рубашкой вверх или вниз.

Ожидаемый ответ заключается в том, что вы должны отсчитать N карт, начиная с верха колоды, и перевернуть их. Это будет одна стопка. Оставшаяся часть колоды составит вторую стопку.

Объясним, почему это работает. В N картах, которые вы отсчитали, может быть любое число карт, лежащих рубашкой вверх, от нуля до N. Представим, что там было (до переворачивания) f таких карт. Перевернув карты, вы добились, что каждая карта рубашкой вверх становится картой рубашкой вниз и наоборот. Поэтому вместо f карт рубашкой вверх вы приходите к варианту N-f карт рубашкой вверх в этой стопке.

В другой стопке, в которой содержится остаток колоды, имеется N карт, лежащих рубашкой вверх, за минусом тех f, которые вы отсчитали. Это то же самое количество, как в первой стопке с перевернутыми картами.

Разбор взят из книжки «Are You Smart Enough to Work at Google?».