Решение задачи про полубокс

Обозначим полубоксы разбиения за B1, B2 … Bm. Наша задача показать, что m >= 2^n. Рассмотрим случайный полубокс S с нечетными длинами сторон и обозначим за Ck пересечение S с Bk (по каждой координате равноверотяно выбирается одно из нечетных непустых неполных подмножеств). Ясно, что Ck дают разбиение S на не пересекающиеся множества, значит хоть в каком-то из них должно быть нечетное число элементов.

Посчитаем вероятность того, что пересечение S с B1 нечетно. Это событие равносильно тому что пересечение по каждой координате Si с B1i нечетно, вероятность которого равна вероятности выбрать нечетное подмножество B1i (при равновероятном выборе любого подмножества) — а тут уже каждый может убедиться что это 1/2. Получается, что искомая вероятность это 1/2^n.

Теперь вероятность того, что хотя бы одно пересечение нечетно не превосходит m / 2^n. С другой стороны, она равна 1, конец.

Интересно, что я не умею решать эту задачу без трюка с нечестностью —хотя именно здесь он кажется мне достаточно контринтуитивным. Задача выглядит так, как будто бы должна несложно решаться по индукции, но мне доделать такой подход не удалось — буду рад, если кто-нибудь меня научит.