задача на перестановку нулей и единиц

[arseniiv]

B@R5uk, Dmitriy40, спасибо за интересный вопрос: есть ли различные с точностью до «эквивалентности» правил 3 двойному 1 и 6 двойному 2 решения? Предсказываю отрицательный ответ.

-- Вс янв 14, 2018 22:29:34 --

(Это для оригинальной задачи с равным числом баранов разного знака и с одним пропуском. Про другие кассандрить не рискну.)

[B@R5uk]

Поэкспериментировал тут с двумя пропусками. Получилась такая табличка:
......1....2....3....4....5....6....7....8....9...10
.1....6....8...10...13...15...17...20...22...24...27
.2....8...11...15...18...21...25...28...31...35...38
.3...10...15...19...24...28...33...37...42...46...51
.4...13...18...24...29...35...40...46...51...57...62
.5...15...21...28...35...41...48...54...61...67...74
.6...17...25...33...40...48...55...63...70...78...85
.7...20...28...37...46...54...63...71...80...88...97
.8...22...31...42...51...61...70...80...89...99..108
.9...24...35...46...57...67...78...88...99..109..120
10...27...38...51...62...74...85...97..108..120..131
Тут уже красивая формула не проглядывается, но если из этой таблички вычесть число $(N+1)(M+1)+\left\lceil\frac{N+M}{2} \right\rceil$, то получится такая интересная табличка:
.....1...2...3...4...5...6...7...8...9..10
.1...1...0...0...0...0..-1...0..-1..-1..-1
.2...0...0...0...0..-1...0..-1..-1..-1..-1
.3...0...0...0...0...0...0...0...0...0...0
.4...0...0...0...0...0...0...0...0...0...0
.5...0..-1...0...0...0...0...0...0...0...0
.6..-1...0...0...0...0...0...0...0...0...0
.7...0..-1...0...0...0...0...0...0...0...0
.8..-1..-1...0...0...0...0...0...0...0...0
.9..-1..-1...0...0...0...0...0...0...0...0
10..-1..-1...0...0...0...0...0...0...0...0
Ну и решение 10 на 10:

(Оффтоп)

1111111111__0000000000
11111111_11_0000000000
11111111_1_10000000000
111111_111_10000000000
1111_11111_10000000000
11_1111111_10000000000
_111111111_10000000000
_11111111101_000000000
_111111111010_00000000
_1111111110_0100000000
_11111111_010100000000
_1111111_1010100000000
_111111101_10100000000
_11111110101_100000000
_1111111010101_0000000
_11111110101010_000000
_111111101010_01000000
_1111111010_0101000000
_11111110_010101000000
_111111_01010101000000
_11111_101010101000000
_1111101_1010101000000
_111110101_10101000000
_11111010101_101000000
_1111101010101_1000000
_111110101010101_00000
_1111101010101010_0000
_11111010101010_010000
_111110101010_01010000
_1111101010_0101010000
_11111010_010101010000
_111110_01010101010000
_1111_0101010101010000
_111_10101010101010000
_11101_101010101010000
_1110101_1010101010000
_111010101_10101010000
_11101010101_101010000
_1110101010101_1010000
_111010101010101_10000
_11101010101010101_000
_111010101010101010_00
_1110101010101010_0100
_11101010101010_010100
_111010101010_01010100
_1110101010_0101010100
_11101010_010101010100
_111010_01010101010100
_1110_0101010101010100
_11_010101010101010100
_1_1010101010101010100
_101_10101010101010100
01_1_10101010101010100
01_101_101010101010100
0101_1_101010101010100
0101_101_1010101010100
010101_1_1010101010100
010101_101_10101010100
01010101_1_10101010100
01010101_101_101010100
0101010101_1_101010100
0101010101_101_1010100
010101010101_1_1010100
010101010101_101_10100
01010101010101_1_10100
01010101010101_101_100
0101010101010101_1_100
0101010101010101_101_0
0101010101010101_10_10
010101010101010101__10
010101010101010101_01_
0101010101010101010_1_
01010101010101010_011_
010101010101010_01011_
0101010101010_0101011_
01010101010_010101011_
010101010_01010101011_
0101010_0101010101011_
01010_010101010101011_
010_01010101010101011_
0_0101010101010101011_
00_101010101010101011_
0001_1010101010101011_
000101_10101010101011_
00010101_101010101011_
0001010101_1010101011_
000101010101_10101011_
00010101010101_101011_
0001010101010101_1011_
000101010101010101_11_
00010101010101010_111_
000101010101010_01111_
0001010101010_0101111_
00010101010_010101111_
000101010_01010101111_
0001010_0101010101111_
00010_010101010101111_
000_01010101010101111_
0000_1010101010101111_
000001_10101010101111_
00000101_101010101111_
0000010101_1010101111_
000001010101_10101111_
00000101010101_101111_
0000010101010101_1111_
000001010101010_11111_
0000010101010_0111111_
00000101010_010111111_
000001010_01010111111_
0000010_0101010111111_
00000_010101010111111_
000000_10101010111111_
00000001_101010111111_
0000000101_1010111111_
000000010101_10111111_
00000001010101_111111_
0000000101010_1111111_
00000001010_011111111_
000000010_01011111111_
0000000_0101011111111_
00000000_101011111111_
00000000_1010111111_11
00000000_10101111_1111
00000000_101011_111111
00000000_1010_11111111
00000000_10_0111111111
00000000__010111111111
00000000_0_10111111111
00000000_001_111111111
0000000000_1_111111111
0000000000__1111111111

