Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Решения

1(3 балла). У лифта на первом этаже 18-этажного дома собрались 17 школьников, всем из них нужно подняться вверх, причём всем на разные этажи. Лифтёр же согласился сделать только один рейс на любой этаж, а дальше пусть они идут пешком. Не смотря на это, все они решили ехать на лифте. Известно, что все школьники спускаются с одинаковым неудовольствием на один этаж вниз и с двойным неудовольствием поднимаются пешком на один этаж вверх. Какой этаж нужно выбрать, чтобы суммарное неудовольствие было наименьшим?

(Малеев А., студент 5 курса ФИВТ)

Решение:

Из условия следует, что на каждом этаже живёт ровно по одному школьнику. Пусть n – искомый номер этажа. Тогда школьнику, живущему на этом этаже, не нужно не подниматься вверх, не спускаться вниз. Вверх же нужно подняться всего 18-n школьникам, на 1, 2, 3, …, 18-n этажей соответственно. Вниз придётся спускаться n-1 школьнику, на 1,2,3,…, n-1 этажей. Подсчитаем общее количество неудовольствий с учётом того, что подниматься вверх школьник не любят в двойне:

Заметим, что минимум полученного квадратного трёхчлена достигается в точке n= . В силу того, что n – целое, а также парабола имеет ось симметрии, лифт должен подняться на 13 этаж. Ответ: на 13 этаж.

Критерии:

Подсчет общего количества неудовольствий.................................................................................................... 2

Нахождение минимума 12,83............................................................................................................................ 0,5

Приближение соответствующее симметрии................................................................................................... 0,5

2(4 балла). Обкладками сферического конденсатора являются две концентрические металлические сферы радиусами r и R (r < R). Конденсатор зарядили до напряжения U­0, а затем с помощью перекидного ключа, начали поочередно заземлять обкладки конденсатора, как показано на рисунке. Первой заземлили внутреннюю обкладку, затем внешнюю, потом снова внутреннюю и т.д. В итоге каждую из обкладок заземлили N раз. Найдите конечные заряды  на внутренней и внешней обкладках соответственно.

(Чудновский А., преподаватель кафедры общей физики МФТИ)

 

Решение:

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

откуда

Полученное выражение можно было записать сразу, воспользовавшись формулой для ёмкости сферического конденсатора:  При заземлении проводника его потенциал становится равным потенциалу бесконечно удалённого тела, который в соответствии с формулой ϕ(x) = kq/x равен нулю. Следовательно, заряд обкладки после каждого заземления можно найти из условия равенства нулю её потенциала:

Расчёт зарядов после второй пары заземлений полностью аналогичен:

Обобщая результаты для n пар заземлений и подставляя Q0 из (1), получим  Отметим, что в условии не сказано, какая из обкладок была изначально заряжена положительно, а какая — отрицательно. В решении мы предположили, что  > 0, а < 0. Если же это не так, то все ответы поменяют знак.

Критерии:

Найдены ................................................................................................................................................... 1

Найдены .................................................................................................................................................... 2

Обобщение............................................................................................................................................................. 1

 

3(4 балла). Имеется банка с белой краской, банка с черной краской и ложка, объем которой в 1000 раз меньше объема краски в банке. Студент факультета инноваций и высоких технологий Рома придумал инновационную технологию получения серой краски заданной концентрации: за одно переливание Рома зачерпывает ложку краски из первой банки, выливает ее во вторую, перемешивает, а затем зачерпывает ложку краски из второй банки и выливает ее в раковину. За сколько таких переливаний Рома добьется того, что концентрация белой краски будет наиболее близка к 1/4?

 (Жернов А., призёр международной олимпиады по физике, студент 1 курса ФИВТ)

Решение:

Пусть объем ложки , начальный объем краски во второй банке – .

