|
|
 |
Условие
На n карточках, выложенных по окружности, записаны числа, каждое из которыхРешение
Обозначим записанные на карточках числа через a1 , a2 , ... , an , а искомое число вопросов через p .
а) Прежде всего заметим, что каждое из данных чисел должно войти хотя бы
в одно из произведений, значения которых мы выясняем, задавая наши вопросы,
ибо в противном случае, изменив знак у числа, записанного на неиспользованной
карточке, мы изменим знак произведения всех чисел, сохранив при этом прежними
ответы на все заданные вопросы. (Это и показывает, что на основании
полученных ответов нельзя определить произведение всех чисел.) Поскольку одним
вопросом мы узнаем произведение трех чисел, то p
.
Если n=3k , то k вопросов достаточно. Выяснив, чему равны k произведений
a1 a2 a3 , a4 a5 a6 , a7 a8 a9 , ... , a3k-2 a3k-1
a3k , и перемножив полученные результаты, мы найдем произведение всех чисел.
Если n=3k+1 , то p k+1 . Покажем, что при k>1 за (k+1) вопросов
можно узнать произведение всех чисел.
Выясним, чему равны (k+1) произведений a1 a2 a3 , a1 a4 a5 ,
a1 a6 a7 , a8 a9 a10 , a11 a12 a13 , ... ,
a3k-1 a3k a3k+1 . В этих произведениях все числа, кроме a1 ,
участвуют по одному разу, а число a1 – три раза. Так как a13=a1 ,
то произведение полученных результатов равно произведению всех написанных
на карточках чисел.
Оставшийся не рассмотренным случай n=4 мы разберем ниже. В этом случае
задачаа) не отличается от задачиб).
Если n=3k+2 , то снова p k+1 . В этом случае произведение всех
написанных на карточках чисел можно найти, перемножив произведения
a1 a2 a3 , a1 a2 a4 , a1 a2 a5 , a6 a7 a8 , a9 a10
a11 , ... , a3k1 a3k+1 a3k+2 , и задав при этом k+2 вопроса
(в произведениях участвуют 3k сомножителей по одному разу, а сомножители
a1 и a2 – по три раза, т.е. 3k+6 сомножителей). Покажем, что
k+1 вопросов недостаточно.
В k+1 произведений входят 3k+3=n+1 сомножителей; но так как каждое из n
написанных на карточках чисел должно выйти хотя бы в одно из этих произведений,
то одно число (назовем его a ) входит в два произведения: abc и ade ,
а каждое из остальных чисел входит ровно в одно произведение. Но, заменив
числа a , b и d , мы не изменим ни одного из полученных ответов, изменив
при этом произведение всех написанных на карточках чисел; значит, на основании
полученных k+1 ответов нельзя определить это произведение.
Итак, ответ в задаче а) таков:
если n=3k , то p=k ,
если n=3k+1 , то p=k+1 (кроме случая n=4 ).
если n=3k+2 , то p=k+2 .
б) Если n=3k , то, как и в задачеа), p=k . Пусть n не делится на 3 .
Заметим, что в условиях задачиб) задавать вопросы можно о значениях лишь
таких n произведений:
Задав все n вопросов, мы узнаем куб произведения a1 a2 ... an ,
а значит, и само произведение– ведь оно равно 1 или -1 . Покажем, что
n-1 вопросов для нахождения произведения a1 a2 ... an недостаточно.
Задав n-1 вопросов, мы будем знать все произведения (*) , кроме одного.
Так как мы могли начать нумерацию карточек с любой из них, то можно считать,
что не задавался вопрос о значении произведения a1 a2 a3 .
Пусть n=3k+1 . Заменив на противоположные числа a2 и a3 , a5 и a6 ,
a8 и a9 , ... , a3k-1 и a3k , а также число a1 , мы
изменим знак всего произведения a1 a2 ... an (так как заменяются 2k+1
чисел). Но поскольку в каждом из произведении (*) , кроме произведения
a1 a2 a3 , о котором мы ничего не спрашиваем, меняются два сомножителя,
то мы об этой перемене знака всего произведения ничего не узнаем, задав n-1
вопросов.
Пусть n=3k+2 . Снова, заменив на противоположные числа a4 и a5 ,
a7 и a8 , a10 и a11 , ... , a3k+1 и a3k+2 и
a2 , мы изменим знак всего произведения a1 a2 ... an (так как
опять заменяется нечетное количество чисел) и снова об этой перемене мы не
узнаем, поскольку опять во всех произведениях (*) , кроме произведения
a1 a2 a3 меняется по два сомножителя.
Итак, ответ к задаче б) таков:
если n не делится на 3 , то p=n ;
если n делится на 3 , то p= .
Теперь мы видим, что в задачеа) при n=4 p=4 .
