Решения задач ЕГЭ 2014года
материал для подготовки к егэ (гиа) по информатике и икт (11 класс) на тему

A 10 На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула

( (x ∈ А) → (x ∈ P) ) ∨ (x ∈ Q)

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

1) [0, 3]
2) [3, 11]
3) [11, 15]
4) [15, 17]

Пояснение. 

Введем обозначения:

(x ∈ А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.

Применив преобразование импликации, получаем:

¬A∨P∨Q.

Логическое ИЛИ истинно, если истинно хотя бы одно утверждение. Выражение P ∨ Q истинно на отрезке [2; 14]. Поскольку все выражение должно быть истинно для любого x, выражение ¬A должно быть истинно на множестве (−∞; 2) ∪ (14; ∞). Таким образом, выражение A должно быть истинно только внутри отрезка [2;14].

Из всех отрезков только отрезок [3; 11] полностью лежит внутри отрезка [2; 14].

Ответ: 2.

A 10 На числовой прямой даны три отрезка: P = [20,50], Q = [15, 20] и R=[40,80]. Выберите такой отрезок A, что формула

( (x ∈ P) → (x ∈ Q) ) ∨ ((x ∈ A)→ (x ∈ R))

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

1) [10,25]
2) [20, 30]
3) [40,50]
4) [35, 45]

Пояснение. 

Логическое ИЛИ истинно, если истинно хотя бы одно утверждение.

Введем обозначения:

(x ∈А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q; (x ∈ R) ≡ R.

Применив преобразование импликации, получаем:

¬P∨Q∨¬A∨R

¬P∨Q∨R истинно тогда, когда x∈(– ∞,20];[40,∞). Выражение ¬A должно быть истинно на интервале [20;40]. Поскольку все выражение должно быть истинно для ЛЮБОГО x, следовательно, выражение A должно быть истинно на промежутке, не включающем отрезок [20;40].

Из всех отрезков только отрезок [40;50] удовлетворяет этому условию.

A 11 В некоторой стране автомобильный номер состоит из 7 символов. В качестве символов используют 18 различных букв и десятичные цифры в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов, при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объем памяти, отводимый этой программой для записи 60 номеров.

1) 240 байт
2) 300 байт
3) 360 байт
4) 420 байт

Пояснение. 

Согласно условию, в номере могут быть использованы 10 цифр (0..9) и 18 букв, всего 10 + 18 = 28 символов. Известно, что с помощью N бит можно закодировать 2N различных символов. Поскольку 24 < 28 < 25, то для записи каждого из 28 символов необходимо 5 бит.

Для хранения всех 7 символов номера нужно 7 * 5 = 35 бит, а т.к. для записи используется целое число байт, то берём ближайшее не меньшее значение, кратное восьми, это число 40 = 5 * 8 бит (5байт).

Тогда 60 номеров занимают 5 * 60 = 300 байт.

Правильный ответ указан под номером 2.

A 11 В некоторой стране проживает 1000 человек. Индивидуальные номера налогоплателыциков-физических лиц в этой стране содержат только цифры 0, 1, 2 и 3. Каково минимальное количество разрядов в ИНН в этой стране, если различные между собой номера имеют абсолютно все жители?

1) 4
2) 5
3) 9
4) 10

Пояснение. 

Мы имеем 4 символа. Из M = 4 различных символов можно составить Q = MN комбинаций длиной N, поэтому решим неравенство 4N ≥ 1000, откуда найдём наименьшее целое N: N = 5.

Минимальное количество разрядов 5.

Правильный ответ указан под номером 2.

В программе описан одномерный целочисленный массив с индексами от 0 до n. Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы, обрабатывающей данный массив:

Чему будет равно значение переменной s после выполнения данной программы? Ответ должен быть верным при любых значениях элементов массива.

1) Минимальному элементу в массиве A
2) Количеству элементов массива A, меньших последнего элемента массива
3) Сумме всех элементов массива А, меньших последнего элемента массива
4) Индексу первого элемента массива А, который меньше A[n]

Пояснение. 

Переменой z присваивается значение последнего элемента.

Внутри цикла все элементы массива сравниваются с последним, при этом если элемент меньше последнего, то переменная s увеличивается на значение данного элемента. Если в массиве x элементов меньше последнего, то s примет значение, равное сумме значений x элементов, меньших последнего элемента массива.

Правильный ответ указан под номером 3.

B2 Определите значение переменной "с" после выполнения следующего фрагмента программы:

x:= 8 + 2*5;

y:= (x mod 10) + 14;

x:= (y div 10) + 3;

c:= x - y;

Пояснение. 

Операция div делит число с отбрасыванием остатка.

Операция mod оставляет только остаток от деления числа.

x:= 8 + 2*5 = 8 + 10 = 18;

y:= (x mod 10) + 14 = 8 + 14 = 22;

x:= (y div 10) + 3 = 2 + 3 = 5;

c:= x - y = 5 - 22 = -17

B2 Определите значение целочисленных переменной c после выполнения фрагмента программы:

а :=6*12 + 3;

b :=(a div 10)+ 5;

a :=(b mod 10)+ 1

с := a + b;

Пояснение. 

Операция div делит число с отбрасыванием остатка.

Операция mod оставляет только остаток от деления числа.

а :=6*12 + 3 = 72 + 3 = 75;

b :=(a div 10)+ 5 = 7 + 5 = 12;

a :=(b mod 10)+ 1 = 2 + 1 = 3;

с := a + b = 3 + 12 = 15

B2  Определите значение переменной c после выполнения следующего фрагмента программы (записанного ниже на разных языках программирования):

Пояснение. 

a := 30;

b := 6;

a := a / 5 * b = 6*6 = 36;

if a > b then (верно)

c := a - 4 * b = 36 - 24 = 12

else (эта часть не выполняется)

c := a + 4 * b;

B6  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * n, при n >1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

Пояснение. 

Последовательно находим: F(2) = F(1) * 2 = 2, F(3) = F(2) * 3 = 6, F(4) = F(3) * 4 = 24, F(5) = F(4) * 5 = 120.

Примечание 

Использование функции позволяет вычислить так называемый факториал числа n — произведение натуральных чисел от 1 до n. Тем самым, F(5) = 1 * 2 * 3 * 4 * 5 = 120.

B6 Последовательность чисел трибоначчи задается рекуррентным соотношением:

F(1) = 0

F(2) = 1

F(3) = 1

F(n) = F(n–3) + F(n–2) + F(n–1), при n >3, где n – натуральное число.

Чему равно одиннадцатое число в последовательности трибоначчи?

В ответе запишите только натуральное число.

Пояснение. 

Последовательно находим:

F(4) = F(1) + F(2) + F(3) = 2,

F(5) = F(2) + F(3) + F(4) = 4,

F(6) = F(3) + F(4) + F(5) = 7,

F(7) = F(4) + F(5) + F(6) = 13,

F(8) = F(5) + F(6) + F(7) = 24,

F(9) = F(6) + F(7) + F(8) = 44,

F(10) = F(7) + F(8) + F(9) = 81,

F(11) = F(8) + F(9) + F(10) = 149.

Одиннадцатое число в последовательности трибоначчи равно 149.

B 6 Последовательность чисел Люка задается рекуррентным соотношением:

F(1) = 2

F(2) = 1

F(n) = F(n–2) + F(n–1), при n >2, где n – натуральное число.

Чему равно десятое число в последовательности Люка?

В ответе запишите только натуральное число.

Пояснение. 

Последовательно находим:

F(3) = F(1) + F(2) = 3,

F(4) = F(2) + F(3) = 4,

F(5) = F(3) + F(4) = 7,

F(6) = F(4) + F(5) = 11,

F(7) = F(5) + F(6) = 18,

F(8) = F(6) + F(7) = 29,

F(9) = F(7) + F(8) = 47,

F(10) = F(8) + F(9) = 76.

Десятое число в последовательности Люка равно 76.

B 8 Ниже записана программа. Получив на вход число x , эта программа печатает два числа, L и M. Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 3, а потом 7.

var x, L, M: integer;

begin

    readln(x);

    L:=0; M:=0;

    while x > 0 do begin

        L:= L + 1;

        if x mod 2 = 0 then

            M:= M + (x mod 10) div 2;

        x:= x div 10;

    end;

    writeln(L); write(M);

end. 

Пояснение. 

Рассмотрим цикл, число шагов которого зависит от изменения переменной x:

while x > 0 do begin

...

x:= x div 10;

end;

Т. к. оператор div оставляет только целую часть от деления, то при делении на 10 это равносильно отсечению последней цифры.

Из приведенного цикла видно, что на каждом шаге от десятичной записи x отсекается последняя цифра до тех пор, пока все цифры не будут отсечены, то есть x не станет равно 0; поэтому цикл выполняется столько раз, сколько цифр в десятичной записи введенного числа, при этом число L столько же раз увеличивается на 1. Следовательно, конечное значение L совпадает с числом цифр в x. Для того, чтобы L стало L=3, x должно быть трёхзначным.

Теперь рассмотрим оператор изменения M:

if x mod 2 = 0 then

  M:= M + (x mod 10) div 2;

end;

Оператор mod оставляет только остаток от деления, при делении на 10 это последняя цифра x.

Условие x mod 2 = 0 означает следующее: чтобы M увеличилось, число x должно быть чётным.

Предположим, исходное x нечётное, тогда на первом шаге M = 0.

Если на втором шаге x также нечётное (вторая цифра исходного числа нечётная), то M = 0, причём каким бы ни было значение x на третьем шаге, мы не сможем получить M = 7, поскольку остаток от деления чётного числа на 10 не превосходит 8, а 8 / 2 = 4, следовательно, вторая цифра исходного x чётная.

Тогда первая цифра может принимать значения 2, 4, 6, 8, но мы ищем наибольшее x, поэтому сделаем первую цифру, равной 9, тогда наше предположение не удовлетворяет условию задачи, и последняя цифра исходного числа обязана быть чётной, т.е. исходное x чётно.

7 = 4 + 3, чему соответствуют цифры 8 и 6. Теперь, располагая цифры по убыванию, находим наибольшее возможное x: x = 986.

Ответ: 986.

B 10 Документ объемом 10 Мбайт можно передать с одного компьютера на другой двумя способами:

А) Сжать архиватором, передать архив по каналу связи, распаковать

Б) Передать по каналу связи без использования архиватора.

Какой способ быстрее и насколько, если

– средняя скорость передачи данных по каналу связи составляет 218 бит в секунду,

– объем сжатого архиватором документа равен 30% от исходного,

– время, требуемое на сжатие документа – 7 секунд, на распаковку – 1 секунда?

В ответе напишите букву А, если способ А быстрее или Б, если быстрее способ Б. Сразу после буквы напишите количество секунд, насколько один способ быстрее другого.

Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23. Слов «секунд», «сек.», «с.» к ответу добавлять не нужно.

Пояснение. 

Способ А. Общее время складывается из времени сжатия, распаковки и передачи. Время передачи t рассчитывается по формуле t = Q / q, где Q — объём информации, q — cкорость передачи данных.

Найдём сжатый объём: 10 * 0,3 = 3 Мбайта

Переведём Q из Мбайт в биты: 3 Мбайта = 3 * 220 байт = 3 * 223 бит.

Найдём общее время: t = 7 с + 1 с + 3 * 223 бит / 218 бит/с = 8 + 3 * 25 с = 104 с.

Способ Б. Общее время совпадает с временем передачи: t = 10 * 223 бит / 218 бит/с = 10 * 25 с = 320 с.

Видно, что способ A быстрее на 320 - 104 = 216 с.

Ответ: A216.

B 10 Документ объёмом 12 Мбайт можно передать с одного компьютера на другой двумя способами. А. Сжать архиватором, передать архив по каналу связи, распаковать. Б. Передать по каналу связи без использования архиватора. Какой способ быстрее и насколько, если:

• средняя скорость передачи данных по каналу связи составляет 222 бит в секунду;
• объём сжатого архиватором документа равен 75% исходного;
• время, требуемое на сжатие документа, — 13 секунд, на распаковку — 3 секунды?

В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого. Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23. Единицы измерения «секунд», «сек.», «с.» к ответу добавлять не нужно.

Пояснение. 

Способ А. Общее время складывается из времени сжатия, распаковки и передачи. Время передачи t рассчитывается по формуле t = Q / q, где Q — объём информации, q — cкорость передачи данных.

Найдём сжатый объём: 12 · 0,75 = 9 Мбайт. Переведём Q из Мбайт в биты: 9 Мбайт = 9 · 220 байт = 9 · 223 бит. Найдём общее время: t = 13 с + 3 с + 9 · 223 бит / 222 бит/с = 16 + 9 · 21 с = 34 с.

Способ Б. Общее время совпадает с временем передачи: t = 12 · 223 бит / 222 бит/с = 12 · 21 с = 24 с. Таким образом, способ Б быстрее на 34 − 24 = 10 с.

Ответ: Б10.

 В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.

По заданным IP-адресу узла и маске определите адрес сети.

IP –адрес узла: 224.9.195.133

Маска: 255.255.192.0

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

Пример.

Пусть искомый IP-адрес 192.168.128.0, и дана таблица

В этом случае правильный ответ будет записан в виде: HBAF

Пояснение. 

1. Запишем числа маски сети в двоичной системе счисления.

2. Адрес сети получается в результате поразрядной конъюнкции чисел маски и чисел адреса узла (в двоичном коде). Так как конъюнкция 0 с чем-либо всегда равна 0, то на тех местах, где числа маски равны 0, в адресе узла стоит 0. Аналогично, там, где числа маски равны 255, стоит само число, так как конъюнкция 1 с любым числом всегда равна этому числу.

3. Рассмотрим конъюнкцию числа 192 с числом 195.

Результатом конъюнкции является число .

4. Сопоставим варианты ответа получившимся числам: 224, 9, 192, 0, т.е. правильный ответ - HBFA.

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» - символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

По запросу Башмачкин & Кряква ни одной страницы найдено не было.

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

Пояснение. 

Наша цель — N1 + N4 + N2 + N5 + N3.

Количество запросов в данной области будем обозначать Ni.

Тогда из таблицы находим, что:

N1 + N4 = 40

N5 + N3 = 600

N2 + N4 + N5 = 6 000

N5 = 200

N4 = 30

Из первого и последнего уравнения: N1 = 10.

Из второго и предпоследнего уравнения: N3 = 400

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

N1 + N4 + N2 + N5 + N3 = 6000 + 400 + 10 = 6410.

У исполнителя Увеличитель две команды, которым присвоены номера:

1. прибавь 1,

2. умножь на 4.

Первая из них увеличивает число на экране на 1, вторая — умножает его на 4.

Программа для Увеличителя — это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 29?

Ответ обоснуйте.

Пояснение. 

Обозначим R(n) — количество программ, которые преобразуют число 1 в число n. Обозначим t(n) наибольшее нечетное число, кратное четырем, не превосходящее n.

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

Верны следующие соотношения:

1. Если n не делится на 4, то тогда R (n) = R(T(n)), так как существует

единственный способ получения n из T(n) - прибавлением единиц.

2. Пусть n делится на 4.

Тогда R (n) = R(n/4)+R(n-1)= R(n/4)+R(n-4) (если n>4).

При n = 4 выполнено: R(n) = 2 (два способа: прибавлением трех единиц или

однократным умножением на 4).

Поэтому достаточно по индукции вычислить значения R(n) для всех нечётных

чисел, кратных четырем и не превосходящих 29.

Имеем:

R(1)= R(2) = R(3) = 1

R(4) = 2 = R(5) = R(6) = R(7)

R(8) = R(2) + R(7) = 1 + 2 = 3 = R(9) = R(10) = R(11)

R(12) = R(3)+R(11) = 1 + 3 = 4 = R(13)= R(14) = R(15)

R(16) = R(4) + R(15) = 2 + 4 = 6 = R(17) = R(18) = R(19)

R(20) = R(5) + R(19) = 2 + 6 = 8 = R(21) = R(22) = R(23)

R(24) = R(6) + R(23) = 2 + 8 = 10 = R(25) = R(26) = R(27)

R(28) = R(7) + R(27) = 2 + 10 = 12 = R(29)

Ответ: 12.

Другой способ решения

Будем решать поставленную задачу последовательно для чисел 1, 2, 3,..., 29 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Число 1 у нас уже есть, значит, его можно получить с помощью «пустой» программы. Любая непустая программа увеличит исходное число, т. е. даст число, больше 1. Значит, R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 4, то оно может быть получено только из предыдущего числа с помощью команды прибавь 1. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: .

Если число на 4 делится, то вариантов последней команды два: прибавь 1 и умножь на 4, тогда . Заполним соответствующую таблицу по приведёным формулам слева направо:

При этом ячейки, относящиеся к числам, которые не делятся на 4, можно в решении и опустить (за исключением первого и последнего чисел):

Ответ: 12.

Определите, какое число будет напечатано в результате выполнения следующего алгоритма:

Var a,b,t,M,R :integer;

Function F(x:integer):integer;

begin

    F:=(x+5)*(x+3);

end;

BEGIN

    a:= -5; b:=5;

    M:=a; R:=F(a);

    for t:=a to b do begin

        if (F(t)> R)then begin

            M:=t;

            R:=F(t);

        end;

    end;

    write(R);

END.

Пояснение. 

1. Алгоритм предназначен для поиска наибольшего значения функции F(t) на отрезке от a до b.

2. Квадратный трехчлен F(t) положительным старшим коэффициентом пересекает ось абсцисс в точках -5 и -3 и, следовательно, возрастает на луче [-3; ∞). Поэтому наибольшее значение функции достигается в точке 5 и равно F(5)=80.

Определите, какое число будет напечатано в результате выполнения следующего алгоритма:

Var a,b,t,M,R :integer;

Function F(x:integer):integer;

begin

    F:=4*(x-5)*(x+3);

end;

BEGIN

    a:=-20; b:=20;

    M:=a; R:=F(a);

    for t:=a to b do begin

        if (F(t)< R)then begin

            M:=t;

            R:=F(t);

        end;

    end;

    write(R);

END.

Пояснение. 

1. Алгоритм предназначен для поиска наименьшего значения функции F(t) на отрезке от a до b.

2. Квадратный трехчлен F(t) с положительным старшим коэффициентом пересекает ось абсцисс в точках 5 и −3 и, следовательно, наименьшее значение достигается в вершине 1 и равно F(1) = −64.

Требовалось написать программу, которая решает неравенство относительно х для любого ненулевого числа b и любого неотрицательного числа а и , введенных с клавиатуры. Все числа считаются действительными. Программист торопился и написал программу неправильно.

Последовательно выполните три задания:

1) Приведите пример таких чисел а, b, х, при которых программа неверно решает поставленную задачу.

2) Укажите, какая часть программы является лишней.

3) Укажите, как нужно доработать программу, чтобы не было случаев ее некорректной работы. (Это можно сделать несколькими способами, поэтому можно указать любой способ доработки исходной программы).

Пояснение. 

1) а = 1, b = −1, х = 0. Значение х может быть не указано. Значение b может быть любым отрицательным числом, значение а — любым положительным. Также допустим ответ, что программа работает неправильно при любых положительных а и отрицательных b.

2) Лишняя часть: не нужно вводить х с клавиатуры; верно: readln (а, b) .

3) Возможная доработка: readln(a,b);

if а=0 then

if b>0 then

write('нет решений')

else

write('x>0 или x<01)

else

if b>0 then

write(-a,'

else

write ('x>0 или x<',-a);

(могут быть и другие способы доработки).

Дан вещественный массив из 50 элементов. Элементы массива могут принимать произвольные значения. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит наименьший номер отрицательного элемента массива или сообщение, что такого элемента нет.

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.

В качестве ответа вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Borland Pascal 7.0) или в виде блок-схемы. В этом случае вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).

Пояснение. 

Приведем решение, использующее только один цикл (один проход по массиву). 

const n=50;

var a: array[1..n] of real;

i, j: integer;

begin

j:=0;

for i:=1 to n do

begin

readln(a[i]);

if (a[i]<0) and (j=0) then j:=i;

end;

if j=0 then writeln('no') else writeln(j);

end.

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Пояснение. 

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в пять раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится более 100. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 101 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 100.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

1. а) При каких значениях числа S Петя может выиграть первым ходом? Укажите все такие значения и выигрывающий ход Пети.

б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

2. Укажите два значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для указанных значений S опишите выигрышную стратегию Пети.

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

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

Пояснение. 

1. а) Петя может выиграть, если S = 21, ..., 100. При меньших значениях S за один ход нельзя получить кучу, в которой больше 100 камней. Пете достаточно увеличить количество камней в 5 раз. При S < 21 получить за один ход больше 100 камней не возможно.

1. б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 20 камней. Тогда после первого хода Пети в куче будет 21 камень или 100 камней. В обоих случаях Ваня увеличивает количество камней в 5 раз и выигрывает в один ход.

2.  Возможные значения S: 4, 19. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 20 камней (при S = 4 он увеличивает количество камней в 5 раз; при S = 29 — добавляет 1 камень). Эта позиция разобрана в п. 1 б). В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.

3. Возможное значение S: 18. После первого хода Пети в куче будет 19 или 90 камней. Если в куче станет 90 камней, Ваня увеличит количество камней в 5 раз и выиграет своим первым ходом. Ситуация, когда в куче 19 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения допустимы).