СПРОСИ ПРОФИ

Мокин Александр Борисович

Информатика, программирование, математика, олимпиады по информатике, спортивное программирование, …
Выполнено заказов: 34, отзывов: 12, оценка: 4,75
Россия, Москва
Вопросов0
Ответов 20
Рейтинг 19

Ответы:


👍
0
👎

Ответ на «Комбинаторика: способ рассадки людей на плацу»

Я только что проверил на компьютере, хороших шаблонов 93, как я говорил.

👍
+1
👎

Ответ на «Комбинаторика: способ рассадки людей на плацу»

В моём решении нигде не фигурировало общее количество шаблонов. Я считал количество шаблонов, где Б не стоят подряд, а затем вычел из него количество шаблонов, где Б не стоят подряд, а А – стоят.
Как я понял, вы написали про все шаблоны, которые есть. Если вы хотели написать про шаблоны, где ни А, ни Б не стоят подряд, то вместо числа 12 правильно было бы написать 5, и получается, что количество хороших шаблонов нечётно, что сходится с моим решением.

👍
0
👎

Ответ на «Графы. Дискретная математика.»

Если 2 листа, то получается 6 всего. К тому же по количеству рёбер не сходится.
Сумма степеней должна быть в два раза больше количества рёбер. Составляем уравнение.
2 * (n — 1) = 4 * 2 + 3 + 2 + (n — 4)
2 * n — 2 = 9 + n
n = 11
Ответ: 11 вершин, из них 7 листьев.

👍
+1
👎
👍
+1
👎

Ответ на «Комбинаторика: заполнение таблицы»

Насколько я понял, имеется в виду набор {2, 3, 4, 5, 6, 7, 8}.
Белые и серые клетки можно расставлять независимо.
Количество способов расставить белые клетки равно A_7_6 = 5040.
Чтобы расставить серые клетки, давайте мысленно вычтем из каждого числа 1, тогда мы имеем дело с набором {1, ..., 7}, и сумма чисел в серых клетках должна быть равна 13 (минус один за каждую клетку, число которых – 10).
Задача разбить 13 на 10 положительных целых слагаемых эквивалентна задаче разбить 13 объектов на 10 непутсых групп. Эта задача известная, ответ на неё – C_n-1_k-1 = C_12_9 = 220.
Получается, ответ равен 5040 * 220 = 1108800.

👍
+1
👎

Ответ на «Комбинаторика: способ рассадки людей на плацу»

Я так понял, что расставить их надо в ряд (а не по кругу).
Давайте австрийцев обозначим за А, болгар – за Б, неизвестных – за Н.
Найдём количество «шаблонов» из 9 символов А, Б, Н, где каждого символа нужное количество и ни один символ не стоит два раза подряд. Тогда итоговый ответ будет равен количеству таких шаблонов, умноженному на 2!, на 3! и на 4!, потому что чтобы получить ответ нужно выбрать шаблон, потом расставить неизвестных 2! способами, расставить австрийцев 3! способами и расставить болгар 4! способами.
Давайте будем считать различные шаблоны, где не стоят подряд два Б, но стоят подряд два А.
Обозначим за x количество таких шаблонов, где при этом первый и второй А стоят рядом, за y – где второй и третий А стоят рядом, за z – где все три А стоят рядом. Причём каждый интересующий нас шаблон входит либо только в первую из этих групп (шаблоны вида АА А), либо только во вторую (шаблоны вида А АА), либо во все три (шаблоны вида ААА).
Давайте обозначим за группу 0 символы до первого Б, за группу 1 – символы между первым и вторым Б, за группу 2 – между вторым и третьим Б, за группу 3 – между третьим и четвёртым Б, за группу 4 – после четвёртого Б. Заметим, что в рассматриваемых нами шаблонах группы 1, 2 и 3 должны быть не пустые.
Чтобы вычислить x, давайте мысленно склеим два первых А в шаблоне – в один (так как в этих шаблонах первые два А стоят подряд). Тогда x – это просто количество способов расставить два А и два Н по пяти группам так, что в группы 1, 2 и 3 попадёт хотя бы один символ. Для построения такого шаблона давайте сначала решим, сколько символов окажется в каждой группе, а потом назначим какой из этих символов является Н, а какой – А. Так как количество способов сделать второй шаг не зависит от выбора первого шага, то x будет равен произведению количества способов сделать первый шаг и количества способов сделать второй шаг. Количество способов сделать первый шаг – это количество способов распределить четыре символа по пяти группам так, что конкретные три группы должны оказаться непустыми. Давайте сразу положим по символу в те группы, которые должны оказаться непустыми, так как это всё равно придётся сделать. Значит количество способов сделать первый шаг равно количеству способов распределить оставшийся один символ в одну из пяти групп, это равно 5. Чтобы сделать второй шаг, нужно просто выбрать какие два из четырёх символов являются А, значит количество способов сделать второй шаг – это просто C_4_2 = 6. Таким образом x = 5 * 6 = 30.
Чтобы посчитать y, надо сделать всё то же самое, только склеивая мысленно второй и третий А, а не первый и второй. Получим, что y = x = 30.
Чтобы посчитать z, надо склеить все три А в один символ. Тогда z равно количеству способов расставить три символа по пяти группам, так чтобы три конкретные группы были непустыми (что конечно равно 1), умноженному на количество способов выбрать, какой из трёх символов является А (что конечно равно 3). Таким образом, z = 1 * 3 = 3.
Количество шаблонов, где Б не стоят подряд, а А – стоят, первого вида (АА А) равно x — z (те, что входят в x, но не входят в z). Аналогично, количество таких шаблонов второго вида (А АА) равно y — z. И количество таких шаблонов третьего вида (ААА) равно z. Значит количество шаблонов, где Б не стоят подряд, а А – стоят, равно x — z + y — z + z = x + y — z = 30 + 30 — 3 = 57.
Чтобы найти количество хороших шаблонов нужно вычесть полученное нами количество из общего количества шаблонов, где никакие Б не стоят подряд. Давайте обозначим последнее за t.
Найдём t с помощью тех же двух шагов: оно равно количеству способов расставить пять символов по пяти группам так, чтобы конкретные три группы были непустыми, умножить на количество способов выбрать из этих пяти символов три, которые будут являться А. Давайте опять же распределим три из пяти символов по одному в каждую непустую группу. Тогда количество способов сделать первый шаг равно количеству способов распределить оставшиеся два символа по пяти группам, при этом каждая группа может остаться пустой. Распределить n объектов по k возможно пустым группам – это известная задача, ответ на неё – C_n+k-1_n. В нашем случае это C_6_2 = 15. Количество способов сделать второй шаг – C_5_2 = 10. Итак, всего шаблонов, где два Б не стоят подряд – 15 * 10 = 150. Из них плохих – 57, значит хороших – 150 — 57 = 93.
Значит, ответ равен 93 * 2! * 3! * 4! = 26784.

👍
+2
👎

Ответ на «Комбинаторика: способ рассадки людей на плацу»

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

👍
+1
👎

Ответ на «Можно ли число 1999 представить в виде суммы»

1. Квадрат нечётного числа по модулю 8 всегда даёт остаток 1. Значит сумма трёх квадратов должна давать по модулю 8 остаток 3, а 1999 даёт 7. Значит нельзя.

👍
+1
👎

Ответ на «Закон сохранения импульса»

Вы в геоцентрической системе мира рассуждаете, или у вас в неинерциальной системе отсчёта закон сохранения импульса выполняется? Определитесь.

👍
+1
👎

Ответ на «Закон сохранения импульса»

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

ASK.PROFI.RU © 2020-2023