Не особо оно сильно отличается от случая с одним пробелом. Разве только если существенно изменить условие задачи: разрешить прыгать баранам через друг друга в свободные места одновременно. Тогда в плане оптимальности ходов действительно интерес появится.

-- 14.01.2018, 22:36 --

Нашёл ошибку в своей программе. После нахождения конечной позиции и внутреннего цикла вышел, а из внешнего забыл выйти. Потому часть данных выше ошибочна: количество ходов может быть завышена. Для задачи с одним пропуском, однако, все пересчитанные ходы совпали. Видимо, решение находится на самой высокой вершине дерева решений. Для случая с двумя пропусками, нашлись улучшения.
Теперь табличка выглядит так:
......0....1....2....3....4....5....6....7....8....9...10
.0....1....3....3....5....5....7....7....9....9...11...11
.1....3....6....7...10...12...15...17...19...21...24...26
.2....3....7...11...14...17...21...24...27...31...34...37
.3....5...10...14...19...23...28...32...37...41...46...50
.4....5...12...17...23...29...34...40...45...51...56...62
.5....7...15...21...28...34...41...47...54...60...67...73
.6....7...17...24...32...40...47...55...62...70...77...85
.7....9...19...27...37...45...54...62...71...79...88...96
.8....9...21...31...41...51...60...70...79...89...98..108
.9...11...24...34...46...56...67...77...88...98..109..119
10...11...26...37...50...62...73...85...96..108..119..131
А после вычитания величины $\left( N+1 \right)\left( M+1 \right)+\left\lfloor \frac{N+M}{2} \right\rfloor $ она становится такой:
.....0...1...2...3...4...5...6...7...8...9..10
.0...0...1..-1...0..-2..-1..-3..-2..-4..-3..-5
.1...1...1...0...0...0...0...0..-1..-1..-1..-1
.2..-1...0...0...0..-1...0..-1..-1..-1..-1..-2
.3...0...0...0...0...0...0...0...0...0...0...0
.4..-2...0..-1...0...0...0...0...0...0...0...0
.5..-1...0...0...0...0...0...0...0...0...0...0
.6..-3...0..-1...0...0...0...0...0...0...0...0
.7..-2..-1..-1...0...0...0...0...0...0...0...0
.8..-4..-1..-1...0...0...0...0...0...0...0...0
.9..-3..-1..-1...0...0...0...0...0...0...0...0
10..-5..-1..-2...0...0...0...0...0...0...0...0
Решение для 10 на 10 получилось совершенно другое, но число ходов то же самое: 130 (131 позиция). Оба решения, разумеется, правильные. Видимо существует множество различных оптимальных решений. Интересно было бы их тоже подсчитать.

