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

Если двигать фишки по диагонали можно:

Если двигать фишки по диагонали можно, то кратчайший путь от правой верхней клетки до левой нижней клетки - это двигаться всё время только влево вниз. Тогда, чтобы переместиться из правой верхней клетки до левой нижней клетки, потребуется 2 хода. А, так как фишек у нас всего 9, то всего потребуется:

2 * 9 = 18 ходов

Ответ: потребуется 18 ходов.

Если двигать фишки по диагонали нельзя:

Если двигать фишки по диагонали можно, то у нас есть 2 кратчайших пути от правой верхней клетки до левой нижней клетки, а именно:

1. Переместиться 2 раза вниз, затем 2 раза влево
2. Переместиться 2 раза влево, затем 2 раза вниз

И там, и там, чтобы переместиться от правой верхней клетки до левой нижней клетки, потребуется 2 + 2 = 4 хода. А, так как фишек у нас всего 9, то всего потребуется:

4 * 9 = 36 ходов

Ответ: потребуется 36 ходов.

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

Тогда, повторим эту операцию для остальных 4 карточек. Итого, для того, чтобы упорядочить все карточки в порядке возрастания, нам потребуется:

5 * 5 = 25 ходов

Это ответ на пункт а).

Теперь ответим на пункт б).

Ссылаясь на ответ пункта а), заметим, что он нечётный. А число 100 - чётное. А чтобы ничего не поменялось, надо сделать чётное количество ходов. Но 100 - 25 = 75, а 75 - нечётное число. Значит, отсортировать карточки по возрастанию ровно за 100 ходов нельзя, так как если прибавить чётное число к чётному, всегда получится чётное число.

Ответ: нельзя.

Наименьшим количеством операций, с помощью которых гарантированно можно перекрасить все клетки в красный цвет - это само количество клеток, а именно 20. Ведь изначально вся полоска может быть полностью синей, и тогда нам потребуется перекрасить абсолютно каждую клетку в красный цвет, потратив 20 операций.

Ответ: за 20 операций.

Нарисуем нашу доску с клетками и фишками.

Звёздочками обозначен правый верхний угол, где изначально расположены фишки.

А жёлтым закрашен левый нижний угол, место назначения, куда надо переправить фишки.

Чтобы добраться из правого верхнего до левого нижнего угла, каждой фишке надо пройти две клетки вниз и две клетки налево, в любом порядке. Всего путь займёт 4 клетки, а значит, 4 хода.

9 фишек переправятся в место назначения за 9*4 = 36 ходов.

Ответ:

2. считаем: единица достигнет своего места самое малое за 5 перестановок.

тройке потребуется 4 хода, чтобы разойтись с 4, 6, 8, 10 и встать после двойки.

пятёрке как ни крути, но придётся разменяться местами с 6, 8, 10, чтобы встать за четвёркой. Это 3 хода.

семёрке надо будет обойти 8, 10, чтобы занять место за 6. Ещё 2.

девятке поменяться с 10, так как их взаимное расположение никто кроме них самих изменить не способен. +1.

Итого: 5 + 4 + 3 + 2 + 1.

Выходит, вынь да положь, но как минимум 15 перестановок сделать придётся.

Это и есть искомый минимум.

Ровно за 100 ходов сделать не получится, потому что все перемещения карточек парные, соответственно, к 15 может прибавиться некоторое чётное число, а значит, количество ходов всегда будет нечётным.

Ответ:

Каждая фишка должна сдвинуться на пять клеток влево и на пять клеток вниз, чтобы занять своё место в новом положении.

Итого, каждая фишка должна сдвинуться на десять клеток, для этого каждая фишка должна сделать десять ходов.

Девять фишек соответственно, должны суммарно сдвинуться на девяносто клеток, для этого этим фишкам нужно сделать девяносто ходов.

Начинать движение нужно с самой левой нижней фишки, потом следующей фишке в этом ряду, затем - последней фишке в этом ряду.

Потом - аналогично сдвигаться фишкам среднего, а затем и верхнего рядов.

1. Для того, чтобы узнать за какое минимальное число ходов фишки можно перевести в левый нижний угол 3х3, необходимо сначала перевести десять фишек из правого верхнего угла (1, 3) в левый нижний угол (3, 1) шахматной доски, а это можно сделать узнав минимальное число ходов для каждой фишки. Каждая фишка должна переместиться из позиции (i, j) в (3, 1). Для каждой фишки расстояние, которое нужно пройти, можно выразить как сумму изменений по координатам:

дельта х = |3 - i| + |1 - j|

Фишки из правого верхнего угла 9 раз имеют координаты (1, 3), где все фишки занимают клетки (1, 3), (1, 2) и (1, 1).

Теперь нужно рассмотреть минимальные ходы для каждой фишки:

Для фишек из клетки (1, 3): потребуются 2 хода:

перемещение в (1, 2) (1 ход)

перемещение в (2, 2) (2 ход)

перемещение в (3, 2) (3 ход)

перемещение в (3, 1) (4 ход)

Можно сначала переместить фишки в ведущие позиции, что займет 4 хода. Таким образом, за 4 операции можно перепрыгнуть одну фишку в другую, чтобы освободить место для следующей фишки. Далее продолжим перемещение оставшихся фишек, но повторно учитывая, что старое расположение фишек может позволить свободное место для новых фишек. Лучший сценарий предллагает, что 9 фишек перемещаются в 4 хода, и каждая фишка проходит минимальное расстояние. Таким образом, минимальное количество ходов, чтобы перенести все фишки, составляет 6.

1. Вторая задача. Для решения необходимо использовать концепцию инверсий. Инверсия это пара карточек, которая располагается в неправильном порядке относительно того, как они должны быть расположены в порядке возрастания.

а) Наименьшее число ходов

Изначальный порядок карточек: 2, 4, 6, 8, 10, 1, 3, 5, 7, 9.

Идеальный порядок: , 2, 3, 4, 5, 6, 7, 8, 9, 10.

Теперь подсчитаем количество инверсий в исходном порядке:

Пары инверсий:

(2, 1), (4, 1), (6, 1), (8, 1), (10, 1) -> 5 инверсий.

(2, 3), (4, 3), (6, 3), (8, 3), (10, 3) -> 5 инверсий.

(2, 5), (4, 5), (6, 5), (8, 5), (10, 5) -> 5 инверсий.

(2, 7), (4, 7), (6, 7), (8, 7), (10, 7) -> 5 инверсий.

(2, 9), (4, 9), (6, 9), (8, 9), (10, 9) -> 5 инверсий.

Итого: 5 + 5 + 5 + 5 + 5 = 25 инверсий.

Каждый раз когда мы меняем местами две соседние карточки, количество инверсий уменьшается на 1 (или остается прежним), поэтому, чтобы отсортировать карточки, потребуется как минимум 25 ходов.

Ответ на а) 25 ходов.

б) по вопросу можно ли сделать ровно за сто ходов? Чтобы определить, можно ли отсортировать карточки за 100 ходов, рассмотрим, что в процессе сортировки количество инверсий должно уменьшаться и идти по четной (или нечетной) последовательности.

Начальное количество инверсий (25) нечетное число.

Каждый ход меняет количество инверсий на 1 (то есть, чётное число инверсий становится нечетным и наоборот).

Известно, что сортировка с 25 инверсиями, чтобы привести в порядок, будет выполнена за нечетное количество ходов, и любой полный порядок (0 инверсий) требует четного числа ходов (поскольку 0 это четное число).

Следовательно, нельзя выполнить сортировку за ровно 100 ходов, так как это четное число и начальное количество инверсий не позволяет достичь четного числа ходов.

Ответ на б) Нет, нельзя сделать ровно за 100 ходов.

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

Перекраска половин: на первом шаге можно перекрасить всю полоску сразу. После первой операции вся полоска станет синей (если изначально была красной).

Перекраска каналов: на втором шаге можно перекрасить первую половину (первую десятку клеток) в красный цвет. Теперь появилась первая половина красной, а вторая синей.

Вторая половина: на третьем шаге можно перекрасить вторую половину в красный цвет. Теперь вся полоска снова станет красной. Таким образом, для гарантированного перекрашивания всей полоски в красный цвет требуется не более 3 операций.

Ответ: 3 операции.

1. Если нельзя передвигать фишки по диагонали, то, для перемещения на шахматной доске 8х8 девяти фишек из верхнего угла 3x3 в противоположный нижний угол, потребуется 90 ходов. По 10 ходов для каждой фишки.
2. Расставить карточки в нужном порядке можно за 15 ходов, и за любое нечётное число ходов большее 15. За 100 - нельзя.
3. Если красные и синии клетки в полоске чередуются (по 10 каждого цвета), то наименьшее число операций, гарантирующее перекраску всей полоски, будет 10 операций. Оно же будет и наибольшим ;)