Задача о распеделении мест между участниками олимпиады

[Rumato]

Добрый день, подскажите, пожалуйста, как решить следующую задачу:

Ученики Андрей, Борис, Вадим, Глеб и Дмитрий приняли участие в олимпиаде по информатике. До начала олимпиады они высказали следующие предположения о распределении мест:
Андрей: Дмитрий займет 4-е место, Вадим займет 5-е место, Глеб займет 1-е место;
Борис: Андрей займет 2-е место, Глеб займет 5-е место, Дмитрий займет 1-е место;
Вадим: Глеб займет 3-е место, Андрей займет 5-е место, Борис займет 1-е место;
Глеб: Вадим займет 2-е место, Борис займет 1-е место, Дмитрий займет 4-е место;
Дмитрий: Борис займет 2-е место, Андрей займет 4-е место, Вадим займет 1-е место.
После подведения итогов выяснилось, что каждый участник сделал ровно одно верное предположение. Найдите все возможные распределения мест, если известно, что не было разделения мест между участниками.

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

Второй способ, это записать по $A_{n}^{k} = n!/(n-k)!$, тогда получить все возможные распределения 3-х элементов в 5-ти местах, но дальше мне не понятно, что делать.

Подскажите, пожалуйста, куда двигаться.

[Henrylee]

По-моему проще всего перебирать варианты и приходит к противоречиям. Или нет.
Например, начиная с предположения, что Андрей займет 1-е место, получаем противоречие. И т.д.

[Rumato]

Henrylee, не совсем понял вас, поясните как это в двух словах, перебераем, находим противоречие -- мне не понятно вот это.

[Cash]

Rumato в сообщении #891906 писал(а):

перебераем

Выписываем все возможные варианты и рассматриваем каждый.

Rumato в сообщении #891906 писал(а):

находим противоречие

Проверяем - соответствует ли вариант условию

-- Ср июл 30, 2014 20:41:37 --

На мой взгляд, самое простое - перебирать возможные верные высказывания

[Henrylee]

2Cash
Вообще-то я не предлагал проверять все 120 вариантов.

Rumato
Пример:
Предположим, Андрей занял 1-е место (это предположение я взял от балды, просто потому что у Вас Андрей первый в списке).
Тогда, у Бориса 1-e и 3-е утврждения ложные $\Rightarrow$ 2-е истинно
$\Rightarrow$ Глеб на 5-м месте.
Тогда Вадим наврал во всех трех утверждениях.
Вот и противоречие.

Далее, предположим, Андрей занял 2-е место..
и т.д.

[Rumato]

Henrylee, мы получается если берём Андрея, то утверждения его не расматриваем, сразу идём от прогноза Бориса, я правильно понял?

[Henrylee]

Rumato в сообщении #892661 писал(а):

Henrylee, мы получается если берём Андрея, то утверждения его не расматриваем, сразу идём от прогноза Бориса, я правильно понял?

Не в том дело. Мы просто обращаем внимание на те утверждения, из которых можно извлечь некоторый однозначный вывод. Исходя из предположения, что Андрей на 1-м месте, мы ничего не вынесем из его собственного утверждения, а вот из утверждения Бориса можно вынести то, что я говорил.

[ewert]

Ну вот тупой перебор. Тупой, но формализованный, поэтому хватает примерно девяти шагов.
Исходные данные (строки -- высказывающиеся, столбцы -- про кого):

     А     Б     В     Г     Д
А               5     1     4
Б   2                 5     1
В   5     1           3   
Г         1     2           4
Д   4     2     1         

Вариант + - - для строки А

Заполняем колонку В, ставим "-" для неправильных "5", дублируем "1-" в кол. Г и "4-" в кол. Д:

     А     Б     В     Г     Д
А               5 +   1 -   4 -
Б   2                 5 -   1
В   5 -   1           3   
Г         1     2 -         4 -
Д   4     2     1 -       

Закрываем строку Г, заполняем колонку Б, ставим "-" для неправильных "1":

     А     Б     В     Г     Д
А               5 +   1 -   4 -
Б   2                 5 -   1 -
В   5 -   1 +         3   
Г         1 +   2 -         4 -
Д   4     2 -   1 -       

Закрываем строки Б,В,Д:

     А     Б     В     Г     Д
А               5 +   1 -   4 -
Б   2 +               5 -   1 -
В   5 -   1 +         3 -
Г         1 +   2 -         4 -
Д   4 +   2 -   1 -       
    ???

Получили противоречие в колонке А.

Вариант - + - для строки А

Заполняем колонку Г, ставим "-" для неправильных "1", дублируем "5-" в кол. В и "4-" в кол. Д:

     А     Б     В     Г     Д
А               5 -   1 +   4 -
Б   2                 5 -   1 -
В   5     1 -         3 - 
Г         1 -   2           4 -
Д   4     2     1 -       

Закрываем строки Б,В,Г:

     А     Б     В     Г     Д
А               5 -   1 +   4 -
Б   2 +               5 -   1 -
В   5 +   1 -         3 - 
Г         1 -   2 +         4 -
Д   4     2     1 -       
    ???

Получили противоречие в колонке А.

Вариант - - + для строки А

Заполняем колонку Д, ставим "-" для неправильных "4", закрываем строку Г, дублируем "1-" в колонке Б:

     А     Б     В     Г     Д
А               5 -   1 -   4 +
Б   2                 5     1 -
В   5     1 -         3  
Г         1 -   2 -         4 +
Д   4 -   2     1        

Данных мало - перебираем варианты строки Б

Подвариант + - - для строки Б

Заполняем колонку А, ставим "-" для неправильных "2":

     А     Б     В     Г     Д
А               5 -   1 -   4 +
Б   2 +               5 -   1 -
В   5 -   1 -         3  
Г         1 -   2 -         4 +
Д   4 -   2 -   1        

Закрываем строки В,Д:

     А     Б     В     Г     Д
А               5 -   1 -   4 +
Б   2 +               5 -   1 -
В   5 -   1 -         3 +
Г         1 -   2 -         4 +
Д   4 -   2 -   1 +      

Нашли решение:
А Б В Г Д
2 5 1 3 4

Подвариант - + - для строки Б

Заполняем колонку Г, ставим "-" для неправильных "5":

     А     Б     В     Г     Д
А               5 -   1 -   4 +
Б   2 -               5 +   1 -
В   5 -   1 -         3 -         ???
Г         1 -   2 -         4 +
Д   4 -   2     1        

Получили противоречие в строке В

Итого -- единственное решение.

[garin99]

Это математическая логика.
Например:
$A_{k}$- Дмитрий занял k-ое место.
Составляется логическое выражение, раскрываются скобки и ответ готов.

[Rumato]

Спасибо, всем кто ответил, каждый ответ помог разобраться в том как решать задачу. Спасибо!