Перейти к содержимому

Нужно обойти как можно больше клеток

  • автор:

Нужно обойти как можно больше клеток

Квадрат 3×3 заполнен цифрами так, как показано на рисунке слева. Разрешается ходить по клеткам этого квадрата, переходя из клетки в соседнюю (по стороне), но ни в какую клетку не разрешается попадать дважды.

Петя прошёл, как показано на рисунке справа, и выписал по порядку все цифры, встретившиеся по пути, – получилось число 84937561. Нарисуйте другой путь так, чтобы получилось число побольше (чем больше, тем лучше).

Решение

Если обойти все клетки доски, то получится девятизначное число, которое, конечно, будет больше любого восьмизначного.
Девятизначное число тем больше, чем больше его первая цифра. Но девятизначного числа, начинающегося с 9, построить не удастся. Более того, ни для какой из чёрных клеток (см. рисунок ниже) не существует начинающегося в ней пути, проходящего по всем клеткам доски. Действительно, ход из чёрной клетки всегда приводит в белую. Всего чёрных клеток четыре, поэтому белых клеток на любом таком пути тоже не более четырёх – все пять белых клеток так не обойти.

Поэтому надо начать с самой большой «белой» цифры – цифры 5, перейти к её наибольшему соседу, цифре 7, а потом к её наибольшему соседу, цифре 3. Затем придётся перейти к клетке 6 – иначе обойти всю доску не получится. Далее путь единственен.

Ответ

Наибольшее число, которое можно получить, – 573618492 (см. рис.).

Замечания

Источники и прецеденты использования

олимпиада
Название Математический праздник
год
Год 2012
Класс
Класс 7
задача
Номер 1

Обойти как можно больше клеток, как нарисовать путь?

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

Результат смотрите на скриншоте.

Для удобства начало пути отмечено стрелочкой, а конечная остановка треугольником.

На скрине видно, что только одна точка осталась неиспользованной (синий цвет).

Интересно, а кто-нибудь сумел пройти путь по всем белым клеткам..

Научный форум dxdy

1. Отметить на доске 8Х8 несколько клеток так, чтобы любая (в том числе и любая отмеченная) клетка граничила по стороне ровно с одной отмеченной клеткой.

Ясно, что отмеченные клетки должны группироваться «парами». Мне кажется, что подобная задача невыполнима.

2. Можно ли доску 6Х6 с двумя вырезанными противоположными углами обойти ходом шахматного коня, побывав в каждой клетке ровно по одному разу?

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

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

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

28.01.2008, 14:43
Переезжаем из «Помогите решить» в олимпиадный раздел
Re: Три задачи на шахматной доске
28.01.2008, 15:00
lexus c. писал(а):

Помогите, пожалуйста с этими тремя задачами:

1. Отметить на доске 8Х8 несколько клеток так, чтобы любая (в том числе и любая отмеченная) клетка граничила по стороне ровно с одной отмеченной клеткой.

Ясно, что отмеченные клетки должны группироваться «парами». Мне кажется, что подобная задача невыполнима.

Нашел нужную расстановку. Перечислю отмеченные клетки, пользуясь шахматными координатами.

$a3,a4,a7,a8,b1,c1,c5,c6,d3,d8,e3,e8,f1,f5,f6,g1,h3,h4,h7,h8$

28.01.2008, 15:05

PAV , ну, здесь только одна задача, насколько мне известно, олимпиадная.

Henrylee , точно! Спасибо Вам большое )

28.01.2008, 15:38
lexus c. писал(а):

2. Можно ли доску 6Х6 с двумя вырезанными противоположными углами обойти ходом шахматного коня, побывав в каждой клетке ровно по одному разу?

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

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

28.01.2008, 16:01
Brukvalub писал(а):
lexus c. писал(а):

2. Можно ли доску 6Х6 с двумя вырезанными противоположными углами обойти ходом шахматного коня, побывав в каждой клетке ровно по одному разу?

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

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

Надо же, и правда )))
Что-то я торможу )
Спасибо огромное!
28.01.2008, 17:57
Brukvalub писал(а):
на доске, стороны которой имеют четное число клеток, такие вырезы убирают клетки одного цвета.

От четности не зависит. Просто диагонали досок так раскрашивают
28.01.2008, 18:07
Батороев писал(а):

на доске, стороны которой имеют четное число клеток, такие вырезы убирают клетки одного цвета.

От четности не зависит. Просто диагонали досок так раскрашивают

