2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Головоломка
Сообщение26.01.2008, 17:17 


26/01/08
4
Господа не поможете?

Изображение

 Профиль  
                  
 
 
Сообщение26.01.2008, 20:58 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Переношу из математического раздела в свободный полет

 Профиль  
                  
 
 
Сообщение26.01.2008, 22:23 
Модератор
Аватара пользователя


11/01/06
5660
Напишите в каждой пустой клетке свою переменную $x_i$ и составьте систему уравнений. В этой системе будет 38 уравнений и $n$ неизвестных (влом считать). Выразите какие-то 38 переменных через остальные (предполагаю, что матрица получится максимального ранга), то есть приведите систему к такому матричному виду:
$x = My + c$
где в матрице $M$ и вектор-столбцах $x$ и $c$ 38 строк, а в вектор-столбце $y$ $n-38$ строк и столько же столбцов в $M$. Здесь $x$ и $y$ образуют разбиение множества переменных, а $c$ - свободный член.
Далее можно действовать двумя методами:

либо домножить каждую строку на НОК знаменателей всех входящих в эту строку коэффициентов из $M$ и $c$ и рассмотреть ее по модулю этого НОК. Таким образом, из системы исчезнут $x$ и она превратиться в систему сравнений. Дальше надо попытаться ее решить.

либо можно приписать к $M$ снизу единичную матрицу размером $(n-38)\times(n-38)$, превратив ее в матрицу $M'$ размером $n\times (n-38)$, и в решетке натянутой на $M'$ искать вектор дающий наилучшее приближение к вектору $c'$, полученному из $c$ приписыванием снизу $n-38$ нулей. Здесь есть готовые алгоритмы (LLL).

Могу попробовать порешать, если вы мне дадите все коэффициенты в нормальном численном виде (скажем, в виде массива с нулями вместо отсутствующих коэффициентов).

P.S. А почему эта задача в свободном полете?

 Профиль  
                  
 
 
Сообщение26.01.2008, 22:36 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
maxal писал(а):
P.S. А почему эта задача в свободном полете?


Не разобрался, показалось, что это что-то по типа судоку. Вернем.

 Профиль  
                  
 
 
Сообщение27.01.2008, 00:10 


26/01/08
4
maxal писал(а):
Напишите в каждой пустой клетке свою переменную $x_i$ и составьте систему уравнений. В этой системе будет 38 уравнений и $n$ неизвестных (влом считать). Выразите какие-то 38 переменных через остальные (предполагаю, что матрица получится максимального ранга), то есть приведите систему к такому матричному виду:
$x = My + c$
где в матрице $M$ и вектор-столбцах $x$ и $c$ 38 строк, а в вектор-столбце $y$ $n-38$ строк и столько же столбцов в $M$. Здесь $x$ и $y$ образуют разбиение множества переменных, а $c$ - свободный член.
Далее можно действовать двумя методами:

либо домножить каждую строку на НОК знаменателей всех входящих в эту строку коэффициентов из $M$ и $c$ и рассмотреть ее по модулю этого НОК. Таким образом, из системы исчезнут $x$ и она превратиться в систему сравнений. Дальше надо попытаться ее решить.

либо можно приписать к $M$ снизу единичную матрицу размером $(n-38)\times(n-38)$, превратив ее в матрицу $M'$ размером $n\times (n-38)$, и в решетке натянутой на $M'$ искать вектор дающий наилучшее приближение к вектору $c'$, полученному из $c$ приписыванием снизу $n-38$ нулей. Здесь есть готовые алгоритмы (LLL).

Могу попробовать порешать, если вы мне дадите все коэффициенты в нормальном численном виде (скажем, в виде массива с нулями вместо отсутствующих коэффициентов).

P.S. А почему эта задача в свободном полете?




Большое спасибо за детальный ответ.

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

Насчет этого:

“Могу попробовать порешать, если вы мне дадите все коэффициенты в нормальном численном виде (скажем, в виде массива с нулями вместо отсутствующих коэффициентов).”

Задачка дана в таком виде. Других деталей/условий не предоставлено.

Надеюсь кто-нибудь решит не простую задачку.

Заранее большое спасибо.

 Профиль  
                  
 
 
Сообщение27.01.2008, 00:26 
Модератор
Аватара пользователя


11/01/06
5660
novichok писал(а):
“Могу попробовать порешать, если вы мне дадите все коэффициенты в нормальном численном виде (скажем, в виде массива с нулями вместо отсутствующих коэффициентов).”
Задачка дана в таком виде. Других деталей/условий не предоставлено.

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

 Профиль  
                  
 
 
Сообщение27.01.2008, 00:27 
Экс-модератор
Аватара пользователя


07/10/07
3368
novichok писал(а):
Но к сожалению я в математику не силен. Не могли бы решить эту задачу?

Насчет этого:

“Могу попробовать порешать, если вы мне дадите все коэффициенты в нормальном численном виде (скажем, в виде массива с нулями вместо отсутствующих коэффициентов).”

Задачка дана в таком виде. Других деталей/условий не предоставлено.

Надеюсь кто-нибудь решит не простую задачку.

Странная задача весьма :?
А откуда вы вообще ее взяли и зачем она вам, если не секрет, конечно?

 Профиль  
                  
 
 
Сообщение27.01.2008, 11:59 


26/01/08
4
maxal писал(а):
novichok писал(а):
“Могу попробовать порешать, если вы мне дадите все коэффициенты в нормальном численном виде (скажем, в виде массива с нулями вместо отсутствующих коэффициентов).”
Задачка дана в таком виде. Других деталей/условий не предоставлено.

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


вот вариант в Exсel

скачать

 Профиль  
                  
 
 
Сообщение27.01.2008, 13:21 
Модератор
Аватара пользователя


11/01/06
5660
Правильно ли я понял, что в 147 пустых клеток в верхней таблице нужно вставить те самые 147 чисел, что указаны в нижней таблице, причем все числа должны быть использованы и ровно по одному разу?

Если так, то что-то не так либо с оригинальной задачей, либо с вашим экселевым файлом.

Предположим, что мы их расставили согласно требованию равенства сумм в каждой строке и столбце 19. Тогда сумма всех чисел в заполненной таблице обязана быть равна $19\cdot19=361$. И эта сумма распадается на сумму $S$ тех чисел, что заданы в таблице изначально, и сумму $T$ расставленных нами чисел. Поэтому должно выполняться равенство $S+T=361$.

Но мы можем вычислить $S$ и $T$, даже ничего не расставляя, так как $S$ - это просто сумма всех заданных чисел в первой таблице, а $T$ - это сумма всех 147-ми чисел во второй таблице.

Так вот, из вашего экселевского файла у меня получилось, что $S=-652$ и $T=1376$, что дает $S+T=724\ne 361$.
Поэтому где-то вкралась ошибка. Проверьте еще раз соответствие содержимого вашего файла таблицам на рисунке. И пересчитайте сами эти суммы.

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

 Профиль  
                  
 
 
Сообщение27.01.2008, 14:18 


26/01/08
4
maxal писал(а):
Правильно ли я понял, что в 147 пустых клеток в верхней таблице нужно вставить те самые 147 чисел, что указаны в нижней таблице, причем все числа должны быть использованы и ровно по одному разу?

Если так, то что-то не так либо с оригинальной задачей, либо с вашим экселевым файлом.

Предположим, что мы их расставили согласно требованию равенства сумм в каждой строке и столбце 19. Тогда сумма всех чисел в заполненной таблице обязана быть равна $19\cdot19=361$. И эта сумма распадается на сумму $S$ тех чисел, что заданы в таблице изначально, и сумму $T$ расставленных нами чисел. Поэтому должно выполняться равенство $S+T=361$.

Но мы можем вычислить $S$ и $T$, даже ничего не расставляя, так как $S$ - это просто сумма всех заданных чисел в первой таблице, а $T$ - это сумма всех 147-ми чисел во второй таблице.

Так вот, из вашего экселевского файла у меня получилось, что $S=-652$ и $T=1376$, что дает $S+T=724\ne 361$.
Поэтому где-то вкралась ошибка. Проверьте еще раз соответствие содержимого вашего файла таблицам на рисунке. И пересчитайте сами эти суммы.

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



я спрошу про это, но помоему ошибка в этом числе 129. там два раза использовано 129. надо помоему второй вариант использовать как "-129".

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

 Профиль  
                  
 
 
Сообщение27.01.2008, 20:29 
Модератор
Аватара пользователя


11/01/06
5660
novichok писал(а):
maxal писал(а):
Так вот, из вашего экселевского файла у меня получилось, что $S=-652$ и $T=1376$, что дает $S+T=724\ne 361$.
Поэтому где-то вкралась ошибка. Проверьте еще раз соответствие содержимого вашего файла таблицам на рисунке. И пересчитайте сами эти суммы.

я спрошу про это, но помоему ошибка в этом числе 129. там два раза использовано 129. надо помоему второй вариант использовать как "-129".

Этого недостаточно. Если заменить "129" на "-129", то это изменит значение $T$ на $T'=1118$, но при этом все равно $S+T'=466\ne 361$.

 Профиль  
                  
 
 
Сообщение30.01.2008, 03:58 
Заслуженный участник
Аватара пользователя


17/10/05
3709
PAV писал(а):
maxal писал(а):
P.S. А почему эта задача в свободном полете?


Не разобрался, показалось, что это что-то по типа судоку. Вернем.

А по-моему, в Свободном полёте вполне уместна. Судоку тоже можно решать через матрицы, но это же не повод…

P.S. Внимание! Я загрузил этот файл. В нём какие-то макросы. Это может быть и вирус!

Добавлено спустя 1 час 58 минут 13 секунд:

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

Что-то здесь не то… By the pricking of my thumbs, // Something wicked this way comes

Добавлено спустя 17 минут 24 секунды:

И одна догадка, проливающая свет на природу ошибки (но не на источник): если выписать все числа подряд, они образуют ряд от -179 до 181, где все цифры встречаются ровно однажды, с двумя искючениями: (1) отсутствует -105, и (2) 0 встречается дважды.

Отсюда два вывода: (1) с наибольшей вероятностью имеется один из 0 — это -105 (и тогда суммы сойдутся); (2) нам дан частично заполненный магический квадрат, в котором (с точностью до смещения на -180) надо вписать числа от 1 до 361, так чтобы получился магический квадрат.

 Профиль  
                  
 
 
Сообщение01.02.2008, 04:29 
Модератор
Аватара пользователя


11/01/06
5660
Догадка насчет магического квадрата скорее всего верна, только вот непонятно почему он неполный (про равенство сумм диагоналей не сказано ни слова). И зачем такой квадрат может понадобиться? Разве что это какое-то соревнование. Автор топика еще куда-то пропал. Сплошные странности :lol:

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

Изображение

 Профиль  
                  
 
 
Сообщение06.03.2008, 14:58 
Аватара пользователя


26/02/06
36
из романов средневековой Франции
Какая же это головоломка, если всё упирается в написание маааленькой программки?!

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


17/10/05
3709
:evil:
Max Godsie писал(а):
Какая же это головоломка, если всё упирается в написание маааленькой программки?!

Которая долго-долго работает :)

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

Модератор: Модераторы



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

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


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

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