2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Квадрат из палочек
Сообщение05.11.2018, 00:28 
Аватара пользователя


01/12/11
8353
Костя выложил из палочек целочисленной длины квадрат $10\times 10$ (вместе с границей), разбитый на клеточки $1\times 1$. Палочки не пересекаются во внутренних точках. Какое наименьшее число палочек единичной длины могло быть при этом использовано?

(автор задачи - К. Кохась)

 Профиль  
                  
 
 Re: Квадрат из палочек
Сообщение05.11.2018, 00:35 
Заслуженный участник
Аватара пользователя


16/07/14
3055
Москва
Можно считать что все вертикальные палочки целые имеют длину 10, а горизонтальные, соответственно, 1. Подсчет количества палочек оставим всем желающим в качестве упражнения.

 Профиль  
                  
 
 Re: Квадрат из палочек
Сообщение05.11.2018, 00:38 
Аватара пользователя


01/12/11
8353
mihaild
А разве доказывать минимальность разве не нужно?

-- 05.11.2018, 00:40 --

И потом, не все горизонтальные обязаны быть 1, две крайние могут быть тоже 10.

 Профиль  
                  
 
 Re: Квадрат из палочек
Сообщение05.11.2018, 01:07 
Заслуженный участник
Аватара пользователя


16/07/14
3055
Москва
Да, про крайние забыл. Минимальность очевидна: любое пересечение внутри, где используется две вертикальных палочки, переделывается в использующее одно без увеличения общего числа палочек (склеиваемые вертикальные и при необходимости ломаем горизонтальную)

 Профиль  
                  
 
 Re: Квадрат из палочек
Сообщение05.11.2018, 01:09 


05/09/16
6029
mihaild
Можно еще оптимальнее, видимо. Для квадрата 4 на 4 у меня получилось 6 единичных палочек (показаны пунктиром).
Изображение
А по вашему методу нужно 12.

 Профиль  
                  
 
 Re: Квадрат из палочек
Сообщение05.11.2018, 12:19 


14/01/11
2077
wrest, конструкция, аналогичная вашей, даёт для квадрата со стороной $n$ число единичных палочек $2n-2$. С другой стороны, каждый единичный квадрат, прилегающий к границе, очевидно, должен иметь в качестве стороны хотя бы одну единичную палочку. Всего таких квадратов $4n-4$. Мы можем сгруппировать их попарно, уменьшив вдвое требуемое число единичных палочек. Итак, ответ $2n-2$, что для $n=10$ даёт $18$.

 Профиль  
                  
 
 Re: Квадрат из палочек
Сообщение05.11.2018, 14:19 
Заслуженный участник
Аватара пользователя


16/07/14
3055
Москва
И правда, заврался я.

 Профиль  
                  
 
 Re: Квадрат из палочек
Сообщение06.11.2018, 21:43 
Заслуженный участник
Аватара пользователя


16/07/14
3055
Москва
Точнее не заврался, а невнимательно прочитал условия: минимизировали общее число палочек, а не число палочек единичной длины.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: gris


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group