Разве я где-либо утверждал, что у досок с нечетным числом клеток на стороне это свойство нарушается?
28.01.2008, 18:53
Батороев писал(а):
От четности не зависит.

От чётности зависит другое, для нас тоже нужное: что клеточек каждого цвета на доске (до обрезания) поровну.

28.01.2008, 19:03

А, и вот ещё одна вдогонку:

Можно ли доску 10*10 разрезать на набор фигурок из четырех клеток в форме букв Г и L (т.е. набор может быть смешанным)?

28.01.2008, 19:23

Последний раз редактировалось Батороев 28.01.2008, 19:32, всего редактировалось 1 раз.

ИСН писал(а):
Батороев писал(а):
От четности не зависит.

От чётности зависит другое, для нас тоже нужное: что клеточек каждого цвета на доске (до обрезания) поровну.

Я только «обрезание» и имел в виду
28.01.2008, 19:28
Brukvalub писал(а):
Батороев писал(а):

на доске, стороны которой имеют четное число клеток, такие вырезы убирают клетки одного цвета.

От четности не зависит. Просто диагонали досок так раскрашивают

Разве я где-либо утверждал, что у досок с нечетным числом клеток на стороне это свойство нарушается?

А на прямоугольной доске вообще нет диагоналей.

28.01.2008, 19:47

У меня есть смутное ощущение, что задачу про тараканов можно переформулировать таким образом, что она станет похожа на первую. В качестве отмеченных будут пустые клетки после «тараканьих бегов» итп.. Только условия «соседства» нужно подобрать особым образом..

Добавлено спустя 14 минут 6 секунд:

Может быть таким образом.
Будем считать клетки с тараканами после бегов (непустые) отмеченными Тогда задача (видимо) переформулируется так:
отметить на доске клетки так, чтобы любая клетка граничила стороной с двумя отмеченными. Причем отмтить таким образом, чтобы число отмеченнх леток было наименьшим.

29.01.2008, 10:05
lexus c. писал(а):

Можно ли доску 10*10 разрезать на набор фигурок из четырех клеток в форме букв Г и L (т.е. набор может быть смешанным)?

Нельзя. Потому что 25 фигур.

Утверждение Если прямоугольная доска разбивается на Г- и L- фигуры, то разбиение состоит из чётного числа фигур.
Пусть такое разбиение существует — доска покрыта Г- и L- фигурами полностью и без пересечений. По крайней мере одна из длин сторон доски (или количество рядов $h$, или количество столбцов $w$) должна быть чётна. Пусть количество столбцов $w$чётно. Будем по одной снимать фигуры с доски и подсчитывать, сколько клеток осталось закрыто фигурами на каждой горизонтали. Сначала в каждом ряду закрыто по $w$клеток $x_1=x_2=. =x_h=w$, после снятия всех фигур станет $x_1=x_2=. =x_h=0$. Заметим, что снятие каждой фигуры уменьшает счётчики клеток на (1,3) или (3,1) или (1,1,2) или (2,1,1). Рассмотрим чётности этих количеств $y_i=x_i \mod 2$. Перед снятием фигур и после снятия все $y_i=0$, а снятие одной фигуры инвертирует чётность какой-то пары соседних счётчиков $y_i, y_<i+1>$» />. Легко доказать по индукции (индукция по числу рядов <img decoding=), что количество парных инверсий (равное количеству фигур) должно быть чётным.

29.01.2008, 10:13

Про тараканов.
Действительно, удалось найти 1 расстановку, в которой любая клетка граничит ровно с 2-мя отмеченными и одну расстановку (с точностью до поворота доски), где выполняется условие выше кроме 2-х клеток, которые граничат с тремя отмеченными. В обоих случаях число неотмеченных (путых) клеток 24.

Страница 1 из 2 [ Сообщений: 23 ] На страницу 1 , 2 След.

Задачи 6 класса (для тренировки и обсуждения)

