2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 23, 24, 25, 26, 27, 28, 29 ... 192  След.
 
 
Сообщение23.12.2008, 17:21 


11/05/06
363
Киев/Севастополь
Aleks-Sid
Потому что $\Theta(n^2)$ растет быстрее, чем $\Theta(n)$

 Профиль  
                  
 
 
Сообщение23.12.2008, 22:14 
Заблокирован


31/10/08

115
Австралия
MaximKat

Цитата:
Потому что $\Theta(n^2)$ растет быстрее, чем $\Theta(n)$

А разве не потому что деревья падают медленней?

 Профиль  
                  
 
 
Сообщение23.12.2008, 22:40 


11/05/06
363
Киев/Севастополь
Aleks-Sid писал(а):
А разве не потому что деревья падают медленней?
Ценю юмор.
Количество неизвестных в магическом квадрате пропорционально $n^2$. Количество уравнений пропрционально $n$. При достаточно больших $n$ первое больше второго и система разрешима. При $n=3$ система переопределена и решения нет.
Еще пояснения нужны?

 Профиль  
                  
 
 
Сообщение23.12.2008, 23:03 
Заблокирован


31/10/08

115
Австралия
MaximKat

Непонятен только один момент (я слаб в математических абстракциях) - почему при n=4 система не переопределена? Где критерий переопределенности?
Я подсчитал - число уравнений для n=3 равно 16 . Это условия пандиагональности и ассоциативности. Количество неизвестных 9. Для n=4 соответственно имеем 25 уравнений и 16 неизвестных. То есть качественно все одно и то же!

 Профиль  
                  
 
 
Сообщение23.12.2008, 23:34 


11/05/06
363
Киев/Севастополь
Точный критерий дать нельзя в общем виде, потому что часть уравнений могут быть эквивалентными, а значит могут быть исключены из системы. Надо писать конкретную систему и смотреть.

 Профиль  
                  
 
 
Сообщение23.12.2008, 23:37 
Заблокирован


31/10/08

115
Австралия
Вот я конкретно и рассмотрел. Все одинаково для двух случаев, но второй имеет решение, а первый почему-то должен артачиться.

P.S. В каждом из двух случаев эквивалентных уравнений не оказалось.

 Профиль  
                  
 
 
Сообщение24.12.2008, 02:27 


11/05/06
363
Киев/Севастополь
Aleks-Sid в сообщении #170582 писал(а):
P.S. В каждом из двух случаев эквивалентных уравнений не оказалось.
Предъявите 25 линейно независимых уравнений для n=4, пожалуйста

 Профиль  
                  
 
 
Сообщение24.12.2008, 04:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Коллеги, я не понимаю, о чём спор.
Система линейных уравнений, описывающая идеальный магический квадрат 4-го порядка, приведена в моей статье “Ассоциативные магические квадраты”.
Эта система имеет решение только с повторяющимися числами. Так сказал Maple.
Система линейных уравнений, описывающая идеальный квадрат 3-го порядка, содержит всего 4 неизвестных и 4 уравнения (не забывайте, что квадрат у нас идеальный, а значит ассоциативный). Вот эти уравнения:
x1 + x2 + x3 = S

x4 = S/3

2x1 – x2 – x3 = 0

2x3 – x1 – x2 = 0
(x1, x2, x3 – числа в первой строке квадрата, x4 – число в центральной ячейке этого квадрата).
Первые два уравнения – это условия ассоциативности, последние два уравнения – это условия пандиагональности. Если рассматривать только первые два уравнения, то будет бесконечно много решений (как с разными, так и с повторяющимися значениями неизвестных), так как ассоциативных (но не пандиагональных!) магических квадратов бесконечно много, традиционных – 8 вариантов, и бесконечно много нетрадиционных. Традиционные магические квадраты 3х3 (8 вариантов) всем известны. Вот пример решения для нетрадиционного квадрата:
Код:
10 17 27
35 18 1
9 19 26

Или вот ещё знаменитый квадрат Дьюдени, составленный из простых чисел:
Код:
67 1 43
13 37 61
31 73 7

(другие примеры нетрадиционных квадратов 3-го порядка вы можете посмотреть здесь или с успехом составить сами, руководствуясь первыми двумя уравнениями приведённой выше системы уравнений).
По этому пункту есть возражения?
Теперь рассматриваем систему в целом, то есть все 4 уравнения, а значит, требуем от квадрата пандиагональности. И вот тут система имеет… тоже бесконечно много решений, но во всех этих решениях все 4 неизвестных принимают одинаковые значения.
Найдите ошибку в моём доказательстве :roll:

 Профиль  
                  
 
 
Сообщение24.12.2008, 08:24 
Модератор
Аватара пользователя


11/01/06
5710
Aleks-Sid в сообщении #170560 писал(а):
Я подсчитал - число уравнений для n=3 равно 16 . Это условия пандиагональности и ассоциативности. Количество неизвестных 9. Для n=4 соответственно имеем 25 уравнений и 16 неизвестных.

Более обще: для квадрата $n\times n$ имеем по $n$ уравнений для горизонталей и вертикалей, $\lceil n^2/2\rceil$ уравнений для ассоциативности и $2n$ уравнений для разломанных диагоналей. Суммарно $4n + \lceil n^2/2\rceil$ уравнений.
MaximKat в сообщении #170543 писал(а):
Количество неизвестных в магическом квадрате пропорционально $n^2$. Количество уравнений пропрционально $n$. При достаточно больших $n$ первое больше второго и система разрешима.

