Решение?

[Гост]

В едно състезание участвали Ангел, Борис, Васил, Георги и Димитър. В регламента на състезанието е казано, че при класирането не може двама състезатели да заемат едно и също място и не може един състезател да заема повече от едно място. На въпроса “Кой кое място е заел?” били дадени следните отговори:
1) Ангел е втори, Борис е трети;
2) Васил е трети, Георги е пети;
3) Георги е първи, Васил е втори;
4) Ангел е втори, Димитър е четвърти;
5) Борис е първи, Димитър е четвърти.
Известно е, че във всеки отговор едната част е вярна, а другата не е вярна.
Какво е било класирането на състезателите?

[Гост]

В едно състезание участвали Ангел, Борис, Васил, Георги и Димитър. В регламента на състезанието е казано, че при класирането не може двама състезатели да заемат едно и също място и не може един състезател да заема повече от едно място. На въпроса “Кой кое място е заел?” били дадени следните отговори:
1) Ангел е втори, Борис е трети;
2) Васил е трети, Георги е пети;
3) Георги е първи, Васил е втори;
4) Ангел е втори, Димитър е четвърти;
5) Борис е първи, Димитър е четвърти.
Известно е, че във всеки отговор едната част е вярна, а другата не е вярна.
Какво е било класирането на състезателите?

Много интересна задача! Ще разгледаме няколко решения.

5 участници могат да се класират по 5! начина, което е 120. Тогава решението е да проверим всяка от тези 120 пермутации и да върнем случаите които изпълняват условието. Това решение има сложност O(N!)

Имаме 5 твърдения всяко от които може да бъде лъжа-истина или истина-лъжа. Значи всяко може да има 2 състояния. Тогава имаме $2^5 = 32$ възможни случаи да проверим за това дали ще дадат решения които не си противоричат. Това решение има сложност O($2^N$)

Второто решение с O($2^N$) < O(N!) е по-добро от първото, но не кой знае колко много защото и двете са експоненциални. Първото решение изглежда по-лесно да накараме компютъра да го реши:

Код: Избери целия код

from itertools import permutations

names = "Ангел,Борис,Васил,Георги,Димитър".split(",")

A=[ [["Ангел", 2], ["Борис", 3]],
   [["Васил", 3], ["Георги", 5]],
   [["Георги", 1], ["Васил", 2]],
   [["Ангел", 2], ["Димитър", 4]],
   [["Борис", 1], ["Димитър", 4]]]

for per in permutations(names):
   for [name1, pos1], [name2,pos2] in A:
      част1 = per[pos1-1] == name1
      част2 = per[pos2-1] == name2
      if not( част1 and not част2 or \
            not част1 and част2 ):
         break
   else:
      print (per)

('Ангел', 'Васил', 'Борис', 'Димитър', 'Георги')

Върна само един отговор, значи това е единственото възможно класиране.

Трети начин е а се опитаме да разсъждаваме с цел да ограничим възможните варианти. Например от

2) Васил е трети, Георги е пети;
3) Георги е първи, Васил е втори;

Можем да направим заключението, че (Васил е трети, Георги е първи) или (Васил е втори, Георги е пети) и няма други възможности. Тогава тръгвайки от Васил е трети, скоро стигаме до противоречие, оставва да проверим Васил е втори, че не стигаме до противоречие и така решаваме задачата правейки 2*4 допълнителни проверки, което (ако не греша) е със сложност О(N) и е най-бързо.

[ptj]

За по-бърз запис ще използвам само първата буква от името + мястото.
От 2.) и 3.) следват само две възможности:
Вярно е или (В2,Г5) или (В3,Г1).

Да разгледаме първата (В2,Г5):
От 4.) [tex]\Rightarrow[/tex]вярно е Д4, т.е. (В2,Г5,Д4).
От 1.) [tex]\Rightarrow[/tex]вярно е Б3, т.е. (Б3,В2,Г5,Д4)
Тогава за А остава вярна само възможността А1, т.е. (А1,Б3,В2,Г5,Д4).
Последното не противоречи на 5.) сл. имаме възможно решение.

Да разгледаме втората (В3,Г1):
От 1.)[tex]\Rightarrow[/tex] вярно е А2, т.е. (А2,В3,Г1)
От 4.)[tex]\Rightarrow[/tex] Д4 е невярно [tex]\Rightarrow[/tex] вярно е Д5 , т.е. единствена възможност е (А2,Б4,В3,Г1,Д5)
Полученото противоречи на 5.) сл. не е решение.

Окончателно класирането е следното:
1.)Ангел
2.)Васил
3.)Борис
4.)Димитър
5.)Георги