Задания
Версия для печати и копирования в MS Word
Тип 15 № 55811
i

Обо­зна­чим через m&n по­раз­ряд­ную конъ­юнк­цию не­от­ри­ца­тель­ных целых чисел m и n. На­при­мер,

14&5  =  11102&01012  =  01002  =  4.

Для ка­ко­го наи­мень­ше­го не­от­ри­ца­тель­но­го це­ло­го числа А фор­му­ла

x\39 =0 \vee левая круг­лая скоб­ка x\11 = 0 arrow x\A не равно 0 пра­вая круг­лая скоб­ка

тож­де­ствен­но ис­тин­на (т. е. при­ни­ма­ет зна­че­ние 1 при любом не­от­ри­ца­тель­ном целом зна­че­нии пе­ре­мен­ной х)?
Спрятать решение

Ре­ше­ние.

При­ведём ре­ше­ние на языке Python.

for a in range(0, 1000):

k = 0

for x in range(0, 1000):

if (x & 39 == 0) or ((x & 11 == 0) <= (x & a != 0)):

k += 1

if k == 1000:

print(a)

break

 

Ответ: 36.

 

При­ведём ре­ше­ние Юрия Кра­силь­ни­ко­ва на языке Python.

print(min([a for a in range(1000) if all([x&39==0 or (x&11!=0 or x&a!=0) for x in range(1000)])]))

 

При­ведём ре­ше­ние Ев­ге­ния Дж­об­са (ана­ли­ти­че­ское через ана­лиз раз­ря­дов).

Пе­ре­ве­дем при­ве­ден­ные числа в дво­ич­ную си­сте­му счис­ле­ния.

 39_10=100111_2 ; 11_10=1011_2.

Про­ана­ли­зи­ру­ем усло­вие и опре­де­лим, когда зна­че­ние па­ра­мет­ра вли­я­ет на зна­че­ние всего вы­ра­же­ния. Для удоб­ства за­ме­ним под­вы­ра­же­ния на ко­рот­ки за­пи­си &39, &11 и &A. По­лу­ча­ем:

 \_39 \vee левая круг­лая скоб­ка \_11 arrow не равно g \_ A пра­вая круг­лая скоб­ка .

Зна­че­ние под­вы­ра­же­ния в скоб­ке су­ще­ствен­но, когда вы­ра­же­ние \_39=0, зна­че­ние под­вы­ра­же­ния &A вли­я­ет на зна­че­ние под­вы­ра­же­ния в скоб­ке, когда \_11=1.

Итого имеем си­сте­му:

 си­сте­ма вы­ра­же­ний левая круг­лая скоб­ка x 39=0 пра­вая круг­лая скоб­ка =0, левая круг­лая скоб­ка x 11=0 пра­вая круг­лая скоб­ка =1, левая круг­лая скоб­ка x A не равно q 0 пра­вая круг­лая скоб­ка =1 конец си­сте­мы . рав­но­силь­но си­сте­ма вы­ра­же­ний x 39 не равно q 0, x 11=0, x A не равно q 0. конец си­сте­мы .

Таким об­ра­зом, можно за­клю­чить, что в числе х биты на 0, 1 и 3 ме­стах (счи­тая с 0 спра­ва) долж­ны быть равны нулю. Также один из битов 0, 1, 2 или 5 дол­жен быть равен 1. Или, со­еди­няя эти два усло­вия в одно, 0, 1 и 3  — ну­ле­вые биты, один из битов 2 или 5 равен 1. По­это­му надо, чтобы па­ра­метр А по­крыл ва­ри­ан­ты, когда или вто­рой бит равен еди­ни­це, или пятые бит равен еди­ни­це, или оба бита (2 и 5) равны еди­ни­це. Сле­до­ва­тель­но, ми­ни­маль­ное зна­че­ние па­ра­мет­ра А, ко­то­рое под­хо­дит под это огра­ни­че­ние, равно 36.

 

При­ведём ре­ше­ние Ев­ге­ния Дж­об­са (ана­ли­ти­че­ское через ал­геб­ру ло­ги­ки).

Для удоб­ства рас­кро­ем им­пли­ка­цию, сде­лав ана­ло­гич­ную преды­ду­ще­му ре­ше­нию за­ме­ну. По­лу­ча­ем:

\_39 \vee левая круг­лая скоб­ка \_11 arrow не равно g \_ A пра­вая круг­лая скоб­ка =\_39 \vee не равно g \_11 \vee не равно g \_ A .

Опи­шем каж­дое под­вы­ра­же­ние с по­мо­щью ло­ги­че­ских вы­ра­же­ний, где Xn будет от­ве­чать за зна­че­ние раз­ря­да в по­зи­ции n числа х. Тогда:

 \_39 = левая круг­лая скоб­ка X_5=0 пра­вая круг­лая скоб­ка \wedge левая круг­лая скоб­ка X_2=0 пра­вая круг­лая скоб­ка \wedge левая круг­лая скоб­ка X_1=0 пра­вая круг­лая скоб­ка \wedge левая круг­лая скоб­ка X_0=0 пра­вая круг­лая скоб­ка ;

 не равно g \_11= левая круг­лая скоб­ка X_3=1 пра­вая круг­лая скоб­ка \vee левая круг­лая скоб­ка X_1=1 пра­вая круг­лая скоб­ка \vee левая круг­лая скоб­ка X_0=1 пра­вая круг­лая скоб­ка .

Можно за­ме­тить, что когда  X_ n =0, зна­че­ние под­вы­ра­же­ния в \_39 при­ни­ма­ет зна­че­ние ис­ти­на, для вто­ро­го на­о­бо­рот. По­это­му для удоб­ства можно за­ме­нить за­пись  левая круг­лая скоб­ка X_n=0 пра­вая круг­лая скоб­ка на  не равно g X_n,  левая круг­лая скоб­ка X_n=1 пра­вая круг­лая скоб­ка на X_n. Под­ста­вим по­лу­чив­ши­е­ся вы­ра­же­ния в вы­ра­же­ние из усло­вия и про­из­ве­дем со­кра­ще­ние вы­ра­же­ния.

 не равно g X_5 \wedge не равно g X_2 \wedge не равно g X_1 \wedge не равно g X_0 \vee X_3 \vee X_1 \vee X_0.

По пра­ви­лу сверт­ки можем со­кра­тить вы­ра­же­ние  не равно g X_1 \wedge не равно g X_0. По итогу по­лу­чим вы­ра­же­ние

 не равно g X_5 \wedge не равно g X_2 \vee X_3 \vee X_1 \vee X_0.

Это вы­ра­же­ние можно пре­об­ра­зо­вать (с уче­том по­ис­ка ми­ни­маль­ных зна­че­ний) в вы­ра­же­ние

\_36 \vee \_8 \vee \_2 \vee \_1.

До­пол­ним его под­вы­ра­же­ни­ем с па­ра­мет­ром

\_36 \vee не равно g \_8 \vee не равно g \_2 \vee не равно g \_1 \vee не равно g \_A.

За­ме­тим, что вы­ра­же­ние может быть све­де­но к то­же­ствен­ной ис­тин­но­сти толь­ко при со­кра­ще­нии его через пра­ви­ло ис­клю­че­ния тре­тье­го для \_36 V не равно g \_ A .

Источник: ЕГЭ по ин­фор­ма­ти­ке 06.04.2023. До­сроч­ная волна