Вы забываете, что нужно абы какое решение, а лишь такое, которое в точности состоит из чисел от 1 до $n^2$. А оно не факт, что существует, даже если система недоопределена.
И, кстати, в "лобовой" системе количество уравнений также пропорционально $n^2$ (см. выше), но вот если по ассоциативности исключить половину неизвестных, то в системе действительно останется $\lfloor n^2/2\rfloor$ неизвестных и лишь $4n$ уравнений.

 Профиль  
                  
 
 
Сообщение24.12.2008, 09:04 
Заблокирован


31/10/08

115
Австралия
Коллеги! Вы все говорите вокруг да около. А мне важно знать одно: существует ли нетрадиционный идеальный МК 3х3? Пусть там хоть 7 чисел будут одинаковые! И если такого нет, то дать четкое объяснение, почему это невозможно. Только не так голословно, как это сделал MaximKat. Да еще вопрос задал:
Цитата:
Еще пояснения нужны?

MaximKat
Если быть точным, то для 4х4 всего 23 уравнения а не 25. Это досадная ночная опечатка. Но суть от этого не меняется. Вот они передо мной на листе написаны. Если у Вас сомнения, то сами составьте, и если я неправ, то скажите мне: какие из них эквивалентные. Заодно и сами для себя проясните задачу.
Nataly-Mak
По ссылкам прошелся, но идеального нетрадиционного 3х3 не обнаружил.
maxal
Число уравнений для пандиагонального квадрата 4n-1. Доказывать не буду, так как это элементарно. Число уравнений по критерию ассоциативности: n^2/2 для четных n, и n^2/2+1 - для нечетных (в центральной ячейке должно быть число, равное половине суммы 1+n^2)

 Профиль  
                  
 
 
Сообщение24.12.2008, 09:41 
Модератор
Аватара пользователя


11/01/06
5710
Aleks-Sid в сообщении #170690 писал(а):
А мне важно знать одно: существует ли нетрадиционный идеальный МК 3х3? Пусть там хоть 7 чисел будут одинаковые! И если такого нет, то дать четкое объяснение, почему это невозможно.

Вам уже сказали, что нет. Так как соответствующая система уравнений имеет решением только наборы чисел, в которых все числа равны между собой.
Aleks-Sid в сообщении #170690 писал(а):
Число уравнений для пандиагонального квадрата 4n-1. Доказывать не буду, так как это элементарно.

Это зависит от того, как вы определяете уравнения. Некоторые из уравнений можно сразу исключить, так как они очевидным образом являются следствием остальных, тогда уравнений будет еще меньше уравнений. Но если не заниматься ручным исключением, то для пандиагонального квадрата количество уравнений равно $4n$.

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

Aleks-Sid в сообщении #170690 писал(а):
Доказывать не буду, так как это элементарно. Число уравнений по критерию ассоциативности: n^2/2 для четных n, и n^2/2+1 - для нечетных

Ну так это в точности и есть $\lceil n^2/2\rceil$, как у меня и написано выше.

 Профиль  
                  
 
 
Сообщение24.12.2008, 09:51 
Заблокирован


31/10/08

115
Австралия
Итак, получается, что с точки зрения идеального магического квадрата, 3 х 3 эквивалентен 1 х 1 и не относится к группе n x n где n>3.
Почему такая особенность с точки зрения математической логики?

 Профиль  
                  
 
 
Сообщение24.12.2008, 09:52 
Модератор
Аватара пользователя


11/01/06
5710
Ради интереса посчитал ранги систем уравнений (то есть, по сути максимальное количество линейно независимых уравнений в системе) описывающих нетрадиционные идеальные квадраты. Для $n$ от 1 до 10 они получились равны:
1, 4, 9, 14, 21, 28, 37, 46, 57, 68
В это же время число неизвестных (включая магическую константу) равно $n^2+1$:
2, 5, 10, 17, 26, 37, 50, 65, 82, 101

Нетрудно понять, что система уравнений в данном случае всегда имеет семейство решений (размерности 1), где все элементы квадрата равны между собой. Поэтому, если ранг системы лишь на единицу меньше числа неизвестных, то ее решение в точности состоит из этого тривиального семейства, и других решений нет. Эту ситуацию мы наблюдаем для $n=1, 2$ и $3$. Для больших значений $n$ разность между числом неизвестных и рангов превышает 1, и поэтому найдется по крайней мере нетрадиционный идеальный магический квадрат, в котором не все элементы равны между собой (другими словами, есть по крайней мере два неравных элемента).

 Профиль  
                  
 
 
Сообщение24.12.2008, 10:00 
Заблокирован


31/10/08

115
Австралия
maxal

О! Вот это объяснение! Теперь все встало на свои места! Ваше имя навеки отпечатается в моей книге, как Евклид отпечатался в своих "Началах" :)

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


11/01/06
5710
maxal в сообщении #170702 писал(а):
Ради интереса посчитал ранги систем уравнений (то есть, по сути максимальное количество линейно независимых уравнений в системе) описывающих нетрадиционные идеальные квадраты. Для $n$ от 1 до 10 они получились равны:
1, 4, 9, 14, 21, 28, 37, 46, 57, 68

Для рангов справедлива формула:
$$\left\lfloor\frac{n^2 + 4n - 3}{2}\right\rfloor$$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2876 ]  На страницу Пред.  1 ... 23, 24, 25, 26, 27, 28, 29 ... 192  След.

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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