(Оффтоп)

1111111111__0000000000
111111111_1_0000000000
111111111_10_000000000
1111111_1110_000000000
11111_111110_000000000
111_11111110_000000000
1_1111111110_000000000
1_11111111_01000000000
1_1111111_101000000000
1_111111101_1000000000
1_11111110101_00000000
1_111111101010_0000000
1_1111111010_010000000
1_11111110_01010000000
1_111111_0101010000000
1_11111_10101010000000
1_1111101_101010000000
1_111110101_1010000000
1_11111010101_10000000
1_1111101010101_000000
1_11111010101010_00000
1_111110101010_0100000
1_1111101010_010100000
1_11111010_01010100000
1_111110_0101010100000
1_1111_010101010100000
1_111_1010101010100000
1_11101_10101010100000
1_1110101_101010100000
1_111010101_1010100000
1_11101010101_10100000
1_1110101010101_100000
1_111010101010101_0000
1_1110101010101010_000
1_11101010101010_01000
1_111010101010_0101000
1_1110101010_010101000
1_11101010_01010101000
1_111010_0101010101000
1_1110_010101010101000
1_11_01010101010101000
1_1_101010101010101000
1_101_1010101010101000
101_1_1010101010101000
101_101_10101010101000
10101_1_10101010101000
10101_101_101010101000
1010101_1_101010101000
1010101_101_1010101000
101010101_1_1010101000
101010101_101_10101000
10101010101_1_10101000
10101010101_101_101000
1010101010101_1_101000
1010101010101_101_1000
101010101010101_1_1000
101010101010101_101_00
10101010101010101_1_00
10101010101010101_100_
1010101010101010101_0_
101010101010101010_10_
1010101010101010_0110_
10101010101010_010110_
101010101010_01010110_
1010101010_0101010110_
10101010_010101010110_
101010_01010101010110_
1010_0101010101010110_
10_010101010101010110_
_01010101010101010110_
0_1010101010101010110_
001_10101010101010110_
00101_101010101010110_
0010101_1010101010110_
001010101_10101010110_
00101010101_101010110_
0010101010101_1010110_
001010101010101_10110_
00101010101010101_110_
00101010101010101_1_01
00101010101010101__101
00101010101010101_01_1
001010101010101010_1_1
0010101010101010_011_1
00101010101010_01011_1
001010101010_0101011_1
0010101010_010101011_1
00101010_01010101011_1
001010_0101010101011_1
0010_010101010101011_1
00_01010101010101011_1
000_1010101010101011_1
00001_10101010101011_1
0000101_101010101011_1
000010101_1010101011_1
00001010101_10101011_1
0000101010101_101011_1
000010101010101_1011_1
00001010101010101_11_1
0000101010101010_111_1
00001010101010_01111_1
000010101010_0101111_1
0000101010_010101111_1
00001010_01010101111_1
000010_0101010101111_1
0000_010101010101111_1
00000_10101010101111_1
0000001_101010101111_1
000000101_1010101111_1
00000010101_10101111_1
0000001010101_101111_1
000000101010101_1111_1
00000010101010_11111_1
000000101010_0111111_1
0000001010_010111111_1
00000010_01010111111_1
000000_0101010111111_1
0000000_101010111111_1
000000001_1010111111_1
00000000101_10111111_1
0000000010101_111111_1
000000001010_1111111_1
0000000010_011111111_1
00000000_01011111111_1
00000000_010111111_111
00000000_0101111_11111
00000000_01011_1111111
00000000_010_111111111
00000000_0_01111111111
00000000_00_1111111111
0000000000__1111111111

[bobah16]

Решение http://www.cyberforum.ru/combinatorics/ ... st12026044