Maths Olympiad Prep

Library / /8 of 46

Combinatorics Difficulty 5.2 AIME, harder Prove it Russia

A Magician performs the following trick. He lays out 36 cards in a 6×66 \times 6 square (6 columns of 6 cards) and asks the Spectator to select (mentally) a card and remember the column containing it. Then the Magician collects the cards, and again lays out the cards in a 6×66 \times 6 square. After that the Magician asks the Spectator to tell which columns contained the selected card in the first and in the second case, and then guesses the selected card. Find a way for the Magician to perform this trick. (L. Emelyanov)

Фокусник выкладывает 36 карт в виде квадрата 6 × 6 (в 6 столбцов по 6 карт) и просит Зрителя мысленно выбрать карту и запомнить столбец, её содержащий. После этого Фокусник определённым образом собирает карты, снова выкладывает в виде квадрата 6 × 6 и просит Зрителя назвать номера столбцов, содержащих выбранную карту в первый и второй раз. После ответа Зрителя Фокусник безошибочно отгадывает карту. Как действовать Фокуснику, чтобы фокус гарантированно удался? (Л. Емельянов)

Solution

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.