2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Суммы чисел в доминошках
Сообщение23.07.2016, 16:03 
Аватара пользователя


01/12/11

8634
Изображение
Расставьте в клетках указанной фигурки числа от 5 до 14 так, чтобы суммы чисел во всех доминошках были разными (доминошка - это прямоугольник, состоящий из двух клеток, соседних по стороне).
(А. Чухнов)

Одна из наугад подобранных мной расстановок сработала (слева направо, сверху вниз):
5, 6, 8, 11
7, 9, 12
10, 13, 14

Однако я не считаю, что наугад подобрать требуемую расстановку означает решить задачу.
Ну просто повезло, и что из этого? Везение ведь не отражает уровень интеллекта.

Хотелось бы научиться решать эту задачу по-настоящему, но не знаю, как.
Пожалуйста, помогите решить.
Заранее спасибо.

 Профиль  
                  
 
 Re: Суммы чисел в доминошках
Сообщение23.07.2016, 17:24 
Заслуженный участник


27/04/09
28128

(Оффтоп)

Ktina в сообщении #1139672 писал(а):
Везение ведь не отражает уровень интеллекта.
А почему нет?

Везение при выкидывании монетки, будем считать, не отражает. Но везением зовут не только это. Если числа подбирались в голове, они могли испытать её влияние…

 Профиль  
                  
 
 Re: Суммы чисел в доминошках
Сообщение23.07.2016, 18:14 
Аватара пользователя


29/06/15
277
[0,\infty )
Ktina в сообщении #1139672 писал(а):
5, 6, 8, 11
7, 9, 12
10, 13, 14

Это не было наугад, Вы с левого верхнего уголка заполняли по порядку по диагональкам. Можно было с левого нижнего начать и тоже выйдет
10,12,13,14
7 , 9, 11
5 , 6, 8
И такие заполнения интуитивно понятно выбраны, график их над плоскостью чертежа- простая линейчатая поверхность, так проще сделать, что центры тяжести кусков графика над каждой из 13 доминошек окажутся на разной высоте (эти высоты возрастают по диагональкам того же направления)

 Профиль  
                  
 
 Re: Суммы чисел в доминошках
Сообщение23.07.2016, 22:16 
Аватара пользователя


01/12/11

8634
iancaple
Спасибо большое!

 Профиль  
                  
 
 Re: Суммы чисел в доминошках
Сообщение30.12.2016, 01:10 
Аватара пользователя


01/12/11

8634
Вот ещё вариант, возможно, даже более простой:
5, 6, 7, 8
9, 10, 11
13, 14, 12

Здесь верхние две строки заполнялись по порядку, а с нижней пришлось немного «поиграть», однако, учитывая, что там всего 6 вариантов...

-- 30.12.2016, 01:16 --

А вообще, напрашивается вопрос, сколько всего способов?

 Профиль  
                  
 
 Re: Суммы чисел в доминошках
Сообщение31.12.2016, 16:58 
Аватара пользователя


26/05/12
1534
приходит весна?
Ktina в сообщении #1180930 писал(а):
А вообще, напрашивается вопрос, сколько всего способов?

Ну, перебрать $10! =3`628`800$ вариантов вполне под силу компьютеру. Тем более, что задачу можно переформулировать в матричном виде. Надо составить матрицу $M$, строки которой содержат две единички и отвечают за суммы доминошек. Строк будет 13 штук, а столбцов 10. Эта матрица умножается на искомый столбец комбинаций чисел и в результате должен получаться столбец, в котором все числа различные.

Мне кажется, что вариантов, удовлетворяющих условию задачи, будет довольно много среди всех возможных расстановок.

Матричный вид задачи можно дальнейшим образом модернизовать: составить всевозможные комбинации разностей пар строк, в результате получится новая матрица, в которой 78 строк. Причём интересными являются не все 78 сток, поскольку есть тривиальные сравнения двух перекрывающихся доминошек. Таки строки нужно выкинуть (они не вносят никаких запретов, так как все числа искомой комбинации разные). В каждой строке получившейся матрицы будет две единички со знаком плюс и две единички со знаком минус. При умножении новой матрицы на столбец искомой комбинации должен получиться столбец, не содержащий нулевых элементов. Не смотря на то, что строк в матрице несколько десятков, накладываемое задачей ограничение довольно свободное, именно поэтому мне кажется, что решений будет очень много.

-- 31.12.2016, 18:35 --

Хотя нет, моя интуиция меня подвела. Из $3`628`800$ комбинаций условиям задачи удовлетворяет только $5`048$, то есть чуть меньше $0,14 \%$. Мне казалось будет больше. Кстати, пар неперекрывающихся доминошек имеется $54$.

-- 31.12.2016, 18:42 --

И кстати, не обязательно числа от 5 до 14 расставлять. Вполне можно брать числа от 0 до 9, получатся ровно те же самые комбинации (только все числа будут на 5 меньше).

 Профиль  
                  
 
 Re: Суммы чисел в доминошках
Сообщение31.12.2016, 18:38 
Аватара пользователя


26/05/12
1534
приходит весна?
Попробовал изменить топологию: взял прямоугольник 2 на 5. Получилось $56$ непересекающихся пар доминошек и $5`424$ комбинации расстановок, удовлетворяющих условию задачи (чуть меньше $0,15\%$ от общего числа комбинаций, расстановки, получающиеся симметриями не выкидывал).

-- 31.12.2016, 19:45 --

Если же взять лесенку $4-3-2-1$, то будет $45$ пар доминошек и $22`520$ решений (чуть больше $0,62\%$).

 Профиль  
                  
 
 Re: Суммы чисел в доминошках
Сообщение01.01.2017, 02:49 
Аватара пользователя


01/12/11

8634
B@R5uk
Большое спасибо и с Новым Годом!

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

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



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

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


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

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