комбинаторика

[Fylhtq1997]

Ночью перерыл интернет и нашел ркшение выше упомянутой задачи, следующее:
В матчах между собой три последних участника набрали 3 очка. Поэтому в матчах с остальными участниками они набрали также 3 очка. Пусть в турнире участвовало Р шахматистов, тогда в матчах с последними тремя остальные шахматисты набрали 3(Р – 3) - 3 очка. Тогда все шахматисты набрали в матчах с последними тремя 3(Р – 3) очков. Общее количество очков, набранных за турнир – Р(Р - 1)/2. Тогда Р(Р+1)/4 = 3(Р – 3). Отсюда Р = 9 или Р = 4. Случай Р=4 не подходит, т.к первый участник в матчах с последними 3, набрал 3(4 – 3) – 3 =0 очков и не мог занять первое место.
Ответ: Р=9.
Попробовал разобраться, так и не смог. Разьъясните пожалуста.
Спасибо.

[devnull]

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

Если есть n игроков, то число матчей между ними будет равно числу сочетаний из n по 2, т.е. n*(n-1)/2 . Например, последние три игрока сыграли между собой 3*2/2 = 3 матча. При каждом матче их суммарный счет повышался на единицу, поэтому за счет игр между собой три последних игрока получили 3 очка. Каждый участник турнира, включая и саму последнюю троицу, получает половину своих очков от игры с последними тремя участниками. Значит, раз последние трое набрали в сумме 3 очка играя между собой, они набрали еще 3 очка играя с остальными участниками. Посмотрим теперь, сколько очков набрали остальные игроки, игравшие с последней троицей. Пусть полное число участников P. У нас есть две группы - последняя троица и P-3 остальных. Между этими группами было сыграно 3*(P-3) матчей. Действительно, для каждого такого матча мы сначала выбираем одного из трех последних игроков, а потом (P-3) способами выбираем второго игрока. Раз было сыграно 3(P-3) матчей между этими группами, то их суммарный счет увеличился на 3(P-3). Однако мы уже выяснили, что из этого полного числа очков три очка "взяли" три последних участника (см. жирный текст выше). Значит, все остальные участники, играя с последними тремя, получили в сумме 3(P-3)-3 очка. Сама же последняя троица играя между собой получила еще 3 очка (с этого мы начинали решение). Итак, все P игроков, играя с последней троицей, получили 3(P-3)-3+3 = 3(P-3) очка.

Полное число матчей (а значит и полное число очков), сыгранных на турнире с P участниками, составило P(P-1)/2. Но в точности половина этого числа, P(P-1)/4, получена в игре с последними тремя. Как мы видели, это число равно также 3(P-3). Отсюда уравнение P(P-1)/4 = 3(P-3) (в приведенном решении опечатка - там стоит плюс вместо минуса). Думаю, что дальше уже все понятно.

[Fylhtq1997]

Между этими группами было сыграно 3*(P-3) матчей?.

Огромное спасибо за подробное разъяснение. Но вопросы у меня остались.
До этого рассуждения  «Между этими группами было сыграно 3*(P-3) матчей?»   всё стало на свои места в моей голове. Дальше если пойму почему « сыграно 3*(P-3) матчей», тоже понимаю.

[devnull]

Есть две группы, в одной n человек, в другой - m. Сколько попарных матчей можно сыграть между этими двумя группами? Для каждого такого матча выбираем первого соперника из n возможных кандидатов, а второго - из m возможных. Результат - n*m возможных матчей. В нашем случае это n = 3 а m = P - 3. Ну или представь себе две параллельные прямые, на одной отмечено n точек, а на другой - m. Сколько отрезков можно провести между первым и вторым множеством точек? Соединяем первую точку на первой прямой со всеми m точками на второй. Потом соединяем вторую точку на первой прямой со всем точками на второй опять же m способами. Затем третью, четвертую, ..., n-ую. Получаем n*m отрезков.

Кстати, можно еще и такое уравнение записать:
полное число матчей в группе из P человек =
    число матчей только между последними тремя +
    число матчей только между P-3 остальными +
    число матчей между последними тремя и P-3 остальными

Число матчей в группе из n человек - это число сочетаний из n по 2 = n*(n-1)/2, поэтому
P*(P-1)/2 =
    3*2/2 +
    (P-3)*(P-4)/2 + 
    число матчей между последними тремя и P-3 остальными
Из этого уравнения следует, что последнее слагаемое равно 3P-9 = 3(P-3).

