Question

При дворе короля Артура есть 17 рыцарей. Во время совещания они садятся за круглый стол так, чтобы никакие два рыцаря, сидевшие рядом на одном из предыдущих совещаний, не сидели рядом. Сам король во время совещаний за стол не садится (и место королю не отведено: за столом ровно 17 мест, их все занимают рыцари). Какое наибольшее количество совещаний сможет провести король?

Answer 1

Т.к. после каждого собрания количество возможных соседей для каждого рыцаря уменьшается на 2 (а изначально их 16), больше 8 совещаний провести не получится. 8 совещаний можно провести, если, например, использовать следующую схему (произвольно пронумеровав рыцарей от 1 до 17):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1
1 3 5 7 9 11 13 15 17 2 4 6 8 10 12 14 16 1
1 4 7 10 13 16 2 5 8 11 14 17 3 6 9 12 15 1
1 5 9 13 17 4 8 12 16 3 7 11 15 2 6 10 14 1
1 6 11 16 4 9 14 2 7 12 17 5 10 15 3 8 13 1
1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12 1
1 8 15 5 12 2 9 16 6 13 3 10 17 7 14 4 11 1
1 9 17 8 16 7 15 6 14 5 13 4 12 3 11 2 10 1

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