Вход через социальные сети

  • 2страниц:
  • 1
  • 2
  • 14.11.2017, 15:34
    0 up down
    Сообщение

    Это задача на принцип Дирихле. Подобные неоднократно предлагались на всяких международных олимпиадах. Решение несложно.

    Выберем из класса двух учеников A и B, которые между собой не дружат. 

    1. Если мы их найти не можем, значит все в классе дружат каждый с каждым. А, стало быть, у каждого из учеников есть 24 друга. Доказано.

    2. Пусь существуют эти самые A и B. Тогда каждый из остальных 23 человек дружит либо с A, либо с B. Это очевидно, так как если бы нашёлся ученик C, который не дружил бы ни с A, ни с B, то мы получили бы тройку A, B, C, среди которых нет друзей, что противоречит условию.

    3. Предположим, что и A, и B имеют каждый не более 11 друзей. Но тогда по принципу Дирихле получается, что в классе может быть не более 24 учеников (разумеется, включая A и B). Пришли к противоречию с условием. Доказано, что по крайней мере один ученик имеет не менее 12 друзей.

    Поэтому на вопрос ТС-а отвечаю: да, может оказаться, а именно ровно 12.

  • 15.11.2017, 08:40
    0 up down
    Сообщение

    Прошу прощения. Не совсем по теме, но, по ассоциации, близко к ней.

    Помнится, лет 10 назад подошел ко мне коллега по работе - вот, сыну-шестикласснику на школьной олимпиаде

    предложили среди прочих задач такую. Как её решить?

    В концертном зале находится 1000 зрителей. У каждого есть среди зрителей как знакомые,

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

    количество знакомых в зале.

    Своё решение пока не выкладываю, Интересно посмотреть на другие, если кто-то сочтет нужным выложить.smile
     

  • 15.11.2017, 09:15
    0 up down
    Сообщение

    Зрителей 1000, а возможное количество знакомых от 1 до 998. То есть, для 998 зрителей можно (может быть) подобрать разное количество знакомств. Для двоих оставшихся придется продублировать.   

    Сообщение было отредактировано Dredd в 15.11.2017, 09:15.


  • 15.11.2017, 10:15
    0 up down
    Сообщение

    Dredd в 15.11.2017, 09:15 написал(а): link
    возможное количество знакомых от 1 до 998

    Ну, вообще-то - от 0 до 999. Это как бы намек уже.

    Чтоб не предположительно:

    Dredd в 15.11.2017, 09:15 написал(а): link
    может быть

    а наверняка.smile

  • 15.11.2017, 10:32
    0 up down
    Сообщение

    grigoriy в 15.11.2017, 10:15 написал(а): link
    Ну, вообще-то - от 0 до 999. Это как бы намек уже.

    Я тоже так подумал, но... если у вас 999 знакомых, а вы - тысячный, то незнакомых у вас нет. А они должны быть. Поэтому 998 и минимум 2 пары или тройка.

    Сообщение было отредактировано Dredd в 15.11.2017, 10:32.


  • 15.11.2017, 10:33
    0 up down
    Сообщение

    grigoriy в 15.11.2017, 10:15 написал(а): link
    а наверняка.

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

  • 15.11.2017, 12:06
    0 up down
    Сообщение

    Ну, с моей точки зрения "наверняка" будет так. Методом "от противного".

    Предположим, что все зрители будут иметь разное количество знакомств.

    Расположим их в порядке увеличения количества знакомств и пронумеруем в том же порядке.

    № зрителя       кол-во знакомств

    1                       0

    2                       1

    3                       2

    .........

    1000                 999

    Зритель-1000 знаком со всеми, в том числе и со зрителем-1, который, в свою очередь, не знаком ни с кем.

    Противоречие.

  • 15.11.2017, 17:55
    0 up down
    Сообщение

    Здравия Вам желаю.

    grigoriy в 15.11.2017, 12:06 написал(а): link
    Противоречие.

    А если кто-то за кем-то следит? Одностороннее знакомство.

  • 15.11.2017, 18:13
    0 up down
    Сообщение

    balans в 15.11.2017, 17:55 написал(а): link
    А если кто-то за кем-то следит? Одностороннее знакомство.

    Забавно, конечно... У самого такая мысля крутилась в качестве юмора -

     - я знаю этого человека, а он меня не знает - это знакомство?

    Знакомство - вещь двусторонняя.  Из этого решение и строится.

    Хотите сформулировать задачу с односторонним? Флаг Вам в руки! И здравия! smile

  • 15.11.2017, 18:27
    0 up down
    Сообщение

    grigoriy в 15.11.2017, 18:13 написал(а): link
    Флаг Вам в руки! И здравия!

    Как интеллигентно Вы меня послали!!!

  • 2страниц:
  • 1
  • 2