21.05.2025 19:43
aabzel 38 3100 Источник

Пролог

Существует классическая задача:

Каждый гость на встрече обменивается рукопожатием с другим. Всего было 78 рукопожатий. Сколько гостей пришло на встречу?

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

Определения

Для начала микро ликбез.

Граф - множество вершин и рёбер (палочки и кружочки).

Неориентированный граф — это граф, рёбра которого не имеют направления. Это значит, что соединение между двумя вершинами можно пройти в обе стороны. Проще говоря палочки без стрелок.

Две вершины неориентированного графа смежны, если они являются разными концами одного ребра

полный граф - простой неориентированный граф, в котором каждая пара различных вершин смежна.

это 4 примера полных графов
это 4 примера полных графов

Сочетание - неупорядоченная выборка из n элементов по k без повторений. Вычисляется по кнопке калькулятора nCr.

Это всё, что надо для решения этой задачи.

Решение

Это задача из раздела дискретной математики, комбинаторики и алгебры.

Если людей принять за вершины графа, а рукопожатия за ребра графа, то сформируется так называемый полный граф. Как математически связаны количество ребер и количеcтво вершин?

Занумеруем всех гостей натуральными числами (1; 2; 3; 4; 5 и т д). Для одного рукопожатия надо выбрать два гостя. Рукопожатие это неупорядоченная (если Уолли жмет руку Ашоку, то и Ашок жмет руку Уолли) выборка без повторений (Тэд же не может пожать руку сам себе).

Согласно формуле nСm надо посчитать

\mathrm{C}_{n}^{2}= \frac{n!}{2!(n-2)!} = \frac{n(n-1)(n-2)!}{2!(n-2)!} = \frac{n(n-1)}{2} \qquad (2)

Вот и получается, что у полного графа есть свойство. Если n- это количество вершин, то

(3) это количество рёбер. Задача сводится к тому, что надо решить уравнение (4)

78=\frac{n(n-1)}{2} \qquad (4)

Это уравнение вырождается в квадратное уравнение

n^{2}-n-156= 0 \qquad (5) \\ x_1 = 13 ; \qquad x_2 = -12 \qquad (6)

Так как ответ мы ищем в множестве натуральных чисел, то выбираем решение 13. Ответ: на встрече пришло 13 человек.




Итог

Вот теперь и Вы умеете решать задачу про рукопожатия и можете объяснить другим.

Ссылки

#

Название

URL

1

Полный Граф

https://en.wikipedia.org/wiki/Complete_graph

3

Рукопожатия

https://tproger.ru/articles/7-zakovyristyh-logiko-matematicheskih-zadach

2

LaTex Editor

https://latexeditor.lagrida.com/

4

Калькулятор квадратных уравнений

https://calc.by/math-calculators/quadratic-equations.html

5

Задача про мышей и отраву (спрашивали на собеседовании)

https://habr.com/ru/users/aabzel/articles/

6

Задача про игральные кубики и треугольники (спрашивали на собеседовании)

https://habr.com/ru/articles/763372/

7

Задача про две ёмкости для жидкости (спрашивали на собеседовании)

https://habr.com/ru/articles/662561/

