Разделы 
Дополнительно
Задача по математике - 3710
2019-06-16 
На карточках написаны числа, каждое из которых равно «+1» или «-1». Разрешается, указав три карточки, спросить: «Чему равно произведение чисел на этих карточках?» (сами числа нам не сообщают). Какое наименьшее число таких вопросов надо задать, чтобы узнать произведение чисел на всех карточках, если число карточек равно: а) 30; б) 31; в) 32? В каждом случае докажите, что меньшим числом вопросов обойтись нельзя.
г) По окружности написано 50 чисел, каждое из которых равно «+1» или «-1». Требуется узнать произведение всех этих чисел. За один вопрос можно узнать произведение трех стоящих подряд чисел. Какое наименьшее число вопросов необходимо задать?
Решение:
а) Разбиваем 30 чисел на 10 троек и узнаем произведения в этих тройках. Ясно, что меньшим числом вопросов не обойтись, так как каждое число должно входить в какую-нибудь тройку.
б) Произведение первых семи чисел находим, перемножив $a_1a_2a_3, a_1a_4a_5$, и $a_1a_6a_7$, а остальные 24 числа разбиваем на тройки, как в пункте а). И в этом случае ясно, что меньшим числом вопросов обойтись нельзя.
в) Произведение первых 5 чисел находим, перемножая $a_1a_2a_3, a_1a_2a_4$ и $a_1a_6a_7$, а остальные разбиваем на тройки.
Так как ясно, что всякое число должно входить в некоторую тройку, то вопросов заведомо не меньше 11.
При этом одно из чисел входит ровно в две тройки (если больше, чем в две, то найдется число, не входящее ни в одну из троек). В произведение всех И троек войдет квадрат этого числа и, следовательно, произведение всех чисел мы не узнаем.
г) За 50 вопросов мы узнаем произведения $a_1a_2a_3, a_2a_3a_4, a_3a_4a_5, \cdots, a_5a_1a_2$. Перемножив их, мы получим куб произведения всех чисел, который совпадает с самым этим произведением.
Меньше 50 вопросов недостаточно. Если, например, мы не знаем произведение какой-нибудь тройки $a_1a_2a_3$, то существуют два набора с разными произведениями, для которых произведения всех остальных троек совпадают: набор, в котором $a_1 = a_3 = a_6 = a_9 = \cdots = a_{48} = 1$, а остальные числа равны .-1, и набор из одних единиц. Все произведения первого набора, кроме $a_1a_2a_3$, равны 1. Во втором наборе все произведения равны 1.
Для $n$ чисел, среди которых можно узнать произведение любых трех, как в задачах а)-в), наименьшее число вопросов
равно: $k$, если $n = 3k$; $k + 1$, если $n = 3k + 1; k + 2$, если $n = 3k + 2$. Если же разрешается узнавать лишь произведение трех чисел, выписанных по окружности, то при $n$, делящемся на 3, надо задать $n/3$ вопросов, а при $n$, не делящемся на 3, - все $n$ вопросов.
Ответ: а) 10 вопросов; б) 11; в) 12; г) 50.
На карточках написаны числа, каждое из которых равно «+1» или «-1». Разрешается, указав три карточки, спросить: «Чему равно произведение чисел на этих карточках?» (сами числа нам не сообщают). Какое наименьшее число таких вопросов надо задать, чтобы узнать произведение чисел на всех карточках, если число карточек равно: а) 30; б) 31; в) 32? В каждом случае докажите, что меньшим числом вопросов обойтись нельзя.
г) По окружности написано 50 чисел, каждое из которых равно «+1» или «-1». Требуется узнать произведение всех этих чисел. За один вопрос можно узнать произведение трех стоящих подряд чисел. Какое наименьшее число вопросов необходимо задать?
Решение:
а) Разбиваем 30 чисел на 10 троек и узнаем произведения в этих тройках. Ясно, что меньшим числом вопросов не обойтись, так как каждое число должно входить в какую-нибудь тройку.
б) Произведение первых семи чисел находим, перемножив $a_1a_2a_3, a_1a_4a_5$, и $a_1a_6a_7$, а остальные 24 числа разбиваем на тройки, как в пункте а). И в этом случае ясно, что меньшим числом вопросов обойтись нельзя.
в) Произведение первых 5 чисел находим, перемножая $a_1a_2a_3, a_1a_2a_4$ и $a_1a_6a_7$, а остальные разбиваем на тройки.
Так как ясно, что всякое число должно входить в некоторую тройку, то вопросов заведомо не меньше 11.
При этом одно из чисел входит ровно в две тройки (если больше, чем в две, то найдется число, не входящее ни в одну из троек). В произведение всех И троек войдет квадрат этого числа и, следовательно, произведение всех чисел мы не узнаем.
г) За 50 вопросов мы узнаем произведения $a_1a_2a_3, a_2a_3a_4, a_3a_4a_5, \cdots, a_5a_1a_2$. Перемножив их, мы получим куб произведения всех чисел, который совпадает с самым этим произведением.
Меньше 50 вопросов недостаточно. Если, например, мы не знаем произведение какой-нибудь тройки $a_1a_2a_3$, то существуют два набора с разными произведениями, для которых произведения всех остальных троек совпадают: набор, в котором $a_1 = a_3 = a_6 = a_9 = \cdots = a_{48} = 1$, а остальные числа равны .-1, и набор из одних единиц. Все произведения первого набора, кроме $a_1a_2a_3$, равны 1. Во втором наборе все произведения равны 1.
Для $n$ чисел, среди которых можно узнать произведение любых трех, как в задачах а)-в), наименьшее число вопросов
равно: $k$, если $n = 3k$; $k + 1$, если $n = 3k + 1; k + 2$, если $n = 3k + 2$. Если же разрешается узнавать лишь произведение трех чисел, выписанных по окружности, то при $n$, делящемся на 3, надо задать $n/3$ вопросов, а при $n$, не делящемся на 3, - все $n$ вопросов.
Ответ: а) 10 вопросов; б) 11; в) 12; г) 50.
