Решение задач по теории игр и графам для подготовки к ЕГЭ по информатике

Задание 17

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в 2 раза. Например, пусть в одной куче 3 камня, а в другой 4 камня, такую позицию мы будем обозначать (3, 4). За один ход из позиции (3, 4) можно получить любую из четырёх позиций: (4, 4), (3, 5), (6, 4), (3, 8). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было 3 камня, во второй куче \(S\) камней, \(1 \le S \le 64\).

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Ваня имеет выигрышную стратегию победы на своём первом ходе. Укажите значение \(S\), когда такая ситуация возможна.

Решение:

Чтобы у Вани была выигрышная стратегия первым ходом, после первого хода Пети, Ваня должен попасть в проигрышную для Пети позицию. Рассмотрим возможные ходы Пети из начальной позиции \((3, S)\):

1. \((4, S)\) - Петя добавил 1 камень в первую кучу.
2. \((3, S + 1)\) - Петя добавил 1 камень во вторую кучу.
3. \((6, S)\) - Петя увеличил в 2 раза первую кучу.
4. \((3, 2S)\) - Петя увеличил в 2 раза вторую кучу.

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

Рассмотрим случай, когда \(S = 32\). Тогда после первого хода Пети возможны следующие позиции:

1. \((4, 32)\) - Ваня может увеличить первую кучу в 2 раза, получив \((8, 32)\), затем еще раз, получив \((16, 32)\), затем еще раз, получив \((32, 32)\), затем еще раз, получив \((64, 32)\). Сумма 96 > 68.
2. \((3, 33)\) - Ваня может увеличить вторую кучу в 2 раза, получив \((3, 66)\). Сумма 69 > 68.
3. \((6, 32)\) - Ваня может увеличить первую кучу в 2 раза, получив \((12, 32)\), затем еще раз, получив \((24, 32)\), затем еще раз, получив \((48, 32)\). Сумма 80 > 68.
4. \((3, 64)\) - Ваня может добавить 1 камень в первую кучу, получив \((4, 64)\). Сумма 68.

Таким образом, при \(S = 32\) у Вани есть выигрышная стратегия.

Ответ: 32

Задание 16

На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Ж?

Решение:

Чтобы найти количество путей из пункта А в пункт Ж, нужно посчитать количество путей, ведущих в каждый промежуточный пункт, и сложить их.

• В пункт Б можно попасть только из пункта А, поэтому количество путей равно 1.
• В пункт В можно попасть только из пункта Б, поэтому количество путей равно 1.
• В пункт Г можно попасть из пунктов Б и В. Количество путей в пункт Б равно 1, и количество путей в пункт В равно 1, поэтому общее количество путей в пункт Г равно 1 + 1 = 2.
• В пункт Д можно попасть из пунктов В и Г. Количество путей в пункт В равно 1, и количество путей в пункт Г равно 2, поэтому общее количество путей в пункт Д равно 1 + 2 = 3.
• В пункт Е можно попасть из пунктов Г и Д. Количество путей в пункт Г равно 2, и количество путей в пункт Д равно 3, поэтому общее количество путей в пункт Е равно 2 + 3 = 5.
• В пункт Ж можно попасть из пунктов Д и Е. Количество путей в пункт Д равно 3, и количество путей в пункт Е равно 5, поэтому общее количество путей в пункт Ж равно 3 + 5 = 8.

Таким образом, существует 8 различных путей из пункта А в пункт Ж.

Ответ: 8

Задание 19

Во фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите ID ребёнка Ивановой П.А.

Решение:

1. Находим ID Ивановой П.А. в таблице 1. ID Ивановой П.А. равен 1217.
2. Ищем ID 1217 в столбце «ID Родителя» таблицы 2.
3. Находим все строки, где «ID Родителя» равен 1217. Это строки с «ID Ребенка»: 1099, 1156.
4. Таким образом, детьми Ивановой П.А. являются люди с ID 1099 и 1156.

Ответ: 1099 1156

Задание 19

Во фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите ID ребёнка Ивановой П.А.

Подробное решение:

Для решения этой задачи необходимо проанализировать две таблицы базы данных: "Таблица 1" (содержащую информацию о людях, включая их ID и ФИО) и "Таблица 2" (содержащую информацию о родственных связях, а именно, ID родителя и ID ребенка).

1. Шаг 1: Идентификация ID Ивановой П.А.

   • Ищем в "Таблице 1" строку, где ФИО соответствует "Иванова П.А.".
   • Находим, что ID Ивановой П.А. равен 1217.

2. Шаг 2: Поиск детей Ивановой П.А. в "Таблице 2"

   • Теперь, когда мы знаем ID Ивановой П.А. (1217), ищем в "Таблице 2" все строки, где столбец "ID Родителя" содержит значение 1217.
   • Каждая такая строка указывает на ребенка Ивановой П.А. Значение в столбце "ID Ребенка" для этих строк и будет ID ребенка.

3. Шаг 3: Определение ID детей

   • Просматривая "Таблицу 2", находим две строки, где "ID Родителя" равен 1217:
     • В первой строке "ID Ребенка" равен 1099.
     • Во второй строке "ID Ребенка" равен 1156.

4. Шаг 4: Формулировка ответа

   • Следовательно, ID детей Ивановой П.А. - 1099 и 1156.

Ответ: 1099 1156

Задание 8

Определите класс соединений и дайте им названия:
1) MnCl2, 2) Mg(OH)2, 3) HF, 4) HCl, 5) MgCl2, 6) MgO, 7) Cu2O, 8) HNO3, 9) Cu(OH)2, 10) Cu(NO3)2, 11) H3PO4, 12) BaSO3, 13) CuO, 14) H2SO4, 15) Ba(OH)2, 16) H2SO3, 17) Al(OH)3, 18) BaO, 19) Al2(SO4)3, 20) Al2O3, 21) BaSO4

Решение:

1. MnCl2: Хлорид марганца(II), соль
2. Mg(OH)2: Гидроксид магния, основание
3. HF: Фтороводород, кислота
4. HCl: Хлороводород, кислота
5. MgCl2: Хлорид магния, соль
6. MgO: Оксид магния, основный оксид
7. Cu2O: Оксид меди(I), основный оксид
8. HNO3: Азотная кислота, кислота
9. Cu(OH)2: Гидроксид меди(II), основание
10. Cu(NO3)2: Нитрат меди(II), соль
11. H3PO4: Фосфорная кислота, кислота
12. BaSO3: Сульфит бария, соль
13. CuO: Оксид меди(II), основный оксид
14. H2SO4: Серная кислота, кислота
15. Ba(OH)2: Гидроксид бария, основание
16. H2SO3: Сернистая кислота, кислота
17. Al(OH)3: Гидроксид алюминия, амфотерный гидроксид
18. BaO: Оксид бария, основный оксид
19. Al2(SO4)3: Сульфат алюминия, соль
20. Al2O3: Оксид алюминия, амфотерный оксид
21. BaSO4: Сульфат бария, соль

Задание 9

Напишите уравнения реакций, с помощью которых можно осуществить следующие превращения:
a) Fe3O3 → Fe → X → Fe(OH)3
б) CuCl2 → X → Cu(NO3)2 → Cu
в) H2SiO3 → Na2SiO3 → SiO2 → X
г) P2O3 → X → K3PO4 → Ca3(PO4)2

Решение:

а) Fe3O3 → Fe → X → Fe(OH)3
1. Fe3O3 + 3CO → 2Fe + 3CO2 (восстановление оксида железа(III) угарным газом)
2. Fe + 2HCl → FeCl2 + H2 (растворение железа в соляной кислоте)
3. FeCl2 + 2NaOH → Fe(OH)2 + 2NaCl (получение гидроксида железа(II))
4. 4Fe(OH)2 + O2 + 2H2O → 4Fe(OH)3 (окисление гидроксида железа(II) до гидроксида железа(III))
* X = FeCl2 или Fe(OH)2

б) CuCl2 → X → Cu(NO3)2 → Cu
1. CuCl2 + 2AgNO3 → 2AgCl + Cu(NO3)2 (обменная реакция с нитратом серебра)
2. Cu(NO3)2 + Zn → Zn(NO3)2 + Cu (вытеснение меди цинком)
* X = Cu(NO3)2

в) H2SiO3 → Na2SiO3 → SiO2 → X
1. H2SiO3 + 2NaOH → Na2SiO3 + 2H2O (нейтрализация метакремниевой кислоты гидроксидом натрия)
2. Na2SiO3 + 2HCl → 2NaCl + H2SiO3 (получение метакремниевой кислоты)
3. H2SiO3 → SiO2 + H2O (разложение метакремниевой кислоты при нагревании)
4. SiO2 + 2NaOH → Na2SiO3 + H2O (взаимодействие диоксида кремния с гидроксидом натрия)
* X = Na2SiO3

г) P2O3 → X → K3PO4 → Ca3(PO4)2
1. P2O3 + 3H2O → 2H3PO3 (взаимодействие оксида фосфора(III) с водой)
2. H3PO3 + 3KOH → K3PO3 + 3H2O (нейтрализация фосфористой кислоты гидроксидом калия)
3. K3PO3 + Ca(NO3)2 -> Ca3(PO3)2 + KNO3 (обменная реакция)
* Ca3(PO3)2 - не существует, должен быть K3PO4 -> Ca3(PO4)2
4. 3K3PO4 + Ca3(NO3)2 -> Ca3(PO4)2 + KNO3 (обменная реакция)
* X = H3PO3