на первую страницу

Решения задач теоретического тура городской олимпиады по информатике 1998-99 г.

  1. Для этой страны 13 февраля - обычный день, т.к. для них он будет записан как 16 февраля (в 7 с/с), а 10-я олимпиада – не счастливая, т.к. она будет записана как 13-я (в 7 с/с).
  2. Отчество на Т имеет лишь два человека и только один имеет имя на Т, следовательно, мы получили кусочек дерева:

Отчество на Н и на К имеют, соответственно, только по два человека. Следовательно, мы можем дополнить наше дерево еще четырьмя именами:

БМ, НМ и КМ - листовые вершины, т.к. нет двух имен на М, следовательно, дерево приобретает следующий вид:

  1. Попугайчик Лори и Орленок Эд разные, т.к. они по-разному судят о Додо. Допустим Додо такой же как и Лори, значит он согласен с ним, что Орленок Эд не в своем уме. А Орленок Эд считает, что Додо в здравом рассудке, чего быть не может, т.к. иначе признает свою безумность.

Значит Додо такой же как Орленок Эд, а раз Эд считает, что Додо в здравом рассудке, то они оба должны быть в уме, а Попугай Лори - нет.

Данную задачу можно было решить и при помощи составления таблицы истинности.

Мы имеем три утверждения, истинность или ложность которых необходимо установить:

Попугай Лори в своем уме (ПЛвСУ), Орленок Эд в своем уме (ОЭвСУ), Додо в своем уме (ДвСУ).

Занесем их в таблицу истинности и рассмотрим все возможные варианты, их всего 8. Кроме того, у нас есть три суждения, которые должны быть истинны одновременно.

Додо считает, что Лори считает, что Орленок Эд не в своем уме, обозначим - ДсчЛсчОЭнеУ;

Лори думает что Додо не в своем уме - ЛдДнеУ;

Орленок Эд думает что Додо в своем уме - ОЭдДвУ

Нам необходимо заполнить таблицу истинности и в качестве решения взять ту строку, в которой три последних столбца имеют истинные значения.

ДвУ ЛвУ ОЭвУ ДсчЛсчОЭнеУ ЛдДнеУ ОЭдДвУ
0 0 0   0  
0 0 1   0  
0 1 0 0 1 1
0 1 1   1 0
1 0 0   1 0
1 0 1 1 1 1
1 1 0   0  
1 1 1   0  

Не обязательно заполнять всю таблицу. Можно начать со второго суждения, для третьего рассматривать только те строки, где второе суждение истинно, а для первого, где истинны второе и третье. В итоге получим единственную строку, в которой все три суждения приняли истинное значение, а именно в случае, когда Додо и Орленок Эд в своем уме, а попугайчик Лори - не в своем уме.

  1. Рассматривая пары примеров, в которых повторяются одинаковые слова: первую и пятую, вторую и шестую, - нетрудно установить следующее соответствие между шуганскими и русскими словами:

кузаа - кувшин гъев - крышка

хац - вода зимаадь - земля

чалак - ведро беечораа - бедняк

Однако в двух из этих четырех пар шуганские слова, которые переводятся русскими существительными в родительном падеже, стоят на первом месте в словосочетаниях (5 и 6 пары), а в двух других - на последнем (1 и 2 пары).

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

В 1 и 2 парах русские существительные в родительном падеже означают некоторое вещество, а существительные в именительном падеже - его меру, количество.

5 и 6 пары - обозначают принадлежность предмета, выраженного русским существительным в именительном падеже, предмету, выраженного русским существительным в родительном падеже.

Тогда 3 и 4 пары дают следующие русско-шуганские соответствия:

тамбал - бездельник

бююн - борода

бииг - горшок

дююнаа - зерно

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

чалак хац

беечораа дююнаа

тамбал кузаа

  1. В ячейку A2 поместить значение 1, а в ячейку А3 поместить формулу:

=ЕСЛИ(B3="";"";ЕСЛИ(A2="";A1+1;A2+1)) - в Excel,

IF(B3="","",IF(A2="",A1+1,A2+1) - в QuattroPRO

скопировав эту формулу в столбец вниз, получим автоматическую нумерацию требуемого вида.

  1. Пусть такой архиватор существует. Зафиксируем число N > 64К.

Тогда суперархиватор должен любой файл длины N сжимать в файл длины M<N. Всего файлов длиной меньшей N и не пустых:

, (1)

поскольку файлов длины M равно 2N .

(1) есть геометрическая прогрессия b1 = 2, q = 2, n = N-1.

Согласно формуле суммы геометрической прогрессии:

Итак, число файлов с длиной меньшей N, равняется 2N -2.

С другой стороны, число файлов с длиной равной N, есть 2N .

Таким образом, между файлами с длиной меньшей N и файлами с длиной равной N не может быть установлено взаимно-однозначное соответствие, а значит, невозможно однозначное восстановление некоторых сжатых файлов.

e-mail: mdia{at}cs.karelia.ru
(C) 2002-03 PetrSU