2002 год
1. Какую наименьшую сумму цифр может иметь натуральное число, делящееся на 6 ? на 66 ? на 666 ?
2. На саммит приехали 10 президентов. Организаторы знают, что каждый из них свободно говорит на каких-то трех из шести официальных языков ООН, но не знают, кто на каких именно. Организаторы планируют проведение пресс-конференций, на каждой из которых будет только один рабочий язык.
Какое наименьшее число пресс-конференций нужно провести, чтобы каждый президент смог участвовать хотя бы в одной из них без переводчика?
3. На какие 13 правильных многоугольников можно разрезать правильный 12-угольник?
4. Полем для игры в «Антикрестики» (как и в обычные «крестики-нолики») служит квадрат 3х3. Два игрока по очереди ставят ОДИНАКОВЫЕ крестики (как и обычно, крестик можно поставить в любую свободную клетку). Другое отличие: тот из двух игроков, кто поставит третий крестик на какой-либо одной прямой (вертикали, горизонтали или диагонали), ПРОИГРЫВАЕТ.
У которого из двух игроков есть возможность наверняка победить в этой игре?
5. Банк покупает доллары у клиентов по 31 рублю, а продает за 32 рубля, покупает евро по 27 рублей, а продает за 28 рублей. У одного из двух братьев есть пачка купюр евро, а у другого – долларов.
В каком соотношении они должны поменять доллары на евро друг другу, чтобы оба могли считать обмен справедливым?
6. Все грани куба с ребром длины 2 разбиты средними линиями на единичные квадраты.
Можно ли раскрасить эти квадраты в четыре цвета так, чтобы любые два из них, имеющие общую вершину, были закрашены в разные цвета?

2003 год
1. В одной из 16 клеток доски 4х4 стоит Шуршавчик, который может ходить по горизонтали или по вертикали на 2 или на 3 клетки (перелетая по воздуху через 1 или 2 клетки). Выберите одну из клеток поля и, начав с неё, обойдите Шуршавчиком как можно больше клеток, не вставая ни на какую более одного раза. Порядок обхода клеток укажите номерами 1, 2, 3, … .
2. Из пяти различных цифр Дима составил пятизначное число. Взяв оставшиеся пять цифр, Влад тоже составил из них пятизначное число. Георгий сложил числа мальчиков. Могло ли у него получиться число, в котором только единицы и двойки?
3. В последовательности 1, 1, 2, 3, 5, 8, 13, … каждое число, начиная с третьего, равно сумме двух предыдущих.
Могут ли в этой последовательности встретиться подряд два числа, кратных 2003?
4. Предприимчивый Георгий купил на рынке партию ручек и предлагает одноклассникам либо одну ручку за 5 рублей, либо три ручки за 10 рублей, потому что хочет от каждого покупателя получить одинаковую прибыль. А за сколько рублей Георгию в таком случае надо продавать ручки покупателю, который хочет купить 5 ручек?
5. Катя Угольникова нарисовала несколько углов, величина каждого из которых больше 10°, меньше 90° и выражается целым числом градусов. При каком наименьшем количестве нарисованных углов можно утверждать, что среди них есть хотя бы три равных?
6. Если последние три цифры числа 2003 записать в обратном порядке, то получится 300. Именно 300 лет исполняется Санкт-Петербургу в мае 2003 года.
Сколько еще раз в XXI веке наступит год с таким же свойством?

2004 год
1. Москва основана в 1147 году.
Был ли и будет ли когда-нибудь такой год, в котором Москве исполняется столько лет, сколько получится, если откинуть от этого года первую цифру?
2. Лев придумал новую алгебру, в которой сумма чисел A и B выражается через обычные арифметические действия формулой (A+B)/(1-AB) .
Чему в новой алгебре Льва равно произведение 3 на 3 ?
3. На клетчатой бумаге по линиям прямоугольной сетки со стороной 1 построена замкнутая ломаная длины 24.
Какую наибольшую площадь может охватить эта ломаная?
4. Найдите количество таких трёхзначных чисел, у которых все цифры различны, первая цифра делится на 3, вторая — на 2.
5. Найдите наименьшее натуральное число, которое нацело делится на 2000, 2001, 2002, 2003 и 2004.
6. Лев купил себе на завтрак стакан сока, салат и кусочек хлеба. Он заметил, что цена сока составляет столько же процентов от цены всего завтрака, сколько цена салата от цены сока. А выпив сок, он понял, что цена хлеба составляет 10% от цены оставшейся части завтрака.
Сколько процентов от цены завтрака составляла цена салата?

