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

Photo

Задание 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

Photo

Задание 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

thinking img
progress gif

Текст скопирован
Готово
Ошибка
×