Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2000/02/kv0200kotova.pdf Дата изменения: Fri Dec 23 19:25:43 2005 Дата индексирования: Tue Oct 2 00:34:30 2012 Кодировка: Windows-1251 Поисковые слова: р р с с р с р р р р с р р р р р р п п р

'КВАНТ'

ДЛЯ

МЛАДШИХ

ШКОЛЬНИКОВ

23

Награда калифа
А.КОТОВА
Ходжа Насреддин обставил его в той самой науке, в которой он полагал себя сильнейшим и несравненным.1 'Ну погоди же, думал он, я задам тебе задачку, которая будет тебе не по силам, и докажу мое превосходство в премудростях'. Поэтому он проглотил обиду, огладил бороду и с важностью сказал: Что ж, я не сержусь на тебя, хотя следовало бы. Слушай же, я расскажу тебе одну поучительную историю. Некогда служил я при дворе знаменитого багдадского калифа Гаруна аль-Рашида. Он очень ценил меня и хорошо платил за предсказания, которые я превосходно умею делать, исходя из положения звезд
1 См. 'Квант' ?1 за этот год.

Г

УССЕЙН ГУСЛИЯ БЫЛ ГЛУБОКО УЯЗВЛЕН ТЕМ, ЧТО

Да-да, помню, негромко заметил Ходжа Насреддин, звезды Сад-ад-Забих противостоят Меркурию, а звезды Сад-ад-Сууд совпадают со звездами Сад-альАхбия Старый звездочет зашипел от злости: Сколько раз я говорил тебе, что звезды Сад-адСууд не могут совпасть со звездами Сад-аль-Ахбия, ибо находятся в одном созвездии с ними, о невежда, сын невежды, внук и правнук невежды!.. Но сейчас речь не о том. Случилось так, что любимая жена великого калифа ожидала ребенка, а ему очень нужен был наследник. И вот калиф (да продлятся дни его бесконечно!) призвал меня и второго астролога, а вторым астрологом был тогда знаменитый Гассан Абдурахман ибнХоттаб, и велел нам составить гороскоп будущего ребенка. Но разве можно составить точный гороскоп


24

КВАНT 2000/?2

того, чей день и час рождения еще неизвестен? И вот мы с Гассаном удалились каждый в свои покои, наблюдали звезды и вычисляли; когда же гороскопы были готовы, оказалось, что мой предсказывает калифу рождение дочери, а гороскоп Гассана рождение сына. Мы долго спорили в чайхане, чье предсказание точнее, но я так и не смог убедить Гассана, а он меня. 'Но что же мы скажем светлейшему калифу? увещевал я его. Если мы ошибемся, повелитель разгневается'. Догадываюсь, вставил Ходжа Насреддин. Нашелся умный человек, подсказавший вам выход. Гуссейн Гуслия с подозрением посмотрел на Насреддина. 'Ты-то как догадался? подумал он. Уж не было ли тебя в той чайхане?' Ты угадал, сказал он. Какой-то незнакомец посоветовал нам поднести калифу оба гороскопа, а награду, которую получит тот из нас, кто окажется прав, разделить между собой. Мы договорились, что тот, чей гороскоп окажется верным, получит большую часть награды, но и другой не останется в накладе. Вскоре долгожданный младенец родился. Увы мне это был мальчик! Гассан получил в дар от калифа десять кошельков, а я ничего. И вы отправились делить деньги, подсказал Насреддин. Разумеется, мы отправились делить деньги! Но когда мы открыли кошельки, оказалось, что один из них пуст, во втором одна таньга, в третьем две и так далее. Мы подарили два кошелька нашему советчику, который снова околачивался в чайхане Вы предпочли бы, чтобы его там не было, заметил Насреддин. Аллах покарает твой злой язык! возмутился Гуссейн Гуслия. Мы честно заплатили тому оборванцу! Остальные же кошельки мы поделили по уговору ибн-Хоттаб получил большую часть. Но тут в чайхану ввалился его брат Омар Юсуф, известный своим завистливым и склочным нравом, увидел кошельки и потребовал часть денег себе. Я принялся

увещевать его, мы поссорились, и Омар Юсуф да будет он проклят! отнял у меня четыре кошелька. Мне осталось всего лишь 10 таньга. Скажи же теперь, если ты так умен, каким хочешь казаться, сколько мы заплатили незнакомцу за совет? Твоя загадка совсем проста, сказал Ходжа Насреддин. Раз у тебя осталось 10 таньга, они лежали по крайней мере в двух кошельках. Поскольку 4 кошелька у тебя отнял Омар Юсуф, ты получил при дележе не меньше 6 кошельков. В шести же кошельках денег не меньше, чем 15 таньга (ведь 0 + + 1 + 2 + 3 + 4 + 5 = 15). Но ибн-Хоттабу досталось не меньше, чем тебе, значит, у него было не меньше двух кошельков. Поскольку еще 2 кошелька получил ваш советчик, у Гассана было ровно 2 кошелька, а у тебя ровно шесть. Значит, у Гассана в двух кошельках было больше денег, чем у тебя в шести, 16 или 17 таньга (ведь 8 + 9 = 17, большей суммы в двух кошельках найти нельзя). Раз у тебя в конце концов осталось 10 таньга, у тебя не могло быть кошельков с 0, 1, 2, 3, 4 и 5 таньга из них нельзя выбрать два с десятью монетами. Значит, у тебя было больше 15 таньга, но меньше, чем у Гассана, т.е. у тебя было 16 таньга, а у него 17. Так что у него были кошельки с 8 и 9 таньга, у тебя с 0, 1, 2, 3, 4 и 6, а незнакомцу достались кошельки с 5 и 7 монетами. Что-то слишком быстро ты ответил, недовольно проворчал Гуссейн Гуслия. Ты не вычислял, какие у меня были кошельки, ты угадал! Видишь ли, почтенный, сказал Ходжа Насреддин, мне не было нужды считать. Я-то прекрасно помню, что получил 12 таньга и неплохо обедал на них четыре дня. О горе мне! вскричал звездочет. Надо же мне было вспомнить историю, в которой участвовал ты сам! Не огорчайся так, утешил его Ходжа Насреддин. Ведь тогда мы не были с тобой знакомы, о великий Гуссейн Гуслия!

НАМ ПИШУТ

Еще раз о малой теореме Ферма
Пусть p простое число. Малая теорема Ферма гласит: если a целое число, не кратное p, то a p-1 кратно p, т. е. число p -1 - 1 p целое. Я хочу обратить внимание на fa = a интересное свойство:

откуда f ab = f a + f b + pf a f b f a + f b

b g bg bg

bgbg bg bg b

mod p .

Р.Пименов

g

bg e

j

f ab f a + f b

b g bg bg b
p -1

mod p

g

Информацию о журнале 'Квант' и некоторые материалы из журнала можно найти в ИНТЕРНЕТЕ по адресам: Курьер образования http://www.courier.com.ru Vivos Voco! http://www.techno.ru/vivovoco (раздел 'Из номера')

для любых целых чисел a и b, не кратных числу p. Доказать p -1 его проще всего, перемножив равенства a = 1 + pf a , p -1 = 1 + pf b . А именно, b

1 + pf ab = ab

bg bgbg

=a

p -1 p -1

b

= 1 + pf a 1 + pf

c

b ghc

bg bb gh ,