2005 год
1. Назовите дату, ровно на 2005 недель более раннюю, чем 24 января 2005 года.
2. В театре есть три прожектора – красный, синий и желтый, которыми с помощью переключателей управляют два осветителя. Переключатель позволяет зажечь любой погашенный прожектор, либо погасить зажженный. Комбинация красного и синего цветов дает фиолетовый, красного и желтого – оранжевый, а синего и желтого – зеленый. Включение сразу всех прожекторов назовем белым цветом, а гашение всех – черным.
В некоторый момент сцена была окрашена в оранжевый цвет. Что произойдет, если одновременно, но не сговариваясь друг с другом, один из осветителей захочет перекрасить ее в фиолетовый цвет, а другой – в зеленый?
3. Министр финансов Дурляндии выпустил в обращение только монеты достоинством в 7 и 11 дуриков. Покупатель должен заплатить продавцу ровно 5 дуриков.
Сумеют ли они рассчитаться, если у каждого из них есть только по 3 монеты того и другого достоинства?
4. Слиток имеет форму кирпича и весит 10 килограмм. Его муляж на 60% короче, на 25% уже и сделан из вдвое более легкого материала. Оказалось, что весят они одинаково.
Что выше – муляж или слиток – и на сколько процентов?
5. Квадратную клеточку можно двумя способами разбить диагональю на два треугольника. Если один из треугольников закрасить, то такую фигуру назовем ежиком. Двух ежиков нельзя размещать на клетчатой бумаге так, чтобы они имели общую сторону.
Какое наименьшее число ежиков и как можно расположить в квадрате 6х6 клеток, чтобы к ним с соблюдением данного условия уже нельзя было добавить ни одного нового?
6. Если одно число с суммой цифр, делящейся на 3, умножить на другое число с таким же свойством, то всегда получится число с суммой цифр, делящейся на 9.
Сохранится ли истинность этого утверждения, если 3 и 9 заменить в нем на 333 и 999?

2006 год
1. Лев записал в таблицу 6х6 целые числа. Оказалось, что каждое число равно среднему арифметическому остальных 5 чисел своего столбца. Могут ли в этой таблице быть различные числа?
2. Ник и Дик придумали себе игру. Сначала они выбирают три различные цифры (от 0 до 9; Ник – первую и третью, а Дик – вторую). Затем Дик выбирает арифметической действие (сложение, вычитание, умножение или деление). Ник должен поставить знак этого действия между двумя из выбранных цифр так, чтобы в итоге получилась третья (в любом порядке). Если он сумеет это сделать, то выигрывает, а если нет, то проиграл. Например, если выбраны цифры 1, 2, 3 и вычитание, то Ник выиграет (так как 3-1=2), а если умножение, то проиграет. У которого из двух игроков есть возможность сделать беспроигрышный выбор?
3. У Винни-Пуха есть несколько горшочков из-под мёда и несколько лопнувших шариков. Так как красных шариков у Винни-Пуха было больше, чем шариков какого-либо другого цвета, то сначала он разложил в горшочки по одному красному шарику. Но несколько горшочков остались пустыми, и тогда Винни-Пух положил в них по одному зеленому шарику. Оставшиеся зеленые шарики он разложил в те горшочки, где уже лежали красные. Затем Винни-Пух разложил по горшочкам шарики остальных цветов, следя за тем, чтобы в каждом горшочке оказалось разное число шариков. Какое наименьшее число горшочков могло быть у Винни-Пуха?
4. Лев утверждает, что если сумма цифр числа, записанного в системе счисления с основанием 2006, делится на 2005, то и само число тоже делится на 2005. Прав ли он?
5. Лев хочет раскрасить все точки плоскости в несколько цветов так, чтобы на каждой прямой отсутствовали точки хотя бы одного из использованных им цветов. Какое наименьшее число цветов потребуется для такой раскраски?
6. Одну из сторон прямоугольника увеличили на 2006%. На сколько процентов нужно уменьшить другую его сторону, чтобы площадь прямоугольника осталась прежней?