Комментарии (38)


  1. SystemSoft
    21.05.2025 19:47
    #28335344

    может 78 + 78 = 156? просто так намного проще. правда, если там может быть что два гостя одному жали руку... то... не знаю


  1. Racheengel
    21.05.2025 19:47
    #28335358

    Классика же, корень из 78×2... и без графов имеем 13...


    1. omaxx
      21.05.2025 19:47
      #28335470

      Вообще-то корень из 156 не равняется 13...


      1. Wesha
        21.05.2025 19:47
        #28335780

        Тсссс, не пугайте миллениалов!


    1. Leather_bag
      21.05.2025 19:47
      #28335556

      Классика не пляшет как-то. Если одно рукопожатие, то челов выходит корень(2).


    1. mlnw
      21.05.2025 19:47
      #28336408

      Не совсем. Берем формулу арифметической прогрессии (или выводим её в две строчки, если забыли):

      (x-1)*x/2 = 78 => (x-1)*x = 156

      И тут уже можно не решать квадратное уравнение, просто берем ближайший больший квадрат целого числа (169). Автор же какойто хрени наворотил.


      1. randomsimplenumber
        21.05.2025 19:47
        #28336490

        И тут уже можно не решать квадратное уравнение, просто берем ближайший больший квадрат целого числа

        А зачем вам квадрат целого числа, если задача свелась таки к уравнению?


        1. mlnw
          21.05.2025 19:47
          #28337038

          А зачем вам квадрат целого числа, если задача свелась таки к уравнению?

          Чтобы не сводить задачу к решению этого уравнения. Вместо задачки для 7го класса, получаем решение для 5го.


          1. randomsimplenumber
            21.05.2025 19:47
            #28337146

            Но мы же взрослые, что было в 5 классе - забыли на 2 года раньше чем то что было в 7 ;)


  1. Politura
    21.05.2025 19:47
    #28335388

    Что-то из вашего объяснения нифига не понятно как вы пришли к своим формулам. Можно же проще. Так и алгоритм подобрать проще:

    1. Сначала пришел один человек, руку жать не кому, значит итого после его прихода общее количество рукопожатий = 0.

    2. Пришел второй, до него был один человек, он жмет ему руку, общее количество рукопожатий = 0 + 1 = 1

    3. Пришел третий, в группе два человека, которые уже пожали друг другу руки. Он жмет им, итого, общее количество рукопожатий стало: 1 + 2 = 3

    4. Пришел четвертый, в группе 3 человека, которые пожали руки друг другу, опять надо всего-лишь добавить к общему количеству столько, сколько этот новый человек пожмет руки. или 3 + 3 = 6.

    5. 6 + 4 = 10

    6. 10 + 5 = 15

    7. и тд

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


    1. omaxx
      21.05.2025 19:47
      #28335460

      Т.е. если вас на собеседовании спросят, допустим, сколько нужно линков чтобы соединить 100 компьютеров друг с другом, вместо того, чтобы просто умножить 50 на 99, вы будете суммировать в столбик? Или вам понадобится 10 минут, чтобы "накодить" и компьютер, чтобы посчитать?


      1. tarandro
        21.05.2025 19:47
        #28335512

        0+1+2+…
        Сумма n элементов арифметической прогрессии — (a1+an)*d/2 = (0+99)*100/2
        Кажется, это сильно проще в вычислении, чем графы и прочее


        1. omaxx
          21.05.2025 19:47
          #28335694

          Каждый из n соединен с n-1. Перемножаем и делим пополам. Куда же уж может быть проще?


      1. Politura
        21.05.2025 19:47
        #28335576

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

        Ну а на вопрос на счет линков я предложу использовать свитчи с 24 портами (не знаю, больше бывают, или нет) Ну и соответственно, 100 линков до первых 6-и свитчей и еще 5 свитчей воткнуть в 6-й свитч. Итого 105 линков, а никак не 50 умножить на 99.


        1. omaxx
          21.05.2025 19:47
          #28335680

          А кто вам сказал, что с вопросе речь идет про коммутируемый ethernet? Там сказано "соединить друг с другом"...


        1. Wesha
          21.05.2025 19:47
          #28335794

          я никакие формулы не могу вспомнить.

          Как нас учили в универе, «не можешь вспомнить — выведи!»


    1. Wesha
      21.05.2025 19:47
      #28335476

      И всё это называется страшным словом ИНДУКЦИЯ!


      1. dzhiharev
        21.05.2025 19:47
        #28335514

        Все это называется "арифметическая прогрессия", а формулу суммы первых N ее членов проходят где-то в 9 классе.


        1. Wesha
          21.05.2025 19:47
          #28335796

          Нет, я про метод, говоря простым языком, «начнём с одного, потом добавим ещё одного, потом ещё одного... повторять до опупения».


          1. dzhiharev
            21.05.2025 19:47
            #28335834

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


  1. VitaminND
    21.05.2025 19:47
    #28335474

    Сколько нынче Бизнес платит за решение подобных задач в процессе трудовой деятельности?

    Или Бизнес все-таки платит не за такие задачи?


    1. aabzel Автор
      21.05.2025 19:47
      #28335546

      "Сколько нынче Бизнес платит за решение подобных задач в процессе трудовой деятельности?"

      На роли программиста микроконтроллеров у меня за 12 лет не возникало таких вот задач.
      Сам не понимаю зачем спрашивать такое на собеседовании.

      Речь шла о ЗП 160к RUR /мес gross.


    1. pnmv
      21.05.2025 19:47
      #28336022

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


  1. pnmv
    21.05.2025 19:47
    #28335528

    (специально, не пошел читать комментарии)

    Каждый гость на встрече обменивается рукопожатием с другим. Всего было 78 рукопожатий. Сколько гостей пришло на встречу?

    что означает "с другим"?

    с одним из соседей?

    только с одним? (тогда, по кругу, и будет 78)

    а на картинках графы, как будто каждый с каждым. зачем?

    если каждый гость обменивается рукопожатиями со всеми остальными, что соответствует графам с картинок, то, если у нас n гостей, то каждый совершает n-1 рукопожатий (неуместно жать руку самому себе), а все вместе n*n-n, тогда получаем уравнение n^2-n-78=0. получается, слегка дробное число гостей.

    вот, если бы их было 72...


    1. tarandro
      21.05.2025 19:47
      #28335544

      n*(n-1) будет, если человек 1 пожал руку человеку 2 (+1) и человек 2 пожал руку человеку 1 (+1)
      Если каждый с каждым здоровался только раз, будет n*(n-1)/2


      1. pnmv
        21.05.2025 19:47
        #28336020

        а выше умножать предлагали.


  1. AuToMaton
    21.05.2025 19:47
    #28336158

    Мне кажется, собеседование о другом, никого не интересует, точнее - не должно интересовать, умеет ли кандидат считать. Такую ерунду как

    Каждый гость на встрече обменивается рукопожатием с другим. Всего было 78 рукопожатий. Сколько гостей пришло на встречу?

    спрашивают чтобы получить откровенный ответ. Типа

    • Пришло 79 гостей если Другой тоже гость, и 78 если Другой - хозяин.

    • Поскольку при обмене сущности не уничтожаются и не появляются, то 78 или 39 или 26 или 13 или 6 или 2 или 3 в зависимости от того, по сколько рукопожатий было у каждого гостя.

    • … (молчит и считает) … (сморкается, вытирает слёзы) … да, он трижды, трижды …

    • О, 78 - это же минимальное число рёбер многогранника в 12-мерном пространстве, значит гостей было 13.

    • Неизвестно - пока одни гости приходили, другие могли не только уходить, но и возвращаться.

    А если человек не даёт откровенного ответа… то он скрытен, подозрителен, коварен и хитёр - такой и нужен нам в команду.


  1. CitizenOfDreams
    21.05.2025 19:47
    #28336208

    Я впервые в жизни встретил эту задачу, и секунды за две увидел последовательность 1+2+3+4+...=78. Какие, на фиг, "смежные вершины неориентированных графов"?


  1. randomsimplenumber
    21.05.2025 19:47
    #28336266

    Надо же чего-то спросить на собеседовании. Как насчёт олимпиадной задачи за 6 класс?

    Недоумевающие смайлик.тхт


    1. omaxx
      21.05.2025 19:47
      #28336462

      Ну, судя по комментариям, их задают не просто так


      1. randomsimplenumber
        21.05.2025 19:47
        #28336568

        Если это собеседование о приеме на работу, то, наверное, от кандидата ожидается максимально простое решение. Если он притащит додекаэдр в 13-мерном пространстве, он конечно же умный. Но если он код будет писать в таком же стиле - нафиг :)


  1. mlnw
    21.05.2025 19:47
    #28336398

    За такое решение при наличии решения в две строчки на уровне 5 класса школы, гнать в шею надо таких кандидатов. Потом и проекты у таких соответствующие: надо написать простейшую функцию, они вместо трёх строчек кода для этого десяток сторонних либ подключат.


    1. aabzel Автор
      21.05.2025 19:47
      #28336492

      Задачу надо было решить не кодом , а карандашом на листке. Чисто аналитическим образом.


      1. mlnw
        21.05.2025 19:47
        #28337070

        Так она и решается при желании даже не карандашом на листке, а в уме. См. коммент выше.


  1. nerudo
    21.05.2025 19:47
    #28336504

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


    1. aabzel Автор
      21.05.2025 19:47
      #28336516

      Можно решить квадратное уравнение численным методом.


  1. ganqqwerty
    21.05.2025 19:47
    #28337360

    А если я дал ответ "каждый гость - вершина графа, каждое рукопожатие - ребро графа, ненаправленное, циклов нет. Количество ребер известно, открывайте справочник, там была формула для количества вершин" - норм?


  1. RavenStark
    21.05.2025 19:47
    #28337478

    Ок... Каждый из гостей (всех гостей) пожал руку другому. То есть, у нас есть неизвестное полное количество, разбитое на неповторяющиеся пары. Таким образом, кмк, задача сводится к вопросу "из какого общего количества элементов можно составить 78 уникальных пар", так?