[Fylhtq1997]

Спасибо, спасибо, спасибо!!!

[Fylhtq1997]

Доброе утро.
Задача:На сколько частей делят плоскость n прямых, никакие три из которых не пересекаются в одной плоскости
Ответ: 1+n*(n+1)/2
Как прийти к этому ответу?
Спасибо!

[devnull]

Замечание по формулировке:

На сколько частей делят плоскость n прямых, никакие три из которых не пересекаются в одной плоскости.

Выделенное слово должно быть "точке" Кроме того, надо уточнить, что речь идет о максимальном числе частей.

Пусть (n - 1) прямых разбивают плоскость на P(n-1) частей. Проведем n-ую прямую. Чтобы разбить плоскость на максимальное число частей, надо, чтобы эта новая прямая пересеклась со всеми предыдущими (n - 1) прямыми.
Ниже приводится схемка такого пересечения.

прямая номер  1     2    ...   n-1

части         |     |     |     |
которые       |     |     |     |
были          |     |     |     |
          -------------------------- прямая номер n
              |     |     |     |
новая часть   |     |     |     |
  номер 1     |  2  | ... | n-1 |  n

Видно, что при добавлении n-ой прямой мы добавили n новых частей, т.е.
P(n) = P(n-1) + n.
Единственная прямая разбивает плоскость на две части, поэтому P(1) = 2.
Таким образом,
P(n) = 2 + 2 + 3 + 4 + 5 + ... + n = 1 + (1 + 2 + ... + n) = 1 + n*(n+1)/2.

[zhekas]

Доброе утро.
Задача:На сколько частей делят плоскость n прямых, никакие три из которых не пересекаются в одной плоскости
Ответ: 1+n*(n+1)/2
Как прийти к этому ответу?
Спасибо!

скорее не пересекаются в одной точке

0 прмых - одна часть
1 прямая - две части
2 прямых - 4 части

Пусть у нас есть уже k - прямых.
Зададимся вопросом. Сколько  частей добавит k+1-ая прямая

k+1-ая прямая пересекает каждую из k прямых в разных точках.

Пронумеруем эти точки в порядке прохожднеия k+1-ой прямой



-------|------------|-----------|---------------------------|----------------|---------------------
       1           2           3 ............            k-1             k

Эти точки делят нашу прямую на k+1 часть

соответственно каждая такая часть прямой делит соответствующий участок плоскости на 2. Тем самым добавляя один участок плоскости.

Тоесть k+1-ая прямая добавляет ещё k+1 участок плоскости


Теперь чтобы узнать сколько частей будет надо просуммировать по каждой прямой


1                             +       ( 1                                           +              2                                    + .............+  n)
был изначально                добавляет первая прямая                    добавляет вторая прямая                      добавляет n-ая прямая

в скобках у нас геометричекая прогрессия






= 1 +  (1+n)*n/2

[Fylhtq1997]

Огромное всем СПАСИБО!

[AnnaCherry]

Помогите решить вот эти задачки)
1. Сколько диагоналей можно провести в опуклосу 15-угольнике? n-угольнике?

2. Сколькими способами можно колоду из 52 карт разделить на 2 равные части так, чтобы в каждой было поровну красных и черных карт?

Заранее спасибо)

[Fylhtq1997]

1. 15*(15-3)=180
    n*(n-3)-формула

[Fylhtq1997]

2. 26!
   Разьяснение:
   У нас имеется в колоде 4 масти и 2 цвета 26 черных и 26 белых.
   В данной задаче не интеисует какая честь первая а какая вторая.
   Поэтому можно выкинуть красные и узнать сколькими спосабами можно помеять местами одни чёрные и разные карты.
   26?25?24?....?4?3?2?1=26!

[Леонид]

2. По-моему, так. Нужно сосчитать способы выбрать 13 из 26 красных, способы выбрать 13 из 26 чёрных, и потом перемножить одно и другое. Это сочетания. Получается 26!/(13!*13!) * 26!/(13!*13!).

[devnull]

По поводу первой задачи: следует учесть, что каждая диагональ соединяет две вершины, поэтому ответ надо не забыть поделить пополам. Ответ: n*(n-3)/2, для 15-угольника получим 90.
По поводу второй задачи: то же замечание, что и для первой   Нас не интересует, какая группа карт первая, а какая - вторая, поэтому надо поделить ответ пополам: (26!/(13!*13!))²/2

[AnnaCherry]

огромное всем спасибо)))