Преглед за печат
Задача:
На рафта стоят 15 тома от събраните ми съчинения, подредени от 15 до 1.
С едно действие мога да хвана няколко тома, и да ги сложа на което и да е
друго място в редичката. С колко действия мога да подредя томовете
от 1 до 15?
(Нямам право да правя никакво въртене или разместване при действието,
слагам групата заедно точно така подредени и ориентирани както са били.)
С 14 действия.
(в задачата се пита "с колко", а не "с колко най-малко" (?))
1-во действие - взимам 14-ти том и го слагам най-отляво
2-ро - 13-ти тома най-отляво
и т.н
14-то -1-ви том най-отляво
ПП.
Май лесно може да се докаже по индукция, че при N на брой тома, минималния брой размествания е N-1
ПП2.
Това за индукцията съм го объркал. Може и да може, но не е лесно. А може и въобще да не е вярно
За 5 става лесно с 3 "действия":
5 4 3 2 1 -> 3 2 5 4 1
3 2 5 4 1 -> 3 4 1 2 5
3 4 1 2 5 -> 1 2 3 4 5
Поотделно нареждаш трите петорки и още 2 хода за групите и готово.
11 хода.
да, 11 е по-добре, ама като гледам как 7 може с 4 хода:
7 6 5 4 3 2 1 -> 4 3 2 7 6 5 1
4 3 2 7 6 5 1 -> 4 3 6 5 1 2 7
4 3 6 5 1 2 7 -> 4 5 1 2 3 6 7
4 5 1 2 3 6 7 -> 1 2 3 4 5 6 7
а 9 - с 5 хода:
9 8 7 6 5 4 3 2 1 -> 5 4 3 2 9 8 7 6 1
5 4 3 2 9 8 7 6 1 -> 5 4 3 8 7 6 1 2 9
5 4 3 8 7 6 1 2 9 -> 5 4 7 6 1 2 3 8 9
5 4 7 6 1 2 3 8 9 -> 5 6 1 2 3 4 7 8 9
5 6 1 2 3 4 7 8 9 -> 1 2 3 4 5 6 7 8 9
подозирам, че за 15 отговорът ще е около 8.
ПП:
М-да... с 8 изглежда добре:
15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 -> 08 07 06 05 04 03 02 15 14 13 12 11 10 09 01
08 07 06 05 04 03 02 15 14 13 12 11 10 09 01 -> 08 07 06 05 04 03 14 13 12 11 10 09 01 02 15
08 07 06 05 04 03 14 13 12 11 10 09 01 02 15 -> 08 07 06 05 04 13 12 11 10 09 01 02 03 14 15
08 07 06 05 04 13 12 11 10 09 01 02 03 14 15 -> 08 07 06 05 12 11 10 09 01 02 03 04 13 14 15
08 07 06 05 12 11 10 09 01 02 03 04 13 14 15 -> 08 07 06 11 10 09 01 02 03 04 05 12 13 14 15
08 07 06 11 10 09 01 02 03 04 05 12 13 14 15 -> 08 07 10 09 01 02 03 04 05 06 11 12 13 14 15
08 07 10 09 01 02 03 04 05 06 11 12 13 14 15 -> 08 09 01 02 03 04 05 06 07 10 11 12 13 14 15
08 09 01 02 03 04 05 06 07 10 11 12 13 14 15 -> 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
или така, че е по-лекинко и ясно:
15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 -> 08 07 06 05 04 03 02 15 14 13 12 11 10 09 01
08 07 06 05 04 03 02 15 14 13 12 11 10 09 01 -> 08 07 06 05 04 03 14 13 12 11 10 09 01 02 15
08 07 06 05 04 03 14 13 12 11 10 09 01 02 15 -> 08 07 06 05 04 13 12 11 10 09 01 02 03 14 15
08 07 06 05 04 13 12 11 10 09 01 02 03 14 15 -> 08 07 06 05 12 11 10 09 01 02 03 04 13 14 15
08 07 06 05 12 11 10 09 01 02 03 04 13 14 15 -> 08 07 06 11 10 09 01 02 03 04 05 12 13 14 15
08 07 06 11 10 09 01 02 03 04 05 12 13 14 15 -> 08 07 10 09 01 02 03 04 05 06 11 12 13 14 15
08 07 10 09 01 02 03 04 05 06 11 12 13 14 15 -> 08 09 01 02 03 04 05 06 07 10 11 12 13 14 15
08 09 01 02 03 04 05 06 07 10 11 12 13 14 15 -> 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
Браво на kamenf :thumbsup:!
Красиво представено решение, и вярно!
Разбира се, другите решения също се приемат...