2007 год
1. Лугопарк имеет форму квадрата 12х12км, разбитого на три полосы, шириной по 4км. Одна из крайних полос покрыта снегом, другая — песком, а на средней полосе залит каток. Конькобежец бежит по льду со скоростью 12км/час, по снегу 4км/час, а по песку — 3 км/час. Лыжник бежит по льду со скоростью 3км/час, по снегу 12км/час, а по песку — 4 км/час. Атлет бежит по льду со скоростью 4км/час, по снегу 3км/час, а по песку — 12км/час. Все трое одновременно стартуют из одного угла лугопарка, чтобы финишировать в противоположном. Каждый из них самостоятельно выбирает наиболее быстрый для себя маршрут движения. Кто из них прибежит первым?
2. У Миши есть чудо-калькулятор с двумя кнопками, одна из которых увеличивает высвеченное на индикации число на 1, а другая — в 3 раза. В начальный момент на индикации 0. Помогите ему так нажать на эти кнопки, чтобы получить на индикации 2007. Как это сделать наименьшим числом нажатий?
3. В понедельник, среду и пятницу акции ООО «Рога и Копыта» росли в цене на 20%, а во вторник и четверг падали на 20%. В какой момент недели курс акций был выше всего?
4. Таня последовательно выписывает натуральные числа (1, 2, 3, 4, . ), ищет общую сумму их цифр и проверяет, не окажется ли она равной 2007. На каком числе Таня остановится, и что покажет её проверка?
5. Материки желтой планеты занимают на ней вдвое большую площадь, чем океаны. Треть площади материков занимают озера. Четверть часть площади океанов и пятую часть площади озер занимают острова. Чего больше на поверхности желтой планеты — суши или воды?
6. Два игрока по очереди ставят цифры в свободные клетки квадрата 4х4. Тот, кто ставит первую цифру, может ставить только нечетные цифры. Он стремится сделать так, чтобы в каждой строчке, каждом столбце и каждом угловом квадрате 2х2 все 4 цифры оказались различными. Второй может ставить только четные цифры и старается помешать первому. Однако он не имеет права нарушать названные правила до тех пор, пока остается иная возможность. Кто из них достигнет своей цели, если будет действовать наилучшим образом?

2008 год
1. Двое детей по очереди (пропускать ход нельзя!) выставляют на стол либо одну фишку, либо столько, сколько их уже стоит на столе (если нужное число фишек еще осталось в коробочке). Выигрывает тот из них, кто поставит последнюю фишку. В начале игры на столе фишек нет, а в коробочке – 6. Кто выиграет, если будет играть наилучшим образом?
2. В дивизионе меньше тысячи солдат, составляющих три одинаковые по численности батареи. Майор хочет построить их всех на плацу в форме прямоугольника. Сначала он хотел поставить по 17 солдат в каждой шеренге, но для этого не хватило одного солдата. Тогда он попытался поставить по 13 солдат в каждой шеренге, но в этот раз один солдат оказался лишним. Сколько солдат в одной батарее?
3. Архитектор хочет спланировать новый город, вокруг которого пройдет кольцевая автодорога в форме окружности, а все 2008 улиц должны быть прямыми. Все перекрестки в этом городе должны иметь форму буквы Т: одна улица (или КАД) проходит перекресток насквозь, а другая в него упирается. Найдите число перекрестков.
4. Арбуз весом 3кг стоит 11 гривен, 4кг – 13 гривен, а 5кг – 17 гривен. Какие арбузы нужно выбрать, чтобы за 100 гривен купить их как можно больше по весу?
5. Какими двумя цифрами заканчивается десятичная запись числа 20082008 ?
6. Серия трамвайных билетов включает все шестизначные номера от 000000 до 999999. Петербурженка Ася коллекционирует билеты, номера которых делятся на 78. Москвич Вася предпочитает билеты, номера которых делятся на 77, но не делятся на 78. Каких билетов в серии больше и на сколько: интересных Асе или Васе?

2009 год
1. Расставьте одну единицу, две двойки, 3 тройки, 4 четверки, 5 пятерок, 6 шестерок, 7 семерок и 8 восьмерок в клетках квадрата 6х6 так, чтобы во всех строках была одна и та же сумма цифр.
2. Расположите на плоскости 12 спичек так, чтобы они образовали как можно больше различных квадратов. Укажите в ответе число этих квадратов.
3. Нарисуйте на клетчатой бумаге квадрат 6х6. Проведите через его вершины замкнутую ломаную без самопересечений, все остальные вершины которой тоже лежали бы в узлах сетки, а площадь ограниченной ею фигуры была бы как можно меньше.
4. Поверхность большого кубика Рубика состоит из 6 квадратных граней, каждая из которых разбита на 16 клеток (4х4). Муравей может из любой клетки переползти в любую из четырех соседних – имеющих с ней общую сторону (в той же грани, либо через ребро). Помогите муравью обойти все клетки, побывав в каждой из них ровно по одному разу.
5. Магазин снизил цену товара в два раза, благодаря чему продал его в 4 раза больше. Как и во сколько раз изменилась выручка магазина?
6. Четыре фломастера стоят дороже пяти авторучек, четыре авторучки дороже трех фломастеров, а два карандаша ровно столько же, сколько фломастер и авторучка вместе взятые. Антон купил 8 карандашей, а Борис — 9 авторучек. Кто из мальчиков потратил больше денег?

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *