2014 dxdy logo

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

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




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


01/12/11

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

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

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


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

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


01/12/11

8634
mihaild
А разве доказывать минимальность разве не нужно?

-- 05.11.2018, 00:40 --

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

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


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

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


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

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


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

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


16/07/14
8347
Цюрих
И правда, заврался я.

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


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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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