После того, как Рома перельет ложку белой краски во вторую банку, в ней окажется  белой и черной краски. Значит, общий объем краски станет равен . Если после перемешивания зачерпнуть ложку из второго сосуда, то доля черной краски в ней будет составлять: . А так как объем ложки равен , то объем черной краски в ложке составит . Это означает, что черной краски во второй банке останется . Продолжим наши исследования: добавление ложки белой краски => всего краски во второй банке стало . После перемешивания и зачерпывания доля черной краски в ложке составляет . Следовательно, объем черной краски в ложке составляет . Значит, после выливания ложки краски в раковину объем черной краски в сосуде станет равным . Можно заметить, что объем черной краски во второй банке согласуется со следующей последовательностью: ,      ,      …

Итак, можно выдвинуть гипотезу, что после  переливаний объем черной краски во второй банке станет равным: . Докажем это методом математической индукции: база уже получена; пусть после n переливаний объем черной краски равен , но, понятно, что объем всей краски во второй банке составляет . После добавления ложки белой краски, объем всей краски станет равным . Зачерпываем ложку, доля черной краски в ней составляет: . Значит, объем черной краски в ложке равен    =>   после выливания ложки в раковину черной краски осталось . Индукционный переход завершен.

Итак, после n переливаний во второй банке будет  черной краски. По условию необходимо, чтобы черной было в три раза больше => . Получаем .

Критерии:

Концентрация после одного переливания......................................................................................................... 1

Индукция по числу переливаний........................................................................................................................ 2

Ответ....................................................................................................................................................................... 1

 

4(3 балла). Дан четырехугольник ABCD, вписанный в окружность. Биссектрисы улов В и С пересекаются в точке L, лежащей на отрезке AD. Известно, что АВ=5 см, СD=3 см. Найдите AD.

(Шевченко А., студент 3 курса ФУПМ)

A

B

C

D

L

K

Решение:

Опишем около треугольника BCL окружность S. Пусть она пересекает AD в точке К. Пусть ÐABC = 2х, ÐBCD=2y. Тогда ÐBAD=p-2y, т.к. ABCD вписанный.ÐBKL=ÐBCL, так как они опираются на одну дугу. Рассмотрим случай, когда L лежит между А и K. Другой случай рассматривается аналогично. Из подсчета углов треугольник АВК равнобедренный, значит АВ= ВК.ÐKBL=y-x=ÐLCK, так как они опираются на одну дугу. Значит ÐDCK=х. ÐСDA=p-ÐАВС=p-2x, значит и треугольник CDK равнобедренный и CD=DK. Так как АВ= ВК, тоАВ+CD=AD=8см. Еще надо доказать, что точка К лежит на отрезке AD. Это следует из того, что AD не может проходить внутри угла BLC, а значит, она пересекает окружность S на той же дуге, что и точка L. Значит на отрезке AD

 

Критерии:

Доп. построение.................................................................................................................................................... 1

Подсчет углов ....................................................................................................................................................... 1

Рассмотрение всех случаев................................................................................................................................... 1

5(5 балла). Даны n куч камней: по 1, 2, …, n камней в каждой. Разрешается из кучи с четным числом камней переложить половину камней в любую другую. Какое наибольшее число камней можно собрать в одной куче?

 (Стебелев М., студент 3 курса ФИВТ)

Решение:

Очевидно, в одной куче можно собрать не более, чем (во всех по одному, кроме одной, в которой остальные). С помощью метода математической индукции докажем, что для любого n из куч 2,3,…,n камней можно перекинуть  камней в кучу номер 1, т.е всегда можно собрать  камней в первой куче.

 База для n=3 очевидна: х,2,3 ® х,1,4 ® (х+2),1,2 ® (х+3),1,1.

 Индукционный переход: пусть для n-1 куч камней мы решили задачу, докажем для n куч. Найдем разницу между n и ближайшей к ней большей степенью двойки. Пусть она равна х. (т.е. n+x= ). Теперь разложим х в сумму степеней двойки. Далее найдём кучку, в которой камней (она есть, так как это число меньше n). В разложении -1 по степеням двойки входят все степени от 0 до k-2, а значит все те, что входят в разложение х, т.к. . Начинаем раскидывать кучу номер . Если степень k-2 входит в разложение x, то перекладываем первым ходом в кучку номер n, если нет – то в кучу 1. Так продолжаем, пока в кучке не останется 1 камень. В итоге у нас сколько-то камней в куче номер один, один камень в куче номер  и в куче номер n. Из кучи номер n переложим половину камней в первую кучку. В ней остается камней. Значит, у нас есть кучки с 1,2,…,n-1 камнями, из которых по предположению индукции можно переложить в кучку номер один камни так, чтобы в каждой осталось по одному камню.

Итак, доказано, что в кучку с одним камнем из кучек 2,3,…,n можно переместить камни так, чтобы в них осталось по одному камню. В итоге, в первой кучке камень, что и требовалось доказать.

Критерии:

Идея разложения остатка по степеням двойки............................................................................................... 2

Построение примера............................................................................................................................................. 1

Индукция................................................................................................................................................................ 1

Ответ....................................................................................................................................................................... 1

6(3 балла). В цилиндре с площадью основания S и высотой Н под невесомым поршнем находится идеальный газ. В начальный момент верхний край поршня совпадает с краем стенок цилиндра. На поршень начинают наливать воду с высоты h. Плотность воды , площадь сечения струи . Когда поршень опустился на половину высоты цилиндра, вода начала переливаться через край. Атмосферное давление . Найдите h. Процесс, происходящий в цилиндре считать изотермическим.

 (Савилов С., студент 3 курса ФИВТ)

Решение:

Пусть скорость воды у верхнего края цилиндра . За время ∆t на поршень упадет масса песка , которая передаст импульс . Значит, падающая вода создает давление . Так как поршень опустился на половину высоты цилиндра, то давление под поршнем равно . Давление над поршнем равно сумме атмосферного давления, давления падающей воды и давления воды, лежащей на поршне, масса которой . Получается уравнение

Из формул равноускоренного движения: .

Ответ:

Критерии:

Нахождение давления лежащего песка............................................................................................................ 0.5

Нахождение давления падающего песка............................................................................................................ 1

Нахождение давления внутри........................................................................................................................... 0.5

Формула равноускоренного движения............................................................................................................ 0.5

Ответ.................................................................................................................................................................... 0.5

 

7(4 баллов). Чтобы записать число  в системе счисления, образованной последовательностью , нужно представить его в следующей форме: , где  - члены образующей последовательности , - цифры числа  в этой системе счисления: . Например, в двоичной системе счисления образующая последовательность -  степени двойки: 1, 2, 4, 8, 16 и т.д. Если система счисления образована последовательностью натуральных чисел, то в ней один записывается как 1, два – как 10, три – как 100, четыре - как 1000 и т.д.

Рассмотрим последовательность простых чисел. В десятичной системе счисления она записывается следующим образом: 1,2,3,5,7,11,13,17,19,23,29,31,37,41… Ниже приведена запись первых членов этой же последовательности в других системах счисления:

1) 1, 10, 11, 101, 111, 1011, 1101, 10001, 10011, 10111, 11101, 11111, 100101

2) 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000

3) 10, 100, 1000, 10000, 10100, 101000, 1000000, 1001010, 1010010, 10000100, 10100000, 10100100, 100001000, 100010100, 100100010

4) 1, 10, 11, 21, 101, 121, 201, 221, 301, 321, 1021, 1101, 1201, 1221, 1301, 1321, 2021, 2121, 2201

В каждом случае найдите образующую последовательность системы.

 (Хамидулин А. 3 курс, ФИВТ)

Решение:

Все решения однообразны:  подставляя цифры числа и само число в это уравнение получаем систему из большого числа линейных уравнений. Чаще всего она решается очень просто. Например, пункт 4):

Узнаются факториалы натуральных чисел.

Ответы:

1) степени двойки: 1,2,4,8,16,32,64…

2) последовательность несоставных чисел 1,2,3,5,7,11,13,17,19,23,29,31,37,41…

3) последовательность Фибоначчи: 1,1,2,3,5,8,13,21,34,55,89…

4) последовательность факториалов: 1,2,6,24,120…

 

Критерии:

Пункт 1................................................................................................................................................................... 1

Пункт 2................................................................................................................................................................... 1

Пункт 3................................................................................................................................................................... 1

Пункт 4................................................................................................................................................................... 1

 

8(5 баллов). Из однородной проволоки сделан тетраэдр, на серединах его ребер построен октаэдр из той же проволоки, как показано на рисунке. Найдите сопротивление между двумя вершинами тетраэдра, если сопротивление его ребра равно r.

(Таранапольский Г., студент 4 курса ФОПФ)

Решение.

Занумеруем узлы фигуры (рис. 2). Сопротивление между любыми вершинами тетраэдра одно и то же. Найдем его между вершинами 1 и 8. Из симметрии следует, что ток между 2 и 3, 5 и 6 узлами течь не будет. Также можно разъединить узел 7. Фигура преобразуется (рис. 3). Аналогично, можно исключить ребра 9-7 и 7-10 и разъединить узел 4. (рис 4).

Таким образом .

Ответ: .

Критерии:

Объяснены все убираемые ребра и узлы............................................................................................................ 2

Составлена итоговая схема.................................................................................................................................. 1

Подсчет................................................................................................................................................................... 2

 

9(8 баллов). Даны примеры с числительными древнемарсианского языка. Знаки арифметических операций и знак равенства мы обозначили привычным образом, а пять символов, которые древние марсиане использовали для обозначения чисел, мы заменили на буквы F, L, R, X и Z. Все числа в примерах – целые, положительные и меньшие 100.

FFL * R = Z

FFRZX + F = ZF

FRX + FLZ = FFXXZ

RF * RF = FZ

FR * LF = LFXX

XXF + ZF = FFRXZ

FX + LF = LX

FL * RF = ZXF

FFR * L = LZX

RXZ + F = FRXZ

LX * L = LXZ

FFL + FXX = RFXX

Напишите тем же способом числа 17, 57, 38, 43, 21, 5 и 42.

(Задача предложена базовой кафедрой ABBYY)

Решение:

А) Заметим, что в примере 4 ( ) прибавленное число просто приписано впереди другого слагаемого. Можно провести аналогию с римской записью чисел.

Б) В примере 5 ( ) прибавление такого же числа F к числу FFRZX, уже содержащему два числа F в записи, заставило переписать число как ZF – возможно,  число Z большего порядка.

В) Предполагаем, что F не в начале, а в конце записи предполагает не прибавление, а вычитание числа F (как в примере 3 ( )).

Г) Из 2 примера ( ) следует, что число RF может равняться 2, 3, 4, 5, 6, 7, 8, 9.

А число ZF – 4,9,16,25,36,49,64,81.

 

Попробуем проверить гипотезы А), Б), В). Если они верны, то в примере 12 ( ) можно вычеркнуть число ХХ из левой и правой части – равенство не должно измениться. Тогда получим: FFL + F = RF

Применив гипотезы А) и В) получаем: F +F +L +F =R -F

Д)

Аналогично из примера 9 ( ) вычеркнем одинаковые числа в левой и правой частях равенства, учитывая, что их позиции одинаковы:

FRX + FL = FFXX

FR + FL = FFX

Е) R + L = X

Если подставим Д):  

Попробуем подставить все найденное в пример 8 ( ):

.  Т.к. в примере 1 , то   

подставляем Е):  Þ  

подставляем Д):  Þ

Ж)

Из Д) и Е) следует, что L < R < X

Предположим, что F = 1.

Попробуем подставить в Ж):

Решаем это квадратное уравнение, получаем два ответа для L - это 4 и -1.5.

Но т.к. все числа в примерах целые и положительные, то подходит только 4.

Тогда из Е) и Д) получаем R = 8, X = 12

А из 1 примера получаем  Z =(1+1+6)*8=48.

Получили такой порядок марсианских «цифр»:

F =1      L =4            R =8       X =12     Z =48

Величина задает старшинство марсианских «цифр».

Осталось разобраться с порядком записи данных «цифр» в числах.

По второму примеру понятно, что FZ это 49, квадрат числа 7. Значит запись RF означает 7, т.е. запись «цифры» F после более «старших» цифр означает вычитание.

З) Выскажем предположение: если в записи марсианская «цифра» следует за более старшей, то она не прибавляется, а отнимается от остальных. Тогда в порядке старшинства «цифры» складываются, а в обратном – отнимаются, т.е. ZXF – это (48-12-1), т.е. запись числа 35.

Попробуем расшифровать все остальные примеры с учетом этих правил.

                           (1+1+4) * 8 =48                                           48=48

                       (8-1) * (8-1) = 1+48                                     49=49

FX + LF = LX                           (1+12)+(4-1)=4+12                                      16=16

RXZ + F = FRXZ                      (8+12+48)+1=1+8+12+48                           69=69

FFRZX + F = ZF                       (1+1+8+48-12)+1=48-1                               47=47

                       (1+8)*(4-1)=4-1+12+12                               27=27

                          (1+4)*(8-1)=48-12-1                                    35=35

                            (4+12)*4=4+12+48                                      64=64

FRX + FLZ = FFXXZ               (1+8+12)+(1+4+48)=1+1+12+12+48          74=74

XXF + ZF = FFRXZ                 (12+12-1)+(48-1)=1+1+8+12+48                70=70

                          (1+1+8)*4=4+48-12                                    40=40

FFL + FXX = RFXX                 (1+1+4)+(1+12+12)=8-1+12+12                 31=31

Можно проверить и другие версии – например, что F не 1 а другое число. Но тогда из равенства Ж получаем  При F > 1 получается, что Z>100, поэтому остается только один вариант, Z=1.

Так что решение единственное:

F =1      L =4            R =8       X =12     Z =48

Запишем тем же способом числа 17, 57, 38, 43, 21, 5 и 42.

17=16+1=12+4+1=FLX

57=56+1=48+8+1=FRZ

38=36+2=48-12+2=FFZX

43=48-4-1=ZLF

21=12+8+1=FRX

5=4+1=FL

42=48-8+2=FFZR

(решение взято из работы Васильева Максима из города Курган)

Критерии:

Нахождение значений F,L,R,X,Z......................................................................................................................... 3

Объяснение способа записи ................................................................................................................................ 2

Единственность решения..................................................................................................................................... 2

Ответ....................................................................................................................................................................... 1

 

10(5 балла). Имеется 2n (n>2) батареек, n из которых заряжено, а n разряжено. Радио работает только от двух заряженных батареек. За одну операцию разрешается вставить любые две батарейки в радио, и проверить - работает ли оно. За какое наименьшее количество операций, можно вставить в радио две гарантированно заряженные батарейки?

 (Задача предложена базовой кафедрой УРВиИТ)

Решение: за n+3.

Занумеруем все батарейки. Пусть в радио будут вставляться следующие пары: 1-2, 2-3, 1-3 и 4-5, 5-6, 4-6. Остальные 2n-6  батареек разобьем на пары. Если среди первой или второй тройки будет две работающие батарейки, то задачу можно считать решенной. Если нет, то на оставшиеся 2n-6 батареек придется n-2 работающие. По принципу Дирихле, получим, что в какой-то из оставшихся пар (их n-3) будет 2 работающие батарейки.  За n+2 операции такие две батарейки указать нельзя. Покажем это по индукции. Для n=3 это очевидно. Пусть мы для всех наборов из 2k<2n батареек и k+2 пар (или операций) умеем приводить такой пример разбиения батареек на заряженные и незаряженные, что в каждой паре будет хотя бы одна разряженная. По принципу Дирихле, найдется батарейка, которую вставляли в радио не более одного раза. Пусть у неё будет номер 2n, а у той, с которой её вставляли 2n-1. Батарейку с номером 2n будем считать заряженной, а с номером 2n-1 разряженной. Для остальных батареек воспользуемся предположением индукции и так разобьем их на работающие и неработающие, что никакая из пар с ними работать не будет.

Критерии:

Правильный пример............................................................................................................................................. 2

Пример на чуть большее число операций ......................................................................................................... 1

Оценка.................................................................................................................................................................... 2

 

11(4 балла). Верно ли, что если все грани тетраэдра суть остроугольные треугольники, то и все двугранные углы этого тетраэдра острые?

 (Задача предложена базовой кафедрой УРВиИТ)

Решение:

Нет, не верно. Приведем такой контрпример. Рассмотрим два правильных треугольника ABC и ABD такие, что плоскости, содержащие их, перпендикулярны. Обозначим середину отрезка AB за M, также для удобства будем считать, что длина AB =1. Тогда MC = MD = , и по теореме Пифагора CD = . Так, получаем, что треугольники ACD и BCD будут равнобедренными, причем основание у них будет иметь длину , а боковые стороны будут по 1. Такие треугольники остроугольные, поскольку < .

Так что, тетраэдр ABCD будет иметь в качестве своих граней остроугольные треугольники, хотя его двугранный угол при AB будет прямым.

Критерии:

Пример.................................................................................................................................................................... 3

Доказательство....................................................................................................................................................... 1

 

12(5 баллов). Дан произвольный набор, состоящий из тридцати различных 6-сочетаний из элементов множества V={1,...,25}. Верно ли, что можно так покрасить элементы множества V в красный и синий цвета, чтобы каждое из наших 6-сочетаний оказалось неодноцветным (содержало и красные, и синие вершины)? (6-сочетанием называется набор из 6-ти различных элементов множества, причем сочетания, различающиеся перестановкой элементов, считаются одинаковыми).

(Райгородский А.М., д.ф.-м.н., руководитель бакалавриата базовой кафедры Яndex )

Решение:

Верно. Всего раскрасок в 2 цвета  штук. Раскрасок, которые оставляют одноцветным одно конкретное 6-сочетание, -  штук. Раскрасок, в которых хотя бы одно сочетание одноцветно, заведомо не больше, чем . Значит, есть раскраски, в которых каждое сочетание неодноцветно.

Критерии:

Алгоритм без доказательства............................................................................................................................... 3

Оценка или алгоритм с доказательством............................................................................................................ 5

 

13(4 балла за вопрос А + 3 балла за вопрос Б). В математическом классе учатся 20 школьников. Из них пятеро одинаково хорошо и лучше всех остальных умеют решать задачи по комбинаторике, пятеро столь же сильны в геометрии, пятеро - в теории чисел и т.д. Всего имеется 18 группировок по 5 человек, которые одинаково хорошо и лучше всех остальных владеют некоторым предметом. Очевидно, что бывают школьники, в равной мере сильные в нескольких дисциплинах (принадлежащие сразу нескольким группировкам). Предположим, нам необходимо отправить на олимпиаду по математике команду от этого класса. Нам  нужно, чтобы, во-первых, для каждого предмета в команде был представитель, который лучше всех решает по нему задачи. И, во-вторых, мы стремимся выбрать команду поменьше, желая минимизировать накладные расходы.  А) Докажите, что всегда можно взять в команду семь человек. Б) Докажите, что бывают случаи, когда команды из пяти человек не хватит.

 (Райгородский А.М., д.ф.-м.н., руководитель бакалавриата базовой кафедры Яndex )

Решение.

а) Выберем школьника, который лучше всех владеет самым большим количеством различных

предметов. Конечно, такой школьник может быть не единственным. Возьмем тогда любого. Главное, что этот школьник владеет не менее 18*5/20 предметами. Иными словами, он служит представителем по крайней мере пяти различных дисциплин.

Остается 13 дисциплин, на каждую из которых нужно найти своего "специалиста". При этом и

специалистов уже не 20, а 19. Но группировки по-прежнему имеют размер 5. Снова берем самого "крутого" школьника. Он покрывает 13*5/19 предметов.  То есть еще для четырех наук дока в них найден.

На следующем шаге у нас 9 предметов, 18 человек и 5 человек в каждой группе. Покрываем 9*5/18, т.е. 3 предмета. Далее, аналогично, 6, 17, 5 дают 2 предмета и 4, 16, 5 тоже дают два предмета. Всего на данном этапе сделано 5 шагов, и, стало быть, в команде 5 человек. Остается два непокрытых предмета. Ну, еще двоих выделяем на них. Семерых хватило.

б) Надо придумать совокупность, состоящую из таких восемнадцати пятиэлементных подмножеств двадцатиэлементного множества, чтобы для любых пяти элементов некоторое подмножество из совокупности с ними не пересекалось. Очень просто. Обозначим исходное множество {1,...,20}. Рассмотрим все 6 пятиэлементных подмножеств в {1,...,6}, все 6 пятиэлементных подмножеств в {7,...,12} и все 6 пятиэлементных подмножеств в {13,...,18}. Всего в аккурат 18 множеств. Ясно, что для каждой из трех шестерок требуются ровно 2 представителя. Значит, пяти не хватит.

Критерии:

А)

Существование школьника, знающего 18*5/20 предметов.............................................................................. 3

Подсчет................................................................................................................................................................... 1

Б)Пример................................................................................................................................................................ 3

14(2 балла за вопрос А + 2 балла за вопрос Б). Cимплекс или n-симплекс - это геометрическая фигура, являющаяся n-мерным обобщением треугольника. Определяется как выпуклая оболочка n+1 точек, не лежащих в одной n-мерной гиперплоскости. Эти точки называются вершинами симплекса.

В частности:

0-симплекс это точка; 1-симплекс это отрезок;

2-симплекс это треугольник;  3-симплекс это тетраэдр; и так далее.

m-гранью n-симплекса (0 £ m £ n) называется m-симплекс, образованный любым подмножеством из m+1 вершины из множества n+1 вершин n симплекса. Точка представляет собой единственную вершину (0-грань). У отрезка две вершины и одно ребро (1-грань). У треугольника три вершины, три ребра и одна грань (2-грань). У тетраэдра четыре вершины, шесть ребер, четыре грани и одна 3-грань. А) Сколько 3-граней у 6-симплекса? Б) Сколько всего граней содержит 6-симплекс (включая себя самого)?

  (Задача предложена базовой кафедрой  Cognitive Technologies )

Решение.

1. По определению n-симплекс содержит n+1 вершину. Любое подмножество из m+1 вершин определяет m-грань. Способов выбрать такое подмножество .

2. Любое непустое подмножество определяет грань. Способов выбрать из n+1 вершины произвольное

непустое подмножество 2n +1 – 1 = 26+1 – 1 = 127.

Критерии:

Комбинаторная формулировка без подсчета...................................................................................................... 3

Подсчет................................................................................................................................................................... 1

Решение А)............................................................................................................................................................. 2

Решение Б).............................................................................................................................................................. 2

b0

b1

b2

b3

Þ

b12

b8

b4

b0

b4

b5

b6

b7

Þ

b13

b9

b5

b1

b8

b9

b10

b11

Þ

b14

b10

b6

b2

b12

b13

b14

b15

Þ

b15

b11

b7

b3

15(5 баллов). Фрагмент черно-белого изображения размером 4х4 пикселя логически представляет собой матрицу 4х4 из нулей и единиц и может быть закодирован в памяти компьютера 16-битовым словом W=b0 b1...b15. Необходимо повернуть изображение по часовой стрелке на 90 градусов (нужно переставить биты в слове: значение бита b0 должно поместиться в бит b12, b1 в b8, b2 в b4 и так далее) 

Поскольку изображение может содержать миллион и более таких фрагментов, операция выполняется многократно и должна быть запрограммирована эффективно. Простейший и скорейший способ – заранее составить специальную таблицу T[ ], в которой для каждого 16-битного числа W в позиции таблицы с номером W указано значение W’ с уже переставленными битами. Процедура вычисления будет состоять из одного оператора, состоящего из двух элементарных операций – извлечения из таблицы и присваивания: W’=T[W]. Однако такая таблица будет содержать 216 элементов по 2 байта каждый, т.е. ее размер составит 128 Кбайт, что для некоторых приложений тяжеловесно.

Как переставить биты, используя объем памяти в пределах 1Кбайт и выполняя не более 10 элементарных операций таких как присваивание, логическая или арифметическая операция, извлечение из таблицы?

(Задача предложена базовой кафедрой  Cognitive Technologies )

b0

b1

b2

b3

 

 

 

b4

b0

b4

b5

b6

b7

 

 

b5

b1

 

 

 

 

 

 

b6

b2

 

 

 

 

 

 

b7

b3

Решение.

Составим таблицу T1[], которая решает задачу для битов 0-7

 

 

 

 

 

b12

b8

 

 

 

 

 

 

b13

b9

 

 

b8

b9

b10

b11

b14

b10

 

 

b12

b13

b14

b15

b15

b11

 

 

Она будет содержать 256 двухбайтовых слов (т.е. 512 байт), в которых исходные биты 0-7 поставлены на свое новое место, а в позициях, соответствующих пустым клеткам таблицы будет записан ноль. Т.е. число в позиции W будет иметь вид

T1[W] = 0 0 b4 b0 0 0 b5 b1 … 0 0 b7 b3

Составим аналогичную таблицу T2 для битов 8-15

Сформируем результат как W’ = T1 [ W >> 8 ]  |  T2[ W &  0xff ]

В таком варианте решение использует 1Кб памяти для таблиц и вычисляется за 6 операций.

Мы можем заметить, что Т2 [x] == T1[x] << 2. Это дает сравнимый по эффективности вариант:

W’ = T1 [ W >> 8 ] |( T1[ W &  0xff ] << 2 ). Он использует 512 байт памяти и вычисляется за 7 операций.

Критерии:

Правильный алгоритм.......................................................................................................................................... 5

Хороший алгоритм ............................................................................................................................................... 3

16(2 балла за вопрос А + 4 балла за вопрос Б). Рассмотрим двухмерную диаграмму (см. рис.1): по одной оси которой отложим «объём выпуска» (количество штук в год), а по другой «число циклов работы» - число функциональных циклов, реализуемых между выпуском изделия и его ремонтом или поломкой. На этой диаграмме кружочками с цифрами отмечены положения следующих изделий: спички, авиационные двигатели, стрелковое оружие. Векторы, исходящие из точек, ориентировочно показывают тенденцию развития образцов данного семейства. А) Вам предлагается определить, какая цифра какому изделию соответствует, и если вы сделаете это верным образом, то получите, что в настоящее время объём выпуска авиационных двигателей остаётся примерно постоянным, а число их циклов работы растёт. Б) Рассмотрите аналогичную диаграмму у которой по осям отложены: «объём дерева сборки» - количество деталей, узлов и агрегатов данного изделия, и «объём выпуска» (см. рис.2). Расставьте на ней точки, соответствующие орбитальным станциям, бульдозерам, телескопам, сигаретам и соответствующие векторы развития.   

(Капустян В. М., к.т.н., зам. заведующего кафедрой Концепт)

Решение:

А) Спички: постоянное число циклов работы (1), объем выпуска самый большой, причем увеличивающийся – цифра 1.

Авиационные двигатели – самый маленький объем выпуска, самое большое число циклов работы, причем качество двигателей (в том числе число циклов работы растет быстрее, чем объем выпуска) – цифра 2.

Объем выпуска

 

 

1

3

4

Объем сборки

 

1

0

1

Рис. 2

.

2

Б) Орбитальные станции – тираж очень маленький, рост количества незначительный. Объем дерева сборки самый большой среди перечисленных изделий, и значительно растет.

Сигареты – объем выпуска самый большой среди данных изделий и, к сожалению, растет. Объем дерева сборки – порядка 10 «деталей» - остается постоянным

Телескопы – объем выпуска больший, чем у бульдозеров, но значительно меньший, чем у сигарет. Объем дерева сборки весьма разнообразный – от порядка 10 деталей в простейших моделях до нескольких миллиардов. Среднее значение, немного больше, чем у бульдозеров, и значительно меньше, чем у орбитальных станций. Тенденция развития - к увеличению, главным образом, объема выпуска.

Бульдозеры – в этой диаграмме схожи с телескопами, но в меньшем масштабе: объем выпуска и объем дерева сборки немного меньше.

Исходя из этих размышлений добавляем точки на диаграмму.

Критерии:

А)

Объяснено положение точек................................................................................................................................ 1

Объяснен вектор развития изделия..................................................................................................................... 1

Б)За каждую точку................................................................................................................................................. 1

 

(решение взято из работы Васильева Максима из города Курган)

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика