16 статей
Из теоремы об изменении импульса системы материальных точек `(Delta vecP_("c"))/(Delta t) = sum_i vecF_i` следует сохранение импульса или его проекций в следующих случаях:
если `sum_i vecF_i = vec 0`, то `vecP_("c")` остаётся неизменным по величине и направлению;
если существует направление `x` такое, что `sum_i F_(i,x) = 0`, то `P_(c,x) = "const"`.
Наконец, если на малом интервале времени внешние силы конечные и импульс этих сил за время действия во много раз меньше по величине импульса системы `|sum_i vecF_i| Delta t < < |vecP_("c") (t)|`, то из равенства
`Delta vecP_("c") = vecP_("c") (t + Delta t) - vecP_("c") (t) = (sum_i vecF_i) Delta t`
следует `Delta vecP_("c") ~~ vec 0`, т. е. сохранение импульса на рассматриваемом интервале времени `vecP_("c") (t + Delta t) = vecP_("c") (t)`.
Артиллерист стреляет ядром массы `m` так, чтобы оно упало в неприятельском лагере. На вылетевшее из пушки ядро садится барон Мюнхгаузен, масса которого `5m`. Какую часть пути до неприятельского лагеря ему придётся идти пешком?
Вы, конечно, догадались, что эта задача иллюстрирует последний из перечисленных случаев сохранения импульса системы. В процессе «посадки» барона на ядро на систему «ядро + барон» действуют внешние силы - это силы тяжести и силы сопротивления воздуха. Но барон столь ловок и устраивается на ядро столь быстро, что импульс этих конечных сил за время «посадки» барона на ядро значительно меньше по величине импульса `m vecv_0` ядра непосредственно перед «посадкой». Тогда скорость `vecv_0` ядра за мгновение до встречи со сказочным персонажем и скорость `vecv_1` системы «барон на ядре» связаны законом сохранения импульса системы
`m vecv_0 = 6m vecv_1`,
так что скорость ядра сразу после того, как Мюнхгаузен устроится на нём поудобнее, уменьшится в `6` раз. Следовательно, в такое же число раз уменьшатся: длительность полёта (равная удвоенному частному от деления начальной вертикальной составляющей скорости на величину ускорения свободного падения)и горизонтальная составляющая скорости. Дальность полёта, равная произведению этих величин, уменьшится в `36` раз, тогда оставшиеся после благополучного приземления `(35)/(36)` расстояния до неприятельского лагеря, барону предстоит пройти пешком!
На гладкой горизонтальной поверхности лежит соломинка массой `M` и длиной `L`. Жук массой `m` перемещается по соломинке с одного конца на другой. На какое расстояние `S` переместится соломинка?
Рассмотрим систему тел «жук + соломинка». На каждом элементарном промежутке времени приращение `Delta vecP_("c")` импульса этой системы равно суммарному импульсу действующих на систему внешних сил: т. е. сил тяжести и силы нормальной реакции
`Delta vecP_("c") = M Delta vecv_1 + m Delta vecv_2 = ((M + m) vecg + vec N) Delta t`,
здесь `vecv_1` - скорость соломинки, `vecv_2` - скорость жука. Обе скорости определены в лабораторной системе отсчёта. Сумма сил тяжести и нормальной реакции равна нулю. Тогда импульс системы «жук + соломинка» в процессе движения остаётся постоянным, равным своему начальному значению:
`M vecv_1 + m vecv_2 = vec 0`.
Поскольку задано перемещение жука в системе отсчёта, связанной с соломинкой, обратимся к правилу сложения скоростей `vecv_2 = vecv_1 + vec u`, здесь `vec u` - скорость жука относительно соломинки. Перейдём в этом равенстве к проекциям на горизонтальную ось, получим `v_(2,x) = v_(1,x) + u_(x')`.
С учётом правила сложения скоростей закон сохранения импульса принимает вид `Mv_(1,x) + m (v_(1,x) + u_(x')) = 0`, т. е. в любой момент времени
`v_(1,x) =- m/(M + m) u_(x')`.
Тогда элементарные перемещения: `Delta x_1 = v_(1,x) Delta t` - соломинки относительно лабораторной системы отсчёта и `Delta x' = u_(x') Delta t` - жука относительно соломинки, связаны соотношением `Delta x_1 =- m/(M + m) Delta x'`.
Суммируя элементарные перемещения по всему времени движения и переходя к абсолютным величинам, приходим к ответу на вопрос задачи
`S = m/(m + M) L`.
Клин массой `2m` и углом наклона к горизонту `alpha (cos alpha = 2//3)` находится на гладкой горизонтальной поверхности стола (см. рис. 12). Через блок, укреплённый на вершине клина, перекинута лёгкая нить, связывающая грузы, массы которых равны `m` и `3m`. Груз массой `3m` может скользить вдоль вертикальной направляющей `AB`, закреплённой на клине. Этот груз удерживают неподвижно на расстоянии `H = 27 sf"см"` от стола, а затем отпускают. В результате грузы и клин движутся поступательно. На какое расстояние `S` сместится клин к моменту удара груза массой `3m` о стол? Массы блока и направляющей `AB` считайте пренебрежимо малыми.
Рассмотрим систему тел «клин + грузы» (рис. 13).
На каждом элементарном промежутке времени приращение `Delta vecP_("c")` импульса системы равно суммарному импульсу действующих на систему внешних сил: тяжести и нормальной реакции горизонтальной опоры
`Delta vecP_("c") = (6 m vec g + vec N) Delta t`.
Проекции сил тяжести и нормальной реакции на горизонтальную ось нулевые. Следовательно, в процессе движения горизонтальная составляющая импульса системы «клин + грузы» остаётся постоянной, равной своему начальному значению - нулю:
`(2m + 3m) v_(x,sf"к") + mv_(x,sf"г") = 0`,
здесь `v_(x,sf"к")` - проекция скорости клина и груза массой `3m` на горизонтальную ось, `v_(x,sf"г")` - проекция скорости груза массой `m` на эту же ось. В системе отсчёта, связанной с клином, модули любых элементарных перемещений грузов равны вследствие нерастяжимости нити. Следовательно, в этой системе модуль перемещения лёгкого груза в проекции на горизонтальную ось за время движения равен `H cos alpha`. Тогда воспользуемся результатами предыдущей задачи. По правилу сложения скоростей `vecv_("г") = vecv_("к") + vec u`, здесь `vec u` - скорость лёгкого груза в системе отсчёта, связанной с клином. С учётом этого соотношения закон сохранения импульса принимает вид
`(2m + 3m) v_(x,sf"к") + m(v_(x,sf"к") + u_(x')) = 0`.
Отсюда находим связь проекций скорости
`v_(x,sf"к") = - m/(6m) u_(x') = - u_(x')/6`
и элементарных перемещений:
`Delta x_sf"к" =- (Delta x')/6`,
где `Delta x_sf"к"` - перемещение клина относительно лабораторной системы, `Delta x'` - проекция перемещения лёгкого груза на горизонтальную ось в системе отсчёта, связанной с клином. Суммируя элементарные перемещения по всему времени движения и переходя к абсолютным величинам, приходим к ответу на вопрос задачи
`S = (H cos alpha)/6 = (27*2)/(6*3) = 3 sf"см"`.
По клину массой `M`, находящемуся на гладкой горизонтальной плоскости, скользит шайба массой `m`. Гладкая наклонная плоскость клина составляет с горизонтом угол `alpha`. Определите величину `a_1` ускорения клина.
Для определения ускорения клина рассмотрим движение каждого из тел. Силы, приложенные к телам, указаны на рис. 14.
Запишем второй закон Ньютона для клина `M veca_1 = M vec g + vec P + vec R` и для шайбы `m veca_2 = m vec g + vec N`.
Переходя к проекциям сил и ускорений на оси ЛСО с учётом `vec P =- vec N` получаем
`Ma_(1x) = N sin alpha`, `ma_(2x) =- N sin alpha`, `ma_(2y) =- mg + N cos alpha`.
Скорость `vecv_2` шайбы в ЛСО, скорость `vec u` шайбы относительно клина и скорость `vecv_1` клина связаны законом сложения скоростей `vecv_2 = vecv_1 + vec u`. Дифференцируя это равенство по времени находим связь соответствующих ускорений `veca_2 = veca_1 + veca_("отн")`. Из треугольника ускорений (рис. 15) следует
`bbb"tg" alpha = (a_(2y))/(a_(2x) - a_(1x))`.
Подставляя в последнее равенство выражения для проекций ускорения шайбы
`a_(2x) =- M/m a_(1x)` и `a_(2y) =- g + a_(1x) M/m "ctg" alpha`,
после несложных преобразований приходим к ответу на вопрос задачи
`a_(1x) = 1/2 (m sin 2 alpha)/(M + m sin^2 alpha) g`.
Рассмотренные примеры подчёркивают важную роль законов сохранения.
Решение прямой задачи динамики, т. е. определение траектории по заданным силам и начальным условиям, упрощается в тех случаях, когда удаётся заменить уравнения Ньютона другими, эквивалентными им, но не содержащими ускорений. Эти уравнения, являющиеся математическим следствием уравнений Ньютона, и связывающие скорости (импульсы) точек с их координатами, называют законами сохранения. Проиллюстрируем это на примере задач о столкновениях частиц.
В физике под столкновениями понимают процессы взаимодействия между телами (частицами) в широком смысле слова, а не только в буквальном - как соприкосновение тел. Сталкивающиеся тела на большом расстоянии являются свободными. Проходя друг мимо друга, тела взаимодействуют между собой, в результате могут происходить различные процессы - тела могут соединиться в одно тело (абсолютно неупругий удар), могут возникать новые тела и, наконец, может иметь место упругое столкновение, при котором тела после некоторого сближения вновь расходятся без изменения своего внутреннего состояния. Столкновения, сопровождающиеся изменением внутреннего состояния тел, называются неупругими. Тела (частицы), участвующие в столкновении, характеризуются (до и после столкновения) импульсами и энергиями. Процесс столкновения сводится к изменению этих величин в результате взаимодействия. Законы сохранения энергии и импульса позволяют достаточно просто устанавливать соотношения между различными физическими величинами при столкновении тел. Особенно ценным здесь является то обстоятельство, что зачастую законы сохранения могут быть использованы даже в тех случаях, когда действующие силы неизвестны. Так обстоит дело, например, в физике элементарных частиц.
Происходящие в обычных условиях столкновения макроскопических тел почти всегда бывают в той или иной степени неупругими – уже хотя бы потому, что они сопровождаются некоторым нагреванием тел, т. е. переходом части их кинетической энергии в тепло. Тем не менее, в физике понятие об упругих столкновениях играет важную роль. С такими столкновениями часто приходится иметь дело в физическом эксперименте в области атомных явлений, да и обычные столкновения можно часто с достаточной степенью точности считать упругими.
Сохранение импульса тел (частиц) при столкновении обусловлено тем, что совокупность тел, участвующих в столкновении, составляет либо изолированную систему, т. е. на тела, входящие в систему, не действуют внешние силы, либо замкнутую: внешние силы отличны от нуля, а сумма внешних сил равна нулю. Несколько сложнее обстоит дело с применением закона сохранения энергии при столкновениях. Обращение к сохранению энергии требует порой учёта различных форм внутренней энергии.
Можно сказать, что действие законов сохранения импульса и энергии в процессах столкновения подтверждено широким спектром опытных данных.
Неупругие столкновения
Два куска пластилина массами `m_1` и `m_2`, летящие со скоростями `vecv_1` и `vecv_2` слипаются. Найдите наибольшее `Q_max` и наименьшее количество `Q_min` теплоты, которое может выделиться в результате абсолютно неупругого соударения.
Рассмотрим абсолютно неупругое соударение («слипание») тел, движущихся в ЛСО скоростями `vecv_1` и `vecv_2` соответственно. В процессе абсолютно неупругого соударения импульс системы сохраняется.
`m_1vecv_1+m_2vecv_2=(m_1+m_2)vecv`.
Отсюда находим скорость составного тела
`vecv=(m_1vecv_1+m_2vecv_2)/(m_1+m_2)`.
Закон сохранения энергии принимает вид
`(m_1vecv_1^2)/2+(m_2vecv_2^2)/2=((m_1+m_2)*vecv)/2+Q`.
Из приведенных соотношений находим убыль кинетической энергии
`Q=(m_1*m_2*(vecv_2-vecv_1)^2)/(2(m_1+m_2))=1/2 mu(vecv_2-vecv_1)^2`,
здесь `mu=(m_1m_2)/(m_1+m_2)` - приведенная масса системы тел.
Итак, при абсолютно неупругом соударении во внутреннюю энергию переходит кинетическая энергия тела приведенной массы, движущегося с относительной скоростью.
Убыль механической энергии достигает наибольшей величины
`Q_max=(m_1*m_2*(vecv_2-vecv_1)^2)/(2(m_1+m_2))=1/2 mu(v_1+v_2)^2`
при `vecv_1 uarr darr vecv_2`.
Убыль механической энергии будет наименьшей
`Q_min=(m_1*m_2*(vecv_2-vecv_1)^2)/(2(m_1+m_2))=1/2 mu(v_2-v_1)^2`
при `vecv_1 uarr uarr vecv_2`.
Упругие столкновения
На гладкой горизонтальной поверхности лежит гладкая шайба массой `M`. На него налетает гладкая шайба массой `m`, движущийся со скоростью `vec v`. Происходит упругий центральный удар шайб. Найдите скорости `vecv_1` и `vecv_2` шайб после соударения. При каком условии налетающая шайба будет двигаться после соударения в прежнем направлении?
Задачу рассмотрим в ЛСО, ось `Ox` которой направим по линии центров шайб в момент соударения. Внешние силы, действующие на шайбы в процессе соударения, это силы тяжести и силы нормальной реакции опоры. Их сумма равна нулю. Следовательно, импульс системы шайб в процессе взаимодействия не изменяется. По закону сохранения импульса `m vec v = m vecv_1 + M vecv_2`.
Переходя к проекциям на ось `Ox`, получаем `mv = mv_(1x) + Mv_2`, здесь учтено, что направление скорости `vecv_1` налетающей шайбы после соударения не известно. По закону сохранения энергии
`(mv^2)/2 = (mv_(1x)^2)/2 + (Mv_2^2)/2`.
Полученные соотношения перепишем в виде
`m(v - v_(1x)) = Mv_2`,
`m(v^2 - v_(1x)^2) = Mv_2^2`.
Разделив второе равенство на первое `(v != v_(1x))`, приходим к линейной системе `v_2 = v + v_(1x)`, `m(v - v_(1x)) = Mv_2`, решение которой имеет вид
`v_(1x) = (m - M)/(m + M) v`, `v_2 = (2m)/(m + M) v`.
Налетающая шайба будет двигаться после соударения в прежнем направлении `(v_(1x) > 0)` при `m > M`, т. е. если масса налетающей шайбы больше массы покоящейся шайбы.
Две гладкие упругие круглые шайбы движутся поступательно по гладкой горизонтальной поверхности со скоростями `vecv_1` и `vecv_2`. Найдите скорости `vecv_1^'` и `vecv_2^'` шайб после абсолютно упругого нецентрального соударения. Массы шайб `m_1` и `m_2`.
Задачу рассмотрим в ИСО, оси координат `Ox` и `Oy` которой лежат в горизонтальной плоскости, при этом ось `Ox` направлена по линии центров шайб в момент соударения (рис. 16).
В течение времени соударения на систему шайб действуют только вертикальные внешние силы: это силы тяжести и силы нормальной реакции. Их сумма равна нулю. Тогда импульс системы шайб в процессе взаимодействия сохраняется
`vecp_1 + vecp_2 = vecp_1^' + vecp_2^'`,
здесь `vecp_1 = m_1 vecv_1`, `vecp_2 = m_2 vecv_2`, `vecp_1^' = m_1 vecv_1^'`, `vecp_2^' = m_2 vecv_2^'` - импульсы шайб до и после соударения.
Так как шайбы идеально гладкие, то в процессе соударения внутренние силы -силы упругого взаимодействия - направлены только по оси `Ox`. Эти силы не изменяют `y`-составляющие импульсов шайб. Тогда из `p_(1y) = p_(1y)^'`, `p_(2y) = p_(2y)^'` находим `y`-составляющие скоростей шайб после соударения
`vecv_(1y)^' = v_(1y)`, `v_(2y)^' = v_(2y)`,
т. е. в проекции на ось `Oy` скорости шайб в результате соударения не изменились.
Найдём `x`-составляющие скоростей шайб после упругого соударения. При таком соударении сохраняется кинетическая энергия
`(m_1 (v_(1x)^2 + v_(1y)^2))/2 + (m_2 (v_(2x)^2 + v_(2y)^2))/2 = (m_1 ((v_(1x)^')^2 + (v_(1y)^')^2))/2 + (m_2 ((v_(2x)^')^2 + (v_(2y)^')^2))/2`.
С учётом равенства `y`-составляющих скоростей шайб до и после соударения последнее равенство принимает вид
`(m_1 v_(1x)^2)/2 + (m_2 v_(2x)^2)/2 = (m_1 (v_(1x)^')^2)/2 + (m_2 (v_(2x)^')^2)/2`.
Обратимся к закону сохранения импульса и перейдём к проекциям импульсов шайб на ось `Ox`
`m_1 v_(1x) + m_2 v_(2x) = m_1 v_(1x)^' + m_2 v_(2x)^'`.
Таким образом, исходная задача сведена к задаче об абсолютно упругом центральном ударе: именно такой вид приняли бы законы сохранения энергии и импульса, если бы скорости шайб были направлены по линии центров. Полученную нелинейную систему уравнений можно свести к линейной. Для этого следует (как и в предыдущей задаче) в обоих уравнениях по одну сторону знака равенства объединить слагаемые, относящиеся к первой шайбе, а по другую - ко второй, и разделить `(v_(1x) != v_(1x)^')` полученные соотношения. Это приводит к линейному уравнению
`v_(1x) + v_(1x)^' = v_(2x) + v_(2x)^'`.
Решая систему из двух последних уравнений, находим
`v_(1x)^' = ((m_1 - m_2) v_(1x) + 2m_2 v_(2x))/(m_1 + m_2)`,
`v_(2x)^' = (2m_1 v_(1x) + (m_2 - m_1) v_(2x))/(m_1 + m_2)`.
Полученные соотношения для `v_(1x)^'`, `v_(1y)^'` и `v_(2x)^'`, `v_(2y)^'` решают вопрос о проекциях и величинах скоростей шайб после соударения
`v_1^' = sqrt((v_(1x)^')^2 + (v_(1y)^')^2)`, `v_2^' = sqrt((v_(2x)^')^2 + (v_(2y)^')^2)`,
а также об углах `alpha_1` и `alpha_2`, которые векторы скорости `vecv_1^'` и `vecv_2^'` образуют с положительным направлением оси `Ox`:
`bbb"tg" alpha_1 = (v_(1y)^')/(v_(1x)^')`, `bbb"tg" alpha_2 = (v_(2y)^')/(v_(2x)^')`.
Построенное в общем виде решение задач упругого центрального и нецентрального соударений открывает дорогу к анализу целого ряда задач, для которых рассмотренная модель соответствует характеру взаимодействия тел (частиц).
Напомним вывод этой теоремы. По второму закону Ньютона
`m Delta vec v = vec F Delta t`.
Умножим обе части этого равенства скалярно на `vec v`, получим
`m (vec v * Delta vec v) = (vec F * vec v Delta t)`.
Это соотношение устанавливает равенство `Delta K = Delta A` на каждом элементарном перемещении приращения кинетической энергии
`Delta K = m ((vec v + Delta vec v)^2)/2 - m ((vec v)^2)/2 ~~ m(vec v * Delta vec v)`
и работы равнодействующей
`Delta A = (vec F * Delta vec r) = (vec F * vec v Delta t)`
на этом перемещении.
Суммируя такие равенства вдоль произвольной траектории, приходим к теореме об изменении кинетической энергии на конечных перемещениях:
На любых перемещениях приращение кинетической энергии материальной точки равно сумме работ всех сил
`K_2 - K_1 = sum_i A_i`.
Если среди сил есть потенциальные, то работа такой силы традиционно принимается равной взятому с обратным знаком приращению потенциальной энергии $$ A=-\left({П}_{2}-{П}_{1}\right)$$.
Из этих соотношений получаем теорему об изменении полной механической энергии (суммы кинетической и потенциальной энергий) материальной точки
$$ \left({П}_{2}+{K}_{2}\right)-\left({П}_{1}+{K}_{1}\right)=$$`sum_i A_(i sf"непотенц")`,
т. е. на любых перемещениях приращение полной механической энергии материальной точки равно сумме работ всех не потенциальных сил.
Отсюда следует: если не потенциальные силы отсутствуют или их работа равна нулю, то полная механическая энергия материальной точки, сохраняется.
Это утверждение - закон сохранения полной механической энергии материальной точки.
На заснеженном склоне с углом наклона `alpha` к горизонту коэффициент трения скольжения лыжника на высотах меньших `h` равен `mu_1 (mu_1 > "tg" alpha)`, на больших высотах коэффициент трения скольжения лыжника равен `mu_2 (mu_2 < "tg" alpha)`. С какой высоты `H` следует стартовать лыжнику с нулевой начальной скоростью, чтобы доехать до основания склона с нулевой конечной скоростью?
По условию `mu_2 < "tg" alpha`, `mu_1 > "tg" alpha`. Тогда при спуске лыжника на верхнем участке склона `F_(sf"тр"2) = mu_2 mg cos alpha < mg sin alpha`, лыжник движется равноускорено. На нижнем участке склона
`F_(sf"тр"1) = mu_1 mg cos alpha > mg sin alpha`,
лыжник движется равнозамедленно. При движении лыжника по склону от старта до финиша:
приращение потенциальной энергии, отсчитанной от нуля у основания склона, равно $$ {П}_{2}-{П}_{1}=-mgH$$,
приращение кинетической энергии `K_2 - K_1 = 0`, работа силы трения скольжения
`A_12 =- mu_2 mg cos alpha * (H - h)/(sin alpha) - mu_1 mg cos alpha h/(sin alpha) =`
`=- (mg)/("tg" alpha) (mu_2 H + (mu_1 - mu_2) h)`.
По теореме об изменении полной механической энергии
$$ \left({K}_{2}+{П}_{2}\right)-\left({K}_{1}+{П}_{1}\right)={A}_{12}$$.
В рассматриваемом случае `- mgH =- (mg)/("tg" alpha) (mu_2 H + (mu_1 - mu_2 )h)`.
Отсюда `H = (mu_1 - mu_2)/("tg" alpha - mu_2) h`.
В велокроссе участвуют `130` спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объём сообщения, записанного устройством, после того как промежуточный финиш прошли `75` велосипедистов?
Первым делом нужно определить, сколько бит необходимо для кодирования `130` номеров спортсменов. Поскольку номера записываются в некотором устройстве, количество бит для кодирования каждого номера обязательно должно быть целым: `H=log_2 130`. После округления результата в большую сторону получим число `8`. Следовательно, для кодирования `1` номера необходим `1` байт. Таким образом, информационный объём сообщения, записанного устройством, составляет `75` байт.
В некоторой стране автомобильный номер состоит из `7` символов. В качестве символов используют `18` различных букв и десятичные цифры в любом порядке.
Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов, при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.
Определите объём памяти, отводимый этой программой для записи `60` номеров.
Первое действие аналогично предыдущей задаче – нужно установить, каким количеством бит кодируется `1` символ. Всего используется `18` букв и `10` десятичных цифр, то есть `28` символов. По формуле Хартли `H=log_2 28`. После округления получается `5` бит на `1` символ. Вторым действием нужно узнать, какой объём памяти занимает `1` номер. Поскольку номер состоит из `7` символов, а каждый символ кодируется `5` битами, нам потребуется `35` бит памяти для хранения `1` номера. Однако по условию каждый номер должен записываться целым количеством байтов, а в каждом байте `8` бит. Ближайшее сверху к `35` число, делящееся на `8` – это число `40`, следовательно, на каждый номер отводится `5` байт. Таким образом, для записи `60` номеров программе потребуется `60*5 = 300` байт памяти.
Сигналы с судна на берег передают, используя различное положение рук. Каждая рука может быть поднята вверх, отведена в сторону или опущена вниз. Сколько различных сигналов можно подать двумя руками, если важно то, какая рука была в каком положении, но обе руки могут находиться и в одинаковом положении?
Главная ловушка этой задачи заключается в следующем неверном ходе мыслей: «Раз одной рукой передаётся `3` сигнала, значит, двумя в `2` раза больше, то есть `6`». На самом деле число исходов с добавлением новой руки увеличивается в `3` раза, поскольку можно продублировать все положения первой руки для каждого из `3` возможных положений второй. Таким образом, в ответе получается `9` сигналов.
В течение `5` секунд было передано сообщение, объём ко-торого составил `375` байт. Каков размер алфавита, с помощью кото-рого записано сообщение, если скорость его передачи составила `200` символов в секунду?
Первым делом найдём скорость передачи этого сообщения: `375//5 = 75` байт в секунду. Далее, нам известно, что в секунду передавалось `200` символов, которые занимают `75` байт памяти. Поэтому следующим действием найдём объём памяти, отводимый под `1` символ, переведя ответ в биты (ибо уже из входных чисел очевидно, что под каждый символ отводится менее `1` байта): `75^(**)8//200 = 600//200 = 3`. Таким образом, под каждый символ отводится `3` бита.
Применяя формулу Хартли, находим, что алфавит состоит из `8` символов.
Информация является одним из фундаментальных понятий современной науки наряду с такими понятиями, как «вещество» и «энергия».
Общее определение этому термину дать невозможно. Однако в раз-личных предметных областях даётся специализированное определение информации, подходящее для данной предметной области. В рамках этого задания мы будем говорить о математической теории информации и рассмотрим два подхода - содержательный (Клод Шеннон) и алфавитный (А.Н.Колмогоров). Начнём с определения понятия «инфор-мация» в каждом из этих подходов.
В содержательном подходе, информация - это снятая неопределённость. Неопределённость некоторого события - это количество возможных результатов (исходов) данного события.
Например, если мы подбрасываем вверх монету, то она может упасть двумя различными способами (орлом вверх или решкой вверх). Соответственно, у данного события два возможных исхода. Если же подбрасывать игральный кубик, то исходов будет шесть.
В алфавитном подходе информация - это сообщение (последовательность символов некоторого алфавита). Причём существенными являются только размер алфавита и количество символов в сообщении. Конкретное содержание сообщения интереса не представляет. Чаще всего алфавит является двоичным (состоит из `2` символов – «`0`» и «`1`»).
После таких определений понятия «информация» можно говорить об её измерении. Введём несколько основных единиц измерения информации.
Чаще всего в качестве основной единицы измерения информации используется бит. При алфавитном подходе один бит - это количество информации, которое можно передать в сообщении, состоящем из одного двоичного знака (`«0»` или `«1»`). С точки же зрения содержательного подхода один бит - это количество информации, уменьшающее неопределённость знания в два раза.
Наряду с битами можно использовать и другие единицы измерения информации, например, триты или диты. При алфавитном подходе один трит - это количество информации, которое можно передать в сообщении, состоящем из одного троичного знака `(«0»`, `«1»` или `«2»)`. С точки же зрения содержательного подхода один трит - это количество информации, уменьшающее неопределённость знания в три раза. Соответственно, один дит - это количество информации, уменьшаю-щее неопределённость знания в десять раз, и количество информации, которое можно передать в сообщении, состоящем из одного десятичного знака (арабской цифры). В некоторых задачах (например, в задаче взлома кодового замка) удобнее в качестве основной единицы измерения информации использовать не биты, а диты, поскольку угадывание каждой цифры из кода уменьшает количество комбинаций в `10` раз.
Для каждой основной единицы измерения информации существуют производные более крупные единицы измерения. Поскольку чаще всего мы будем использовать в качестве основной единицы бит, рассмотрим производные единицы измерения для бита. На практике чаще всего используется не бит, а байт.
`1` байт (`1`B) `= 8` бит;
Далее существует две линейки производных единиц для байта – линейка десятичных приставок и линейка двоичных приставок. В случае десятичных приставок каждая следующая единица измерения равна `1000` предыдущих единиц. Обозначаются десятичные приставки латинскими буквами (буква префикса из системы СИ и заглавная «B», обозначающая «байт») Итак:
`1` килобайт (`1` kB) `= 1000` B (1000 байт);
`1` мегабайт (`1` MB) `= 1000` kB ;
`1` гигабайт (`1` GB) `= 1000` MB;
`1` терабайт (`1` TB) `= 1000` GB;
`1` петабайт (`1` PB) `= 1000` TB;
`1` эксабайт (`1` EB) `= 1000` PB;
`1` зеттабайт (`1` ZB) `= 1000` EB;
`1` йоттабайт(`1` YB) `= 1000` ZB.
Более крупных единиц на настоящий момент не введено.
При использовании двоичных приставок, каждая следующая едини-ца измерения равна 1024 предыдущих единиц. В России принято обозначать двоичные приставки, записывая префикс заглавной русской буквой и после него слово «байт» целиком и тоже русскими буквами. За рубежом для обозначения двоичных приставок между префиксом и «B» добавляется маленькая буква «i» (от слова «binary»). Кроме того, все префиксы записываются заглавными буквами. Итак:
`1` кибибайт (`1` Кбайт, `1` KiB) `=2^10` байт `= 1024` байт;
`1` мебибайт (`1` Мбайт, `1` MiB) `=2^20` байт `= 1024` Кбайт;
1 гибибайт (`1` Гбайт, `1` GiB) `=2^30` байт `= 1024` Мбайт;
1 тебибайт (`1` Тбайт, `1` TiB) `=2^40` байт `= 1024` Гбайт;
1 пебибайт (`1` Пбайт, `1` PiB) `=2^50` байт `= 1024` Тбайт;
1 эксбибайт (`1` Эбайт, `1`EiB) `=2^60` байт `= 1024` Пбайт;
1 зебибайт (`1` Збайт, `1` ZiB) `=2^70` байт `= 1024` Эбайт;
1 йобибайт (`1` Йбайт, `1` YiB) `=2^80` байт `= 1024` Збайт.
Как уже упоминалось выше, в качестве основной единицы измерения информации мы будем использовать бит. Соответственно, с точки зрения алфавитного подхода мы будем кодировать информацию при помощи нулей и единиц (двоичных знаков).
Для того чтобы измерить количество информации в сообщении, надо закодировать сообщение в виде последовательности нулей и единиц наиболее рациональным способом, позволяющим получить самую короткую последовательность. Длина полученной последовательности нулей и единиц и является мерой количества информации в битах.
Поставим себе одну из наиболее часто встречающихся задач в теории информации. Пусть у нас есть `N` возможных равновероятных вариантов исходов некоторого события. Какое количество информации нам нужно получить, чтобы оставить только один вариант?
Например, пусть мы знаем, что некоторая интересная для нас книга находится на одной из полок нашего книжного шкафа, в котором `8` полок. Какое количество информации нам нужно получить, чтобы однозначно узнать полку, на которой находится книга?
Решим эту задачу с точки зрения содержательного и алфавитного подходов. Поскольку изначально в шкафу было `8` полок, а в итоге мы выберем одну, следовательно, неопределённость знания о местоположении книги уменьшится в `8` раз. Мы говорили, что один бит – это количество информации, уменьшающее неопределённость знания в `2` раза. Следовательно, мы должны получить `3` бита информации.
Теперь попробуем использовать алфавитный подход. Закодируем номера всех полок при помощи `0` и `1`. Получим следующие номера: `000, 001, 010, 011, 100, 101, 110, 111`. Для того чтобы узнать, на какой полке находится книга, мы должны узнать номер этой полки. Каждый номер состоит из `3` двоичных знаков. А по определению, `1` бит (в алфавитном подходе) – это количество информации в сообщении, состоящем из `1` двоичного знака. То есть мы тоже получим `3` бита информации.
Прежде чем продолжить рассмотрение поставленной общей задачи введём важное математическое определение.
Назовём логарифмом числа `N` по основанию `a` такое число `X`, что Обозначение:
`X=log_aN`.
На параметры логарифма налагаются некоторые ограничения. Число `N` обязательно должно быть строго больше `0`. Число `a` (основание логарифма) должно быть также строго больше нуля и при этом не равняться единице (ибо при возведении единицы в любую степень получается единица).
Теперь вернёмся к нашей задаче. Итак, какое же количество информации нам нужно получить, чтобы выбрать один исход из `N` равновероятных? Ответ на этот вопрос даёт формула Хартли: `H=log_aN`, где `N` – это количество исходов, а `H` – количество информации, которое нужно получить для однозначного выбора `1` исхода. Основание логарифма обозначает единицу измерения количества информации. То есть если мы будем измерять количество информации в битах, то логарифм нужно брать по основанию `2`, а если основной единицей измерения станет трит, то, соответственно, логарифм берётся по основанию `3`.
Рассмотрим несколько примеров применения формулы Хартли.
В библиотеке `16` стеллажей, в каждом стеллаже `8` полок. Какое количество информации несёт сообщение о том, что нужная книга находится на четвёртой полке?
Решим эту задачу с точки зрения содержательного подхода. В переданном нам сообщении указан только номер полки, но не указан номер стеллажа. Таким образом, устранилась неопределённость, связанная с полкой, а стеллаж, на котором находится книга, мы всё ещё не знаем. Так как известно, что в каждом стеллаже по `8` полок, следовательно, неопределённость уменьшилась в `8` раз. Следовательно, количество информации можно вычислить по формуле Хартли `H=log_2 8=3` бита информации.
Имеется `27` монет, одна из которых фальшивая и легче всех остальных. Сколько потребуется взвешиваний на двухчашечных весах, чтобы однозначно найти фальшивую монету?
В этой задаче неудобно использовать бит в качестве основной единицы измерения информации. Двухчашечные весы могут принимать три положения: левая чаша перевесила, значит, фальшивая монета находится в правой; правая чаша перевесила, значит, монета находится в левой; или же весы оказались в равновесии, что означает отсутствие фальшивой монеты на весах. Таким образом, одно взвешивание может уменьшить неопределённость в три раза, следовательно, будем использовать в качестве основной единицы измерения количес-тва информации трит.
По формуле Хартли `H = log _3 27 = 3` трита. Таким образом, мы видим, что для того чтобы найти фальшивую монету среди остальных, нам потребуется три взвешивания.
Логарифмы обладают очень важным свойством: `log_a(X*Y)=log_aX+log_aY`.
Если переформулировать это свойство в терминах количества информации, то мы получим закон аддитивности информации: Коли-чество информации`H(x_1, x_2)`, необходимое для установления пары `(x_1, x_2)`, равно сумме количеств информации `H(x_1)` и `H(x_2)`, необходимых для независимого установления элементов `x_1` и `x_2`:
`H(x_1,x_2)=H(x_1)+H(x_2)`.
Проиллюстрируем этот закон на примере. Пусть у нас есть игральная кость в форме октаэдра (с `8` гранями) и монета. И мы одновременно подбрасываем их вверх. Нужно узнать, какое количество информации несёт сообщение о верхней стороне монеты после падения (орёл или решка) и числе, выпавшему на игральной кости.
Игральная кость может упасть `8` различными способами, следовательно, по формуле Хартли можно вычислить, что, определив число, выпавшее на игральной кости, мы получаем `3` бита информации. Соответственно, монета может упасть только `2` способами и несёт в себе `1` бит информации. По закону аддитивности информации мы можем сложить полученные результаты и узнать, что интересующее нас сообщение несёт `4` бита информации.
Рассмотрим другой способ решения этой задачи. Если мы сразу рассмотрим все возможные исходы падения `2` предметов, то их будет `16` (кость выпадает `8` способами, а монета - орлом вверх, и кость выпадает `8` способами, а монета - решкой вверх). По формуле Хартли находим, что интересующее нас сообщение несёт `4` бита информации.
Если в результате вычислений по формуле Хартли получилось нецелое число, а в задаче требуется указать целое число бит, то результат следует округлить в большую сторону.
Всякий текст состоит из символов - букв, цифр, знаков препинания и т. д., - которые человек различает по начертанию. Однако для компьютерного представления текстовой информации такой метод неудобен, а для компьютерной обработки текстов - и вовсе неприемлем. Используется другой способ: все символы кодируются числами, и текст представляется в виде набора чисел - кодов символов, его составляющих. При выводе текста на экран монитора или принтер необходимо восстановить изображения всех символов, составляющих данный текст. Для этого используются кодовые таблицы символов, в которых для каждого символа устанавливается соответствие между его кодом и изображением. Все кодовые таблицы, используемые в любых компьютерах и любых операционных системах, подчиняются международным стандартам кодирования символов.
Основой для компьютерных стандартов кодирования символов послужил ASCII (American Standard Code for Information Interchange) - американский стандартный код для обмена информацией, разработанный в 1960-х годах и применяемый в США для любых видов передачи информации. В нём используется `7`-битное кодирование: общее количество символов составляет `2^7=128`, из них первые `32` символа - «управляющие», а остальные - «изображаемые», т. е. имеющие графическое изображение. Управляющие символы должны восприниматься устройством вывода текста как команды, например:
|
Cимвол |
Действие |
Английское название |
|
№7 |
Подача стандартного звукового сигнала |
Beep |
|
№8 |
Затереть предыдущий символ |
Back Space (BS) |
|
№13 |
Перевод строки |
Line Feed (LF) |
|
№26 |
Конец текстового файла |
End Of File (EOF) |
|
№27 |
Отмена предыдущего ввода |
Escape (ESC) |
К изображаемым символам в ASCII относятся буквы английского (латинского) алфавита (заглавные и прописные), цифры, знаки препинания и арифметических операций, скобки и некоторые специальные символы. Фрагмент кодировки ASCII приведён в таблице.
|
Символ |
Десятичный код |
Двоичный код |
Символ |
Десятичный код |
Двоичный код |
|
Пробел |
`32` |
`00100000` |
`0` |
`48` |
`00110000` |
|
`!` |
`33` |
`00100001` |
`1` |
`49` |
`00110001` |
|
# |
`35` |
`00100011` |
`2` |
`50` |
`00110010` |
|
$ |
`36` |
`00100100` |
`3` |
`51` |
`00110011` |
|
`**` |
`42` |
`00101010` |
`4` |
`52` |
`00110100` |
|
`+` |
`43` |
00101011 |
5 |
53 |
`00110101` |
|
, |
`44` |
`00101100` |
`6` |
`54` |
`00110110` |
|
`–` |
`45` |
`00101101` |
`7` |
`55` |
`00110111` |
|
. |
`46` |
`00101110` |
`8` |
`56` |
`00111000` |
|
/ |
`47` |
`00101111` |
`9` |
`57` |
`00111001` |
|
`A` |
`65` |
`01000001` |
`N` |
`78` |
`01001110` |
|
`B` |
`66` |
`01000010` |
`O` |
`79` |
`01001111` |
|
`C` |
`67` |
`01000011` |
`P` |
`80` |
`01010000` |
|
`D` |
`68` |
`01000100` |
`Q` |
`81` |
`01010001` |
|
`E` |
`69` |
`01000101` |
`R` |
`82` |
`01010010` |
|
`F` |
`70` |
`01000110` |
`S` |
`83` |
`01010011` |
|
`G` |
`71` |
`01000111` |
`T` |
`84` |
`01010100` |
|
`H` |
`72` |
`01001000` |
`U` |
`85` |
`01010101` |
|
`I` |
`73` |
`01001001` |
`V` |
`86` |
`01010110` |
|
`J` |
`74` |
`01001010` |
`W` |
`87` |
`01010111` |
|
`K` |
`75` |
`01001011` |
`X` |
`88` |
`01011000` |
|
`L` |
`76` |
`01001100` |
`Y` |
`89` |
`01011001` |
|
`M` |
`77` |
`01001101` |
`Z` |
`90` |
`01011010` |
Хотя в ASCII символы кодируются `7`-ю битами, в памяти компьютера под каждый символ отводится ровно `1` байт (`8` бит). И получается, что один бит из каждого байта не используется.
Главный недостаток стандарта ASCII заключается в том, что он рассчитан на передачу только текста, состоящего из английских букв. Со временем возникла необходимость кодирования и неанглийских букв. Во многих странах для этого стали разрабатывать расширения ASCII-кодировки, в которых применялись однобайтные коды символов; при этом первые `128` символов кодовой таблицы совпадали с кодировкой ASCII, а остальные (со `128`-го по `255`-й) использовались для кодирования букв национального алфавита, символов национальной валюты и т. п. Из-за несогласованности этих разработок для многих языков было создано по нескольку вариантов кодовых таблиц (например, для русского языка их около десятка).
Впоследствии использование кодовых таблиц было несколько упорядочено: каждой кодовой таблице было присвоено особое название и номер. Указав кодовую таблицу, автоматически выбирают и язык, которым можно пользоваться в дополнение к английскому; точнее, выбирается то, как будут интерпретироваться символы с кодами более `127`.
Для русского языка наиболее распространёнными являются однобайтовые кодовые таблицы СР-`866`, Windows-`1251`, ISO `8859-5` и КОИ-`8`. В них первые `128` символов совпадают с ASCII-кодировкой, а русские буквы помещены во второй части таблицы (с номерами `128-255`), однако коды русских букв в этих кодировках различны! Сравните, например, кодировки КОИ-`8` (Код Обмена Информацией `8`-битный, международное название «koi-`8`r») и Windows-`1251`, фрагменты которых приведены в таблицах на странице `13`.
Несовпадение кодовых таблиц приводит к ряду неприятных эффектов: один и тот же текст (неанглийский) имеет различное компьютерное представление в разных кодировках, соответственно, текст, набранный в одной кодировке, будет нечитабельным в другой!
Однобайтовые кодировки обладают одним серьёзным ограничением: количество различных кодов символов в отдельно взятой кодировке недостаточно велико, чтобы можно было пользоваться одновременно несколькими языками. Для устранения этого ограничения в 1993-м году был разработан новый стандарт кодирования символов, получивший название Unicode, который, по замыслу его разработчиков, позволил бы использовать в текстах любые символы всех языков мира.
В Unicode на кодирование символов отводится `32` бита. Первые `128` символов (коды `0-127`) совпадают с таблицей ASCII, все основные алфавиты современных языков полностью умещаются в первые `65536` кодов (`65536=2^16`), а в целом стандарт Unicode описывает все алфавиты современных и мёртвых языков; для языков, имеющих несколько алфавитов или вариантов написания (например, японский и индийский), закодированы все варианты; внесены все математические и иные научные символьные обозначения, и даже - некоторые придуманные языки (например, письменности эльфов и Мордора из эпических произведений Дж.Р.Р. Толкиена). Потенциальная информационная ёмкость Unicode столь велика, что сейчас используется менее одной тысячной части возможных кодов символов!
В современных компьютерах и операционных системах используется укороченная, `16`-битная версия Unicode, в которую входят все современные алфавиты; эта часть Unicode называется базовой многоязыковой страницей (Base Multilingual Plane, BMP).
|
`I=8000*16*128=1384000` бит `I=8000*16*128//8=2048000` байт `I=8000*16*128//8//1024=2000` Кбайт `I=8000*16*128//8//1024//1024~~1,95` Мбайт |
`1` мин `= 60` сек `~~64` сек `= 2^6` сек
`1000~~1024=2^(10)`
Итак, объём музыкального файла вычисляется по формуле
`I=f*r*k*t`,
где `f` – частота дискретизации, `r` – разрешение (глубина кодирования), `k` – количество каналов, `t` – время звучания.
Теперь применим полученные знания о представлении текстовой информации на практике. В языке программирования Паскаль для работы с текстовой информацией есть специальный символьный тип переменных, который называется char (от английского character). Переменные этого типа занимают в оперативной памяти по `1` байту и, соответственно, могут принимать `256` различных значений. Значениями переменных этого типа являются элементы какой-либо однобайтовой кодовой таблицы (например, KOI-`8` или Windows-`1251`). Какие именно символы являются значениями данного типа, зависит от того, какая кодовая таблица используется в момент выполнения (а не написания) программы. То есть одна и та же программа, например, печатающая изображение всех символов кодовой таблицы, на компьютерах с различными текущими кодировками будет иметь различные результаты работы.
Переменным символьного типа можно присваивать значения при помощи оператора присваивания. При этом есть два способа записи символьных констант. Первый способ – записать явное изображение символа, заключив его в апострофы. Пусть, например, переменная C имеет тип char. Присвоим ей значение: C:= 'a'; Описанный способ записи символьных значений удобно применять практически всегда. Единственный недостаток этого способа заключается в том, что так невозможно представить служебные символы, которые не имеют явных изображений (в кодовой таблице это первые `32` символа). Поэтому существует ещё один способ записи символьных констант – сначала указать спецсимвол решётку (#), а потом код интересующего нас символа. Например, C:=#13; Недостаток этого способа заключается в том, что нужно помнить коды всех символов, поэтому обычно его применяют только для записи символов без явного изображения.
Переменные типа char можно выводить на экран при помощи оператора вывода и вводить с клавиатуры. Апострофы при вводе набирать не нужно (каждый апостроф также будет считаться отдельным символом). Служебные символы вводятся следующим образом: нужно зажать alt и на правой цифровой клавиатуре набрать код символа (например, 13).
К переменным типа char можно применять операции сравнения (> , < , >= , <= , = , <>). При этом сравниваются коды символов и большим признаётся символ, имеющий больший код (то есть символ, находящийся дальше от нулевого). Результатом операции сравнения является логическое значение – true или false.
Существует `5` стандартных функций для работы с переменными символьного типа:
|
Функция |
Действие |
Тип аргумента |
Тип результата |
|
Ord(c) |
Выдаёт код символа |
Char |
Integer |
|
Chr(x) |
Выдаёт символ по коду |
Integer |
Char |
|
Succ(c) |
Выдаёт следующий символ кодовой таблицы. Не определена для последнего символа |
Char |
Char |
|
Pred(c) |
Выдаёт предыдущий символ кодовой таблицы. Не определена для нулевого символа |
Char |
Char |
|
Upcase(c) |
Если аргумент является строчной латинской буквой, превращает его в соответствующую заглавную. Иначе ничего не делает |
Char |
Char |
Тип char является порядковым, то есть для каждого символа можно назвать его порядковый номер в типе, а также следующий и предшествующий элементы типа. Например, символ '1' имеет код `49`, следующий символ – это '2', а предыдущий – '0'. Благодаря этому свойству переменные типа char могут использоваться в качестве счётчиков в цикле for. Например, распечатать все заглавные латинские буквы можно следующим образом:
For c:= 'A' to 'Z' do write (c);
где переменная c имеет тип char.
Если в цикле for используется слово to, то на каждом шаге цикла счётчик будет принимать следующее значение в типе, в случае же downto – предыдущее значение в типе.
Рассмотрим несколько примеров задач на символьные переменные.
Вывести на экран все символы кодовой таблицы.
Эту задачу можно решать двумя способами: перебрать все символы или все их коды – разница только в типе счётчика цикла.
Способ 1:
var c:char;
begin
for c:=#0 to #255 do
write(ord(c),'-',c,' ');
readln
end.
Способ 2:
var i:integer;
begin
for i:=0 to 255 do
write(i, '-',chr(i), ' ');
readln
end.
Дана последовательность символов, заканчивающаяся точкой. Подсчитайте сумму цифр, входящих в эту последовательность.
Эта задача демонстрирует очень важную вещь – как превратить символ-цифру в целое число. Это осуществляется следующим образом: необходимо вычислить код интересующего нас символа (например, код единицы `49`) и вычесть из него код символа «ноль». В любой кодировочной таблице символы-цифры идут подряд, поэтому, выполнив указанные действия, мы гарантированно получим числовое значение символа-цифры. Приведём полный текст решения.
var c: char; s: integer;
begin
s :=0;
read (c);
while c <> '.' do
begin
if (c >= '0')and(c <= '9')
then s:= s+ord(c)–ord('0');
read (c);
end;
writeln ('s=',s);
readln
end.
Дана непустая последовательность слов, состоящих из заглавных и строчных латинских букв в любом порядке. Между соседними словами запятая, за последним словом – точка. Никакие другие символы в последовательность не входят. Определить количество слов, которые начинаются на букву `Z`.
Это ещё один классический тип задач на обработку последовательностей символов. При её решении у нас возникнет конструкция из вложенных циклов: внутренний цикл анализирует слово, а внешний перебирает слова. Приведём полный текст решения.
var c:char; s:integer;
begin
s:=0;
repeat
read(c);
if c='Z' then s:=s+1;
repeat
read(c)
until (c=',')or(c='.')
until c='.';
writeln('s=',s);
readln
end.
Данный оператор представляет собой естественное расширение условного оператора. В общем виде он записывается следующим образом:
case <выражение порядкового типа> of
константа_1: оператор_1;
константа_2: оператор_2;
...
Константа_n: оператор_n;
else оператор
end
Слова: case, of, else, end - являются ключевыми словами языка. Выражение, стоящее между словами case и of, называется селектором и должно иметь порядковый тип. Тип является порядковым, если можно для каждого значения назвать порядковый номер в типе, предыдущее и следующее значение в типе (кроме первого и последнего значения в типе). Из известных нам стандартных типов порядковыми являются типы integer, longint, boolean и char. Тип real порядковым не является.
Работает оператор выбора следующим образом. Сначала вычисляется значение селектора, затем оно сравнивается с константами. В случае совпадения селектора с какой-нибудь константой выполняется оператор, стоящий после этой константы, далее управление переходит на следующий за case оператор программы. Если селектор не совпал ни с одной из констант, то выполняется оператор после слова else. Очевидно, что селектор и константы должны иметь одинаковые типы. Иначе невозможно будет провести операции сравнения.
Если нужно для многих различных значений селектора выполнить один и тот же набор команд, то можно не записывать множество строк с одинаковой правой частью, а перечислить константы через запятую, затем поставить двоеточие и один раз написать нужную последовательность команд. Если константы идут подряд, можно также записать их в виде диапазона: константа_1..константа_2. В этом случае команда будет выполняться при совпадении селектора с любой константой из диапазона. Граничные значения считаются включёнными в диапазон. Можно также указать несколько диапазонов через запятую.
Оператор выбора предполагает однозначный выбор варианта. То есть нельзя одной и той же константой пометить два различных варианта. Все константы должны быть различны. Особенно аккуратно следует обращаться с диапазонами. Широко распространённая ошибка – указывать одну и ту же константу в качестве начальной границы одного диапазона и конечной – другого. Однако поскольку границы входят в диапазон, получается, что это значение будет входить в два разных диапазона.
Последнее замечание заключается в том, что в отличие от оператора if перед else необходимо ставить точку с запятой. И кстати, аналогично оператору if, если в ветке else должен стоять пустой оператор, её можно не записывать. Приведём примеры нескольких различных операторов варианта.
case c of
'+': x := x + y;
'-': x := x - y;
'*': x := x * y;
else writeln('error')
end;
case c of
'a'..'z','A'..'Z': writeln('letter');
'0'..'9': writeln('digit')
end;
называется процесс, в котором участвуют две или более стороны, ведущие борьбу за реализацию своих интересов.
Согласно этому определению, довольно много жизненных ситуаций можно считать играми - для этого требуется лишь борьба двух или более лиц и какие-либо интересы, за которые эти лица ведут борьбу. Шахматы, домино, прыжки в высоту - всё это игры. Стремление занять свободное место в автобусе, соперничество мировых держав в ядерной сфере, беседа сотрудника ГИБДД с нарушителем, поход семейной пары в торговый центр - и это тоже игры. Так, в случае стремления занять свободное место в пустом автобусе в этом процессе участвуют не менее двух человек, которые ведут борьбу за свободные места (свои интересы), причём довольно часто количество свободных мест намного меньше количества участвующих в этой игре человек, поэтому в этой игре есть выигравшие и проигравшие. В этом случае интересы (занять свободное место) у игроков совпадают. Однако в случае игры «поход семейной пары в торговый центр» интересы часто строго противоположные: жене хочется совершить как можно больше покупок; мужу - потратить как можно меньше денег на эти покупки.
Изучение такого широкого класса игр математическими методам бессмысленно – в каждой игре есть свои мало-формализуемые особенности, а процесс принятия решений игроками может опираться не только на какие-то математические принципы, в него могут вписываться другие особенности человека, например, уровень интеллекта и характер.
Для решения спора Петя и Вася обращаются к компьютеру за случайным натуральным числом. Если выданное число - чётное, спор выигрывает Петя, если нечетное - спор выигрывает Вася. Является ли описанная процедура игрой?
Данная процедура тоже является игрой - два игрока ведут борьбу за свои интересы (выиграть спор), и то, как это они делают - неважно. Фактически, игроки с помощью компьютера реализовали подкидывание монетки.
Для решения спора Петя и Вася пишут цифры по очереди на доске слева направо, начинает Петя. Если после десяти ходов полученное `10`-значное число не делится на девять, в споре побеждает Петя, а если делится – Вася. Докажите, что Вася может выиграть спор.
Второй игрок (Вася) может дополнять число, написанное первым игроком, до девяти. Если ход Пети - «`9`», то ход Васи - «`0`» и т. п. После десяти ходов получим `10`-значное число, сумма цифр которого равна `9^(**)5=45`, и полученное число будет делиться на девять. Таким образом, второй игрок (Вася) сможет выиграть при любых ходах первого игрока (Пети).
Такие игры, в которых как играть - известно одному или обоим игрокам, уже представляют интерес для формализации и изучения. Одним из самых узких классов таких игр является класс математических игр. Этому классу и посвящено данное задание.
Будем называть игру математической, если для неё выполнены следующие условия:
Условие 1. В игре участвуют два игрока.
Условие 2. Игра заканчиваются выигрышем одного из участников. Это автоматически означает проигрыш соперника. Иногда в математических играх допускают ничью.
Условие 3. В игре участники ходят по очереди и помнят все предыдущие ходы.
Условие 4. Игра характеризуется позицией, которая зависит только от ходов игроков.
Вернёмся к примеру 1. Эта игра не будет являться математической, поскольку не будет удовлетворять только условию 4: мы не сможем определить позицию игры, которая будет зависеть только от хода самих игроков, поскольку игроки обращаются к компьютеру.
Также в математических играх по той же причине не может быть случайных карточных раскладов, игральных кубиков, подкидываний монеток. Попробуем же тогда реализовать игру из этого примера, которая является фактическим подкидыванием монетки игроками, без помощи, как монетки, так и компьютера.
Для решения спора Петя и Вася пишут на листочках по натуральному числу. Если сумма написанных чисел - чётная, спор выигрывает Петя, если нечетная - спор выигрывает Вася. Является ли описанная процедура математической игрой?
Здесь уже не выполняется условие 3, которое гласило, что игроки должны ходить по очереди и помнить все предыдущие ходы.
Сделаем небольшую модификацию условий игры, чтобы игра стала математической и посмотрим, какая игра из этого получится. Чтобы условие 3 поочередности выполнялось, сначала должен походить первый игрок, написать своё число на бумажке и показать это число всем, включая второго игрока. Кто из двух игроков будет первым, они между собой должны договориться сами. И тогда уже второй игрок, зная число, которое написал первый, должен написать своё число, затем эти два числа будут сложены и сумма проверена на чётность.
Однако, если второй игрок обладает хоть каким-либо интеллектом, он может подобрать своё число, чтобы сумма была выигрышной для него чётности. Суть «подкидывания монетки» от этого полностью теряется, т. к. данная игра находится под полным контролем второго игрока.
Два человека встречаются и обмениваются закрытыми сумками, понимая, что одна из них содержит деньги, другая - товар. Каждый игрок может уважать сделку и положить в сумку то, о чём договорились, либо обмануть партнёра, дав пустую сумку. Является ли эта игра математической?
Во-первых, эта игра не удовлетворяет условию 2: в условии не определено, какой игрок выигрывает в каком случае, а какой автоматически при этом проигрывает. Во-вторых, игроки ходят одновременно, а не по очереди, что нарушает условие 3. Поэтому данная игра не является математической.
Заметим, что условие 2 можно выполнить, считая, что в случае если один игрок обманул другого, обманувший игрок выиграл, а обманутый проиграл, в остальных случаях (оба игрока честные или оба обманщики) зафиксировать ничью. Однако условие 3, как и в предыдущем примере, уже нельзя выполнить без существенного изменения самой игры.
Итак, в математической игре имеются два игрока, которые ходят поочередно. Участник, который начинает игру, обычно называется первым игроком, его соперник – вторым. Имеется конечное или бесконечное множество позиций. В каждой позиции для обоих игроков указаны допустимые ходы – разрешённые переходы в другие позиции. Некоторые позиции объявляются выигрышными для какого-то игрока, что автоматически означает, что эти позиции являются проигрышными для соперника. Очень часто выигрышными объявляются те и только те позиции, из которых соперник не может сделать ход, т. е. выигрывает тот игрок, которому удаётся своим последним ходом достичь позиции, в которой у соперника нет допустимых ходов.
Есть две кучи по семь камней в каждой. За ход разрешается взять любое количество камней, но только из одной кучи. Проигрывает тот, кто не сможет сделать ход. Как можно определить позиции в данной игре, и какие позиции будут выигрышными?
Позицией в данной игре являются два числа `(x, y):` `x` – количество камней в первой куче, `y` – количество камней во второй куче. Игрок выигрывает, если противник не может сделать ход, т. е. перед ходом противника камней в обеих кучах не останется. Таким образом, позиция `(0, 0)` является выигрышной для того из игроков, который попал туда своим последним ходом.
Особенно отметим следующее.
Во-первых, в играх могут быть ничьи. Это значит, что некоторые позиции для обоих игроков объявляются ничейными. Игроку целесообразно добиваться ничьей только тогда, когда он не может гарантированно достичь выигрышной позиции.
Во-вторых, оба игрока не обязательно должны преследовать одинаковые цели (например, чтобы противник не смог сделать ход). Так, например, в примере 2 один из игроков стремится к тому, чтобы полученное число не делилось на девять, а второй стремится к обратному.
Поэтому позиция должна ещё характеризоваться номером игрока (либо того, который пришел в эту позицию, либо того, который делает ход из этой позиции в зависимости от ситуации). Так, если в примере 7 добавить номер игрока, который делает ход, то теперь позиция в этой задаче будет выражаться тремя числами `(x,y,n)`, где `n` – номер игрока, который делает ход, имея в начале $$ x$$ камней в первой куче, а $$ y$$ – во второй.
Позиция `(0,0,1)` будет проигрышной для первого игрока (он не может сделать ход) и выигрышной для второго, позиция `(0,0,2)` – наоборот.
Однако в играх, в которых игроки преследуют одинаковые цели и возможные ходы у обоих игроков одинаковы, как например, в примере 5, можно номер игрока из позиции опустить. В этом задании мы будем рассматривать только такие игры.
В точке 0 оси координат находится фишка. За ход игрок обязан подвинуть фишку на единицу влево или вправо. Выиграет тот игрок, после хода которого координата фишки превысит десять. Как определить позиции в данной игре? Какие позиции следует объявить выигрышными? Какие позиции следует объявить ничейными?
Позицией является целое число `(x):` положение фишки на оси. При этом все позиции с `x > 10` будут проигрышными для первого игрока, т. е., выигрышными для второго. Стартуя из позиции `(10)`, первый игрок может одним ходом передвинуть фишку в позицию `(11)` и выиграть. Если же игра начинается из позиции `(x)`, `[x < 10]`, то ни первый, ни второй игрок не могут гарантированно рассчитывать на победу, так как любой игрок в данной игре может не позволить своему противнику достичь выигрышной позиции, просто двигая каждый раз своим ходом фишку влево. Поэтому, стартуя из позиции `(x)`, `[x < 10]`, игра может закончиться выигрышем одного из игроков, если и только если соперник ошибётся. Но что следует считать исходом игры при старте, например, из начала координат (как в условии примера)? Можно было бы, например, считать, что исход игры при старте из начала координат просто не определён. Но мы потребуем выполнения более жёсткого условия.
Условие 5. При старте из любой допустимой позиции, как бы ни играли соперники, через конечное (возможно, очень большое) число ходов обязательно достигается либо выигрышная, либо ничейная позиция.
Иначе говоря, независимо от того, как играют оба игрока, через конечное число ходов игра должна закончиться выигрышем одного из соперников или ничьей.
Так, в примере 5 условие 5 выполняется, поскольку количество камней с каждым ходом уменьшается, а значит, когда-нибудь камней не останется, и один из игроков выиграет.
Для того, чтобы игра из примера 6 удовлетворяла условию 5, нужно кроме уже заданных выигрышных позиций `(x)`, `[x > 9]` объявить все позиции `(x)`, `[x < 10]` ничейными[1].
Чтобы избежать игр с бесконечным количеством ходов, мы можем, например, запретить игрокам ходы, приводящие к полному повторению ранее встречавшихся позиций. Или, наоборот, в таком случае объявлять ничью. Так, в шахматах троекратное повторение одной и той же позиции на доске является поводом для объявления ничьей (в случае, если это будет замечено одним из игроков).
[1] Таким образом, в примере 6 при старте из любой точки кроме точки `(10)` игроки не сделают ни одного хода, и немедленно будет объявлен результат.
Вернёмся к примеру 5 и зададимся вопросом: кто выиграет?
В общем случае может выиграть любой из игроков – для этого его сопернику достаточно «подыграть». Однако второй игрок может выиграть при любых ходах первого игрока. Для этого ему нужно брать то же количество камней, которое брал первый игрок предыдущим ходом, но из другой кучи. После хода второго игрока количество камней в обеих кучах будет равным. Далее. Первый игрок возьмёт несколько камней в одной из кучек, тогда после его хода количество камней в кучках станет неодинаковым, а значит, второй игрок сможет уравнять количество камней в кучах и передать ход сопернику. Второй игрок всегда сможет сделать свой ход, а поскольку камней становится все меньше и меньше, наступит момент, когда один из игроков не сможет сделать ход, и это будет первый игрок. Таким образом, второй игрок сможет выиграть в данный игре, как бы ни играл первый.
Выигрышной стратегией назовём набор правил, следуя которым, один из игроков обязательно выиграет при произвольных ответах соперника.
Аналогично, ничейной стратегией назовём набор правил, следуя которым, один из игроков обязательно выиграет или сведёт игру к ничьей при произвольных ответах соперника.
Подчеркнём в определении стратегии условие «при произвольных ответах соперника». Важно понимать, что на месте игрока может оказаться что или кто угодно, например, компьютер. Нужно уметь отвечать на произвольные ходы соперника и в любом случае выигрывать.
Как было сказано выше, мы пытались выделить игры, в которых один из игроков обязательно выиграет при произвольных ответах соперника. Следующая теорема позволяет утверждать, что математические игры и есть искомый класс игр.
В любой математической игре существует либо выигрышная стратегия одного из игроков, либо ничейная стратегия для обоих игроков.
Идея доказательства этого утверждения в частном случае будет рассмотрена при решении задач методом анализа с конца (см. § 3).
С одной стороны, заметим, что данная теорема обобщается на случай игр, которые теоретически могут продолжаться бесконечно долго. Для этого в условии теоремы вместо существования ничейной стратегии для обоих игроков нужно потребовать, чтобы каждый игрок имел стратегию, позволяющую данному игроку не проиграть.
С другой стороны, рассмотрим игры, которые завершаются за конечное количество ходов выигрышем одного из игроков (и ничьих нет). Согласно теореме, у кого-то из игроков обязательно существует выигрышная стратегия, и он должен выиграть у своего соперника, как бы ни играл последний. Введём понятие правильной игры.
называется игра, в которой каждый из игроков применяет выигрышную или ничейную стратегию, если она у него есть.
Так, если игроки из примера 2 играют в правильную игру, второй игрок должен воспользоваться своей выигрышной стратегией (например, дополнять число до девяти; у него может быть также и иная выигрышная стратегия) и довести игру до победы.
Таким образом, ответить на вопрос, заданный в самом начале (см. пример 1), кто выиграет при правильной игре, можно так: необходимо найти определённую стратегию одного из игроков и доказать, что она является выигрышной.
В заключение параграфа отметим, что согласно теореме выигрышная или ничейная стратегия существуют даже в таких математических играх, как шахматы и шашки. Однако ни человеческий ум, ни современные вычислительные мощности пока не позволили найти эту стратегию…
Одним из способов нахождения выигрышных стратегий является удачный ответ на ход противника, например, учитывающий симметрию.
Два игрока по очереди ставят на шахматную доску слонов так, чтобы фигуры не били друг друга. Цвет фигур значения не имеет. Проигрывает тот, кто не сможет сделать ход. Кто выиграет при правильной игре?
Выиграет второй игрок. Для этого мысленно разрежем шахматную доску пополам линией, параллельной одной из сторон доски. Второй игрок должен ставить слона на место, симметричное полю, на которое текущим ходом поставил свою ладью первый игрок относительно проведённой оси. Докажем от противного, что второй игрок всегда сможет сделать ход.
Пусть это неверно и второй игрок не сможет сделать хода. Разберём два случая.
Случай 1. На поле предполагаемого хода уже стоит слон. Но этот слон не мог быть поставлен ранее вторым игроком, так как он ставит слонов только симметрично ходам первого игрока. Если первый игрок ранее поставил слона на это поле, то второй игрок был обязан своим ходом поставить слона на поле, симметричное полю противника. Однако по условию на это поле слона поставил первый игрок текущим ходом. Получаем противоречие.
Случай 2. Данное поле находится под боем какого-то слона. Заметим, что этот слон не был поставлен первым игроком на предыдущем ходу, так как два симметричных относительно оси слона не бьют друг друга. Тогда, в соответствии со стратегией второго игрока, слон, расположенный симметрично данному, также должен уже стоять на доске. Однако этот слон будет бить слона, поставленного первым игроком предыдущим ходом. Противоречие.
Таким образом, было доказано, что у второго игрока всегда есть допустимый ход, а так как игра должна когда-нибудь закончиться (на шахматной доске всего 64 клетки), то первый игрок когда-то не сможет сделать своего хода и проиграет.
В кучке лежат: а) `30` камней; б) `32` камня. За ход можно взять от одного до пяти камней из кучи. Проигрывает тот, кто не сможет сделать ход. Кто выигрывает при правильной игре?
В данном случае работает стратегия дополнения до шести. Пусть своим ходом первый игрок берёт `x in{1,2,3,4,5}` камней. Тогда в пункте а) второй игрок отвечает ходом `(6-x)`, и поскольку после каждого его хода количество камней будет делиться на шесть, то в итоге второй игрок выиграет.
В пункте б) выигрывает первый игрок. Первым ходом он должен взять два камня и свести задачу к пункту а), в котором он уже будет выступать как второй игрок.
Два игрока перемещают ладью из левого нижнего угла `("a"1)` шахматной доски в правый верхний `("h"8)`. За ход можно сместить ладью на любое количество клеток вверх или вправо. Кто выиграет при правильной игре?
Выиграет второй игрок. Для этого ему нужно во время ходов возвращать ладью на диагональ, проведенную из левого нижнего угла в верхний правый угол. Подумайте, почему первый игрок проиграет при любых своих ходах.
Вторым важным способом решения задач является решение задачи с конца. Предположим (хотя это и не всегда верно), что для обоих игроков одни и те же позиции являются выигрышными.
Вернёмся к примеру 9.
Для нахождения выигрышной стратегии рассмотрим общую задачу. Считаем, что начальная позиция является параметром, и будем искать выигрышную стратегию при старте с этой позиции. Будем обозначать знаком «`-`» позиции, в которых при правильной игре участник, начинающий играть из данной позиции, выиграет, и знаком «`+`» отметим позиции, ведущие к поражению[1].
Если игра начинается в поле `"h"8`, первый игрок уже проиграл – это позиция «`+`» (рис. 1).
Далее, если игра стартует с полей `"h"1-"h"7` или `"a"8-"g"8`, то начинающий игрок может за один ход достичь поля `"h"8` и выиграть. Это позиция «`-`» (рис. 2).
Рассмотрим ладью, стоящую в поле `"g"7`. У первого игрока есть только два хода – `"g"8` и `"h"7`. Но в обеих этих позициях стоит «`-`». Следовательно, второй игрок, стартующий из этих позиций, выиграет. Как бы ни ходил первый игрок, он проиграет. Это снова позиция «`+`».
Далее, рассмотрим группы полей `"g"1-"g"6` и `"a"7-"f"7` (рис. 3). Стартуя из этих полей, первый игрок может за один ход попасть в поле `"g"7`, которое помечено знаком «`+`». Любой ход второго игрока из `"g"7` ведёт к его проигрышу.
Продолжая таким образом заполнять шахматную доску, мы видим, что знаки «`+`» размещаются на диагонали `"a"1-"h"8` (рис. 4). В поле a1 стоит знак «`+`», поэтому первый игрок потерпит поражение.
Зафиксируем общие правила расстановки знаков «`+`» и «`-`»:
1) знаком «`-`» обозначаются позиции, в которых при правильной игре участник, стартующий из данной позиции, выиграет, и знаком «`+`» отмечаются позиции, ведущие к поражению;
2) знак «`-`» ставится в позиции, из которой можно за один ход прийти в позицию со знаком «`+`»;
3) знак «`+`» ставится в выигрышных позициях, а также в тех позициях, из которых все возможные ходы ведут только в позиции, уже отмеченные знаком «`-`»[2].
Таким образом, сначала нужно расставить знаки «`+`» в выигрышных позициях. На втором этапе нужно отметить знаком «`-`» те позиции, которые отделяет от выигрышных один ход. На третьем этапе следует просмотреть все позиции и найти «тупиковые», ведущие к положениям, обозначенным знаком «`-`». На игровом поле обязательно будет хотя бы одна такая позиция[3]. Второй и третий этапы необходимо поочередно повторять до тех пор, пока начальная позиция не будет помечена знаком «`+`» или «`-`», что и даст ответ на вопрос, кто выиграет при правильной игре.
Как же должен действовать побеждающий участник игры? Он должен стремиться ходить в позиции, отмеченные знаком «`+`». При этом после очередного хода соперника он опять окажется в позиции со знаком «`-`», так как по определению знака «`+`» все возможные ходы из этой позиции ведут только в позиции со знаком «`-`». Таким образом, стратегия выигрывающего игрока формулируется просто: делать ход в позиции, обозначенные знаком «`+`». По определению знака «`-`» из этой позиции существует хотя бы один ход в позицию, отмеченную знаком «`+`», поэтому такой ход у выигрывающего игрока всегда будет в наличии.
Отметим следующий факт. Если известно, что игра длится не более чем `n` ходов при любых действиях первого и второго игроков, то начальная позиция обязательно будет помечена не более чем за `n` повторений шагов `2` и `3`. Это является идеей доказательства основной теоремы из § 2 в частном случае игр, в которых ничейных позиций нет, и каждая позиция является выигрышной для одного из игроков.
Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой – три камня, а во второй – два камня. У каждого игрока имеется неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в три раза число камней в какой-либо куче, или добавляет один камень в любую кучу. Выигрывает тот игрок, после хода которого, в двух кучах станет не менее `16` камней. Кто выиграет при правильной игре: игрок, сделавший первый ход, или игрок, сделавший второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Попробуем изобразить позиции графически. Рассмотрим таблицу, в которой количество камней в первой куче будет соответствовать номеру столбца, а количество камней во второй куче – номеру строки. Чёрным цветом выделена позиция `(2, 3)`, с которой должна начинаться игра в условии:
1. Выигрышные позиции – точки с координатами `x`, `y`, где `x + y ≥ 16`. Данные точки обозначим знаком «`+`» в таблице ниже[4].
2. Далее, ставим знак «`-`» в позиции, которые отделяет от выигрышных один ход.
По условию, можно либо увеличить одну из кучек в три раза, либо добавить камень в одну из куч, т. е. мы должны поставить знак «`-`» в позицию `(x, y)`, если верно одно из условий: `x+y+1≥16`; `x+3y≥16`; `y+3x≥16`.
3. После чего, ставим знак «`+`» в те позиции, из которых все ходы ведут только в позиции, обозначенные знаком «`-`». Таковыми будут позиции `(0, 5)`, `(5, 0)` и `(4, 3)`, `(3, 4)`.
4. Знак «`-`» ставим в те позиции, стартуя из которых можно за один ход дойти до одной из позиций, отмеченных знаков «`+`» (поставленных на этапе 3).
Стартуя из позиций `(4, 0)`, `(0, 4)`, `(3, 3)`, `(2, 4)`, `(4, 2)`, можно попасть в позиции, обозначенные знаком «`+`», увеличив количество камней в одной из кучек на единицу. Из позиций `(1, 4)` и `(4, 1)` можно прийти в позиции со знаком «`+`», увеличив в три раза количество камней в меньшей куче.
5. Знак «`+`» ставим в те позиции, из которых все ходы ведут только в позиции, обозначенные знаком «`-`». На этот раз таковыми будут позиции `(2, 3)` и `(3, 2)`.
В позиции `(2, 3)` был поставлен знак «`+`», а это значит, что победит второй игрок.
При оформлении задачи необходимо указать выигрывающего игрока, записать его стратегию и показать, что этот игрок победит при любых ответах соперника. Если имеется таблица позиций, то стратегия выигрывающего игрока формулируется простым правилом: делать ходы в позиции, отмеченные знаком «`+`». Но эту стратегию рекомендуется записать в явном виде. Таблицу позиций же, наоборот, при оформлении работы можно не рисовать (она уже сделала свое дело: помогла определить победителя и найти его стратегию).
Покажем, что второй игрок может выиграть при произвольных ответах первого игрока.
Рассмотрим все возможные начальные ходы первого игрока и укажем правильные ответы соперника:
а) если первый игрок в три раза увеличивает число камней в одной из куч, то второй игрок должен увеличить количество камней в этой же куче также в три раза. Тогда в обеих кучах будет как минимум 2*3*3+3=21 камень. Второй игрок побеждает. Рассмотрение этого случая закончено;
б) если первый игрок из позиции (2, 3) делает ход (2, 4) или (3, 3), то второй игрок должен пойти в позицию (3, 4) (именно она в нашем случае обозначена знаком «+»). Теперь первый игрок делает второй ход (заметим, этот ход не может быть выигрышным). Возможны три варианта:
- первый игрок увеличивает в три раза количество камней в одной из куч. Тогда второй игрок повторяет это действие с оставшейся кучкой камней, получает в сумме 21 камень и выигрывает,
- первый игрок добавляет один камень в первую кучу – позиция (4, 4). Тогда второй игрок увеличивает количество камней в одной из куч в три раза, получает в сумме 16 камней и выигрывает,
- первый игрок добавляет один камень во вторую кучу – позиция (3, 5). Тогда второй игрок увеличивает количество камней во второй куче в три раза, получает в сумме 18 камней и выигрывает.
Таким образом, второй игрок побеждает при любых ходах своего соперника.
Обратите внимание, что стратегию второго игрока можно придумать, не основываясь на таблице позиций. Важно помнить: если вы пропустите или не разберёте хотя бы один ход соперника (проигрывающего игрока), это может быть чревато тем, что данная стратегия может оказаться в корне неверной. Также нужно внимательно отнестись к расстановке знаков «`+`» и «`-`» в таблице позиций: один неверно поставленный знак может изменить ответ. Лучше не торопиться и расставить только те знаки, в которых вы уверены на данный момент. И не существенно, если вы не поставите никакого знака в данной позиции на определенном этапе (например, по правилам его необходимо поставить, но вы этого не заметили). Главное – не поставить неверного знака.
[1] «`+`»-позиции иногда называют `"P"`-позициями, а «`-`»-позиции – `"N"`-позициями по первым буквам английских слов «Previous» (предыдущий) и «Nеxt» (следующий), указывающими, какой из игроков выиграет при старте из этой позиции – игрок, который пришёл в эту позицию последним ходом, или игрок, совершающий следующий ход из этой позиции.
[2] Недопустимо, чтобы из этой позиции один ход вёл в позицию, обозначенную знаком «`+`», а другой – вёл в позицию, ещё не обозначенную ни одним из знаков.
[3] Хотя убедиться в этом непросто, мы предлагаем читателю самостоятельно подумать, почему это верно.
[4] Хотя таблица должна быть бесконечной (количество камней может быть сколь угодно большим), достаточно нарисовать таблицу `17` x `17` – случаи, когда в одной из куч более `16` камней, нас не интересуют, так как все эти позиции являются выигрышными.
Данный способ является разновидностью анализа с конца и заключается в том, что мы будем анализировать в знаках «`+`» и «`-`» не все позиции, а только те, в которые можно прийти из начальной позиции. Для этого мы нарисуем дерево ходов из начальной позиции. Разберём этот метод на примере 10.
Первоначальная позиция - `(2,3)`. За один ход из этой позиции можно прийти в позиции: `(3,3)`; `(2,4)`; `(6,3)`; `(2,9)`, добавляя один камень в одну из куч или умножая количество камней в куче на три.
Наша цель, в конечном счёте, во все эти позиции поставить знаки «`+`» и «`-`». Чтобы поставить знак «`+`», нужно быть уверенным, что все ходы из этой позиции ведут в «`-`»; для того, чтобы поставить знак «`-`», нужно, чтобы хотя бы один ход из этой позиции вел к «`+`».
Выше приведённое означает, что если из позиции за один ход можно прийти в позицию с количеством камней, не меньшим `16` (что по условию задачи равносильно выигрышу), это - позиция, выигрышная для первого игрока, т. е. позиция «`-`». В связи с этим знаки «`-`» можно поставить в позициях `(6,3)` и `(2,9)`, умножая количество камней в большей куче на `3`, мы получим `6^(**)3+3=21` и `2+9^(**)3=29` камней соответственно, и выиграем.
Мы не сможем такого утверждать для позиций `(3,3)` и `(2,4)`, поэтому отразим в дереве все позиции, в которые мы можем прийти из них ещё за один ход. Две из полученных после двух ходов позиций повторяются (это позиция `(3,4)`). Можно не делать дубликат позиции `(3,4)`, а провести к ней пути как из позиции `(2,4)`, так и из позиции `(3,3)`. А можно - оставить как есть, что в данном случае мы и сделаем.
Обозначим знаком «`-`» позиции, из которых можно дойти за один ход до выигрышных. Из оставшихся позиций продолжаем дерево дальше позициями, в которые можно попасть за три хода
Из всех полученных позиций можно за один ход дойти до выигрышных. Поэтому, в них можно поставить «`-`» и далее дерево ходов не продолжать. Теперь, посмотрим на позиции `(3,4)` и `(4,3)`. Все ходы в этих позициях ведут в позиции со знаком «`-`», т. е. в позиции, проигрышные для пришедшего в них игрока (и выигрышные для начинающего с них игрока). Поэтому, начинающий из такой позиции при правильной игре проиграет - это позиции «`+`».
После этого, отметим знаком «`-`» позиции `(3,3)` и `(2,4)` уровнем выше как позиции, из которых существует хотя бы один ход в позицию, отмеченную знаком «`+`». И, наконец, позицию `(2,3)` отметим знаком «`+`» как позицию, все ходы из которой ведут в позиции со знаком «`-`».
Таким образом, в позиции `(2,3)` стоит знак «`+`»[1], а это означает, что в данной игре выиграет второй игрок. Его стратегия формулируется тем же правилом, что и ранее: делать ходы в позиции, отмеченные знаком «`+`». Стратегия выигрывающего игрока в явном виде («образец оформления примера») уже была описана ранее. Аналогично анализу с конца обратим внимание, что важно построить дерево позиций до конца - пропуск любой, даже самой маленькой, ветви может существенно поменять всю расстановку знаков в вершинах дерева существенно поменять всю расстановку знаков в вершинах дерева и даже привести к тому, что победит другой игрок. Причём последнее не является редкостью.
Отдельно отметим, что хотя «анализ с конца» и «дерево игры» являются различными вариациями одной и той же идеи, в некоторых случаях быстрее действовать одним методом, а в некоторых - другим. Так, если в игре легко отобразить схематично всё множество позиций (например, на клетчатом листе), с другой стороны, количество ходов до выигрыша может быть довольно большим (см. пример 9), гораздо легче действовать методом «анализ с конца». В примере 10 решения обоими методами примерно идентичны по трудозатратам.
Однако, если известно, что игра всегда заканчивается за малое количество ходов - логичнее нарисовать дерево игры. Более того, если множество позиций сложно или невозможно каким-либо образом изобразить схематически (например, если не две кучи камней, а три кучи) - «анализ с конца» вообще малоприменим – нужно рисовать дерево игры или вообще решать задачу методом «удачный ход».
[1] Поскольку данное дерево игры заполнялось знаками по тем же правилам, что и таблица позиций, знаки «`+`» и «`-`» в позициях, отмеченных на дереве и в таблице позиций ранее, должны совпадать.
Данный параграф появился в связи с тем, что с 2015 года в ЕГЭ в задаче по теме теории игр требуется не только указать стратегию выигравшего, но и провести более подробный анализ, нарисовав дерево игры (о чём прямо сказано в условии) и ответив на дополнительные вопросы вида «из каких позиций выиграет первый игрок, причем ровно за два хода» или «какое максимальное количество ходов потребуется для выигрыша». Условие такой задачи в реальном ЕГЭ будет, скорее всего, очень длинным и занимать до страницы; однако этого не нужно бояться.
Два игрока играют в следующую игру. Перед игроками лежит куча из `S` камней, игроки по очереди могут за ход провести над кучей следующую операцию: добавить `1` или `4` камня в кучу или, если количество камней в куче чётно, увеличить количество камней в куче в `1,5` раза. Выигрывает игрок, после чьего хода в куче будет не менее `31` камня.
Укажите все значения `S`, при которых в правильной игре
А) Первый игрок может выиграть первым ходом.
Б) Второй игрок может выиграть первым ходом.
В) Первый игрок может выиграть вторым ходом, при этом он не может выиграть своим первым ходом.
Г) Найдите хотя бы одно значение `S`, при котором в правильной игре выигрывает второй игрок, при этом он не может выиграть своим первых ходом.
Нарисуем клеточную прямую и отметим знаком «`+`» выигрышные позиции в конце игры - позиции с количеством камней не менее `31`. Далее отметим знаками «`-`» позиции, из которых до указанных можно дойти за `1` ход: это позиция (`30`), из которой можно выиграть ходом «добавить `1` камень», позиции `(30)`, `(29)`, `(28)`, `(27)` из которых выиграть ходом «прибавление `4` камня» и позиции `(22)`, `(24)`, `(26)`, `(28)`, `(30)`, из которых можно выиграть за ход «увеличить кучу с чётным количеством камней в `1,5` раза»[1]. Из некоторых позиций, как видно выше, существует сразу несколько выигрышных ходов, однако это неважно: должен существовать хотя бы один. Чтобы отличать эти отмеченные позиции от всех других, добавим ещё цифру «`1`» к позиции для удобства, получив «`-1`».
Найдя позиции, которые подпадают под условие пункта А), перейдём к пункту Б). Нас интересует не просто дальнейшая расстановка плюсов и минусов в позициях, а ещё и количество ходов до выигрыша. Фраза «второй игрок выиграет первым ходом» означает, что из данных позиций не должно быть ходов ни в какие другие позиции, кроме как в позиции, отмеченные знаком «`-1`», т. е. позиции, из которых второй игрок сможет выиграть за один ход. Такие позиции лучше перебрать следующим образом:
Сначала отметим все пустые позиции знаком «?», из которых существует хотя бы один ход до позиций, уже отмеченных знаком «`-1`». Ходом «добавить один камень» можно за ход попасть в указанное множество из позиций `(25)`, `(23)`, `(21)`; ходом «добавить `4` камня» за ход можно попасть из позиций `(25)`, `(23)`, `(20)`, `(18)`, и ходом «увеличить в `1,5` раза» - из позиций `(16)`, `(18)`, `(20)`.
Теперь для каждой из отмеченных «?» позиций проверим условие, что все допустимые ходы идут в нарисованное множество минусовых позиций.
`(16)`, `(18)`, `(20)` - ход «`+1`» противоречит условию выше;
`(21)` - ход «`+4`» противоречит условию выше;
`(23)`, `(25)` - подходят. Таким образом `(23)`, `(25)` - являются позициями, в которых второй игрок выиграет за один ход. В этих позициях будет стоять знак «`+`» как в позициях, откуда все ходы идут в позиции со знаком «`-1`».
Теперь, перейдём к пункту В). Перед этим сотрём все знаки «?», поскольку в позициях, отличных от `(23)` и `(25)` нам неизвестно, существует ли хотя бы один ход, ведущий в минусовую позицию.
Первый игрок выиграет вторым ходом тогда и только тогда, когда не может выиграть за ход, но может прийти в позицию, из которой он, как второй игрок, выиграет первым ходом. Эти позиции уже найдены - это позиции `(23)` и `(25)`. Таким образом, нас интересуют все позиции, из которых можно за ход дойти до `(23)` и `(25)`. Это позиции `(19)`, `(21)`, `(22)`, `(24)`. Однако из позиций `(22)` и `(24)` в данный момент уже отмечены знаком «`-`», то есть из них можно выиграть за ход, а нас интересуют в данном пункте позиции, где за ход выиграть нельзя. Таким образом, в пункте В). Ответ - позиции `(19)` и `(21)`.
Наконец, в пункте Г) нас интересуют позиции, в которых выиграет второй игрок, т. е. позиции «`+`». Отметим отличие пункта Г) от пункта Б). В пункте Г) нас интересуют позиции, в которых второй игрок выиграет и он не сможет выиграть первым ходом, как бы не ходил его соперник. В пункте Б) же нас интересуют позиции, в которых второй игрок сможет, наоборот, выиграть первым ходом как бы не ходил его соперник. Позиции «`+`», где в зависимости от хода первого игрока второй сможет выиграть как первым своим ходом, так и не первым, нас не интересуют ни в пункте Б), ни в пункте Г).
Для решения пункта Г) просто продолжим заполнять согласно правилам таблицу позиций.
Нас интересует позиция, в которой выиграет второй игрок, то есть позиция «`+`». С другой стороны, нас интересует позиция, из которой второй игрок не сможет выиграть своим первым ходом. Это означает, что первый игрок всеми своими ходами должен ходить в минусовые позиции, но ни одним своим ходом не сможет походить в позиции «`-1`», из которых существует выигрышный ход. Этим свойством будет обладать, например, позиция `(15)` - возможные ходы из неё будут вести в позиции `(16) ` и `(19)`, отмеченные знаком «`-`», а не «`-1`». Это будет наибольшей позицией, обладающей таким свойством - из позиций `(18)` и `(20)`, выигрышных для второго игрока, существует ход первого игрока «`1,5x`», приводящий к позициям `(27)` и `(30)`. Из этих позиций можно выиграть за ход.
А) `(22), (24), (26), (27), (28), (29), (30)`;
Б) `(23), (25)`;
В) `(19), (21)`
Г) Например, `(15)`.
Два игрока играют в следующую игру. Перед игроками лежит две кучи: в первой куче `5` камней, во второй куче - `S` камней. Игроки по очереди могут за ход провести над одной из куч следующую операцию: добавить `2` камня в кучу или, если количество камней в куче чётно, увеличить количество камней в куче в `2,5` раза. Выиграет игрок, после чьего хода суммарное количество камней в обеих кучах будет не менее `39`.
Укажите все значения `S`, при которых в правильной игре
А) Первый игрок может выиграть первым ходом
Б) Второй игрок может выиграть первым ходом.
В) Первый игрок может выиграть вторым ходом, но не может выиграть первым ходом.
Данный пример очень похож по условию на пример 11, однако здесь возникает проблема в том, что количество куч - две, хоть и задано, что изначально в первой куче `5` камней. Если рассматривать двумерную таблицу позиций, это приведёт к побочному анализу многих позиций, в которых количество камней в первой куче отлично от пяти (в примере 11 таких «лишних» позиций не было). Построение дерева игры также не приведёт к быстрому результату, т. к. начальная позиция неизвестна, и такие деревья нужно будет рисовать при каждом `S`.
В связи с этим проведём предварительный анализ игры, не пользуясь ни таблицей позиций, ни деревом игры.
А) Первый игрок выиграет за ход. Первый игрок не может увеличить количество камней в кучке из `5` камней в `1,5` раза. Следовательно, его возможные ходы – это либо добавление камней к одной из куч, либо увеличение количества камней в второй куче в `2,5` раза. В первом случае суммарное количество камней до увеличения должно равняться `37` или `38` (т. е. во второй куче `32` или `33` камня). Во втором случае: пусть `x` – количество камней во второй куче. Тогда `x` - чётно и `2,5x+5>=40`, откуда `x>=14`. Следовательно, возможное количество камней во второй куче, при котором первый игрок победит за ход - `14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 33` (больше `33` нельзя, т. к. изначальное суммарное количество камней должно быть меньше `39`, чтобы игра имела смысл).
Б) Второй игрок выиграет за ход. Это должны быть позиции, при которых первый игрок не сможет выиграть за ход, а второй игрок – сможет выиграть за ход после любого хода первого игрока. Рассмотрим все возможные ходы первого игрока:
– первый игрок увеличивает количество камней в куче с `S` камнями на `2` (этот ход второй игрок может применить в любой ситуации). Тогда второй выиграет, если после этого `S` станет равно `14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 33` (см. предыдущий пункт, количество камней в первой куче не менялось), т. е. изначально `S` могло быть равно `12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 31`.
Из этих вариантов числа камней `S` только варианты `12,31` соответствуют тому, что первый игрок не может выиграть своим первым ходом. Будем далее рассматривать только `S=12`, `S=31` и проверим оставшиеся возможные ходы первого игрока.
Проверим `S=12:`
– первый игрок увеличивает количество камней в куче с `S` камнями в `2,5` раза, получив `30` камней во второй куче. В таком случае второй игрок сможет выиграть за ход, также увеличив количество камней в этой куче в `2,5` раза.
– первый игрок увеличивает количество камней в куче с `5` камнями в `2,5` раза: невозможный ход.
– первый игрок увеличивает количество камней в первой куче на `2`. Таким образом, в первой куче - `7` камней, во второй - `12`. Однако в данном случае второй игрок не сможет выиграть - ни один из его ходов не приводит к ситуации, когда суммарное количество камней после его хода не менее `39`.
`S=12` не подходит. Проверим `S=31:`
– первый игрок увеличивает количество камней в куче с `S` камнями в `2,5` раза: невозможный ход.
– первый игрок увеличивает количество камней в куче с `5` камнями в `2,5` раза: невозможный ход.
– первый игрок увеличивает количество камней в куче с `5` камнями на `2`. Тогда второй игрок также увеличит количество камней в одной из куч на `2`, получит суммарное количество камней - `39`, и победит!
`S=31` подходит.
В) Первый игрок выиграет вторым ходом. После своего хода он должен прийти в позицию, из которой он (будучи «вторым» игроком), сможет выиграть за ход (т. е. в позицию, соответствующую п. Б).
Если после хода первого игрока количество камней в первой куче останется равным `5`, то мы придём в ситуацию предыдущего пункта (после хода первого игрока, если они поменяются ролями, первому игроку, находящемуся в роли второго игрока, нужно выиграть за оставшийся ход). Ответ пункта Б) гласит, что после хода первого игрока количество камней во второй куче должно стать `31`. Единственная возможная ситуация - `29` камней.
Заметим, что при начальном количестве в `5` камней для первой кучи и `29` камней во второй куче единственно возможные ходы - добавления по `2` камня к одной из куч. При этом никогда чётного количества камней в какой-либо из куч не получится, и применить ход «увеличить в `2,5` раза» также будет невозможно. Поэтому при любых ходах как первого, так и второго игрока, через три хода суммарное количество камней станет `29+5+2+2+2=40`, поэтому игра закончится за три хода победой первого игрока (своим вторым ходом).
Второй случай - если первый игрок в правильной игре своим ходом поменяет количество камней в куче единственно возможным ходом «`+2` камня», при этом после хода первого игрока получится `7` камней в первой куче и `S` - во второй. После этого мы должны для начала полностью повторить анализ, по образцу предыдущего пункта. Рассмотрим следующий ход второго игрока:
– второй игрок увеличивает количество камней в куче с `S` камнями на `2`. Тогда первый выиграет, если после этого `S` станет равно `14, 16, 18, 20, 22, 24, 26, 28, 30, 31 ` `(2,5x+7>=39)`, т. е. изначально `S` могло быть равно `12, 14, 16, 18, 20, 22, 24, 26, 28, 29`.
Из этих вариантов числа камней `S` только варианты `12, 29` соответствуют тому, что второй игрок не может выиграть своим первым ходом. Вариант `S=29` уже был рассмотрен ранее - он подходит. Рассмотрим `S=12` и оставшиеся возможные ходы второго игрока.
– второй игрок увеличивает количество камней в куче с `12` камнями в `2,5` раза. При этом он получит `30` камней во второй куче, и `37` - суммарно в обеих кучах. Любой ход первого игрока приведёт к выигрышу.
– первый игрок увеличивает количество камней в первой куче в `2,5` раза: невозможный ход, т. к. `7` - нечётное число.
– первый игрок увеличивает количество камней в первой куче на `2`. Таким образом, в первой куче - `9` камней, во второй - `12`. В данном случае первый игрок сможет выиграть за ход, увеличив количество камней во второй куче, `12`, в `2,5` раза: `9+30 = 39` камней, ровно столько, сколько и требуется для победы. Любой другой ход первого игрока приведёт к тому, что после этого его соперник увеличит в `2,5` раза кучу из `12` или `14` камней и победит, т. о., этот ход не является ходом первого игрока при правильной игре (см. замечание после данной задачи).
Итак, `S=12` будет подходить под условие «первый игрок всегда выиграет вторым ходом», если первым ходом первый игрок увеличит количество камней в первой куче с `5` до `7`. Заметим, что все остальные ходы первого игрока `(12->14; 12->30)` приведут к тому, что второй игрок увеличит количество камней во второй куче в `2,5` раза и выиграет с суммарным количеством камней `40` и `80`. Следовательно, такие ходы первого игрока не могут быть ходами в правильной игре.
А) `S=14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 33`;
Б) `S=31`;
В) `S=12,29`.
[1] Если в условии явно просят объяснить, откуда возникают вышеуказанные позиции и почему других таких позиций нет (это встречено автором в демоверсии ЕГЭ 2015), желательно выписать возникающие неравенства и их решить. Иначе в случае сильно строгой проверки можно недосчитаться первичных баллов на пустом месте. Так, в случае хода «умножить кучу с чётных количеством камней на 1,5» нужна система условий, состоящая из 1) неравенства (невыигрышная априори); 2) неравенства (можно дойти за 1 ход до выигрышной) и 3) чётно.
Уравнение вида `ax^4+bx^3+cx^2+-bx+a=0` называется возвратным.
Чтобы его решить, надо вынести за скобку `x^2`. Тогда выражение в скобке приведётся к квадратному уравнению относительно `x+-1/x`:
`ax^4+bx^3+cx^2+-bx+a=0hArrx^2(ax^2+bx+c+-fracbx+fraca{x^2})=0hArr`
`a(x^2+frac1{x^2}+2-2)+b(x+-frac1x)+c=0`.
При этом,
`ax^4+bx^3+cx^2-bx+a=0hArra(x-frac1x)^2+b(x-frac1x)+(c+2a)=0`
`ax^4+bx^3+cx^2+bx+a=0hArra(x+frac1x)^2+b(x+frac1x)+(c-2a)=0`.
Решите уравнение `t^4+8t^3+6t^2-8t+1=0`.
Уравнение является возвратным. Вынесем за скобку `t^2`, а затем оставшееся выражение в скобке группировкой сведется к квадратному трёхчлену:
`t^2(t^2+8t+6-frac8t+frac1{t^2})=0hArrt^2+frac1{t^2}+8t-frac8t+6=0hArr`
` iff(t^2-2+frac1{t^2})+8(t-frac1t)+8=0hArr(t-frac1t)^2+8(t-frac1t)+8=0hArr`
`iff t-1/t=-4+-2sqrt2 iff`
.
Найдите все значения параметра `a`, при каждом из которых уравнение `x^2-6|x|-a+6=0` имеет ровно два различных решения.
Первый способ – решение «в лоб».
Чтобы уравнение `x^2-6|x|-a+6=0` имело ровно два различных решения, необходимо и достаточно, чтобы уравнение `t^2-6t-a+6=0` `t=|x|`, имело одно положительное решение. Это возможно, если
`1`. Или дискриминант `=0` и единственный корень положителен:
`2`. Или дискриминант положителен, но корни имеют разные знаки (тогда отрицательный корень нам не подходит):
Это очень удобно, потому что легко строить эскиз графика оставшегося квадратного трёхчлена, не думая о дискриминанте.
Теперь построим график функции `y=t(t-6)` - рис. 9. |
| Рис. 9 |
С помощью эскизов графиков можно рассматривать некоторые типы уравнений и неравенств. Приведём примеры таких задач.
Найдите все значения параметра `a`, при каждом из которых уравнение
`x^2+f^2(a)x-g(a)=0`
имеет единственное положительное решение.
Перепишем уравнение в другом виде: `(x+f^2(a))x=g(a)`. Построим эскиз левой части – рис. 10.
 |
| Рис. 10 |
Видно, что условию задачи удовлетворяют все положительные значения правой части, т. е.
`g(a)>0`.
Найдите все значения параметра `a`, при каждом из которых уравнение
`x^2+f^2(a)x-g(a)=0`
имеет два отрицательных решения.
Перепишем уравнение в другом виде: `(x+f^2(a))x=g(a)`. Построим эскиз левой части – рис. `10`. Видно, что условию задачи удовлетворяют те значения `g(a)`, которые лежат между значениями левой части в вершине и числом `0`, т. е.
`y(-frac{f^2(a)}2)<g(a)<0hArr-(-frac{f^2(a)}2)^2<g(a)<0`.
Найдите все значения параметра `a`, при каждом из которых неравенство
`x^2-f^2(a)x-g(a)<=0`
имеет единственное положительное решение.
Перепишем неравенство в другом виде: `(x-f^2(a))x<=g(a)`. Построим эскиз левой части – рис. 11. Видно, что условие задачи выполнено только тогда, когда `g(a)` равно значению левой части в вершине, т. е.
`g(a)=y(frac{f^2(a)}2)=-(frac{f^2(a)}2)^2`.
 |
| Рис. 11 |
