Задача о математическом сейфе на матрицах

Рассматривается задача о математическом сейфе, заданная на матрице. Исследуется сейф с однотипными замками. Находятся необходимые условия существования решения задачи для простого числа состояний замков. Розглядається задача про математичний сейф, заданий на матриці. Досліджується сейф з однотиповим...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Теорія оптимальних рішень
Datum:	2013
Hauptverfasser:	Якуб, А.Г., Донец, Г.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/85054
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Задача о математическом сейфе на матрицах / А.Г. Якуб, Г.А. Донец // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 124-130. — Бібліогр.: 3 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-85054
record_format	dspace
spelling	Якуб, А.Г. Донец, Г.А. 2015-07-18T17:09:18Z 2015-07-18T17:09:18Z 2013 Задача о математическом сейфе на матрицах / А.Г. Якуб, Г.А. Донец // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 124-130. — Бібліогр.: 3 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/85054 519.8 Рассматривается задача о математическом сейфе, заданная на матрице. Исследуется сейф с однотипными замками. Находятся необходимые условия существования решения задачи для простого числа состояний замков. Розглядається задача про математичний сейф, заданий на матриці. Досліджується сейф з однотиповими замками. Знаходяться умови існування розв’язку задачі для простого числа станів замків. The task about the mathematical safe, set on a matrix is considered. The safe with the same type of locks is researched. We have found the necessary conditions of the solution of the task for a prime number of states of the lock. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Задача о математическом сейфе на матрицах Задача про математичний сейф на матрицях The task about the mathematical safe on matrices Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Задача о математическом сейфе на матрицах
spellingShingle	Задача о математическом сейфе на матрицах Якуб, А.Г. Донец, Г.А.
title_short	Задача о математическом сейфе на матрицах
title_full	Задача о математическом сейфе на матрицах
title_fullStr	Задача о математическом сейфе на матрицах
title_full_unstemmed	Задача о математическом сейфе на матрицах
title_sort	задача о математическом сейфе на матрицах
author	Якуб, А.Г. Донец, Г.А.
author_facet	Якуб, А.Г. Донец, Г.А.
publishDate	2013
language	Russian
container_title	Теорія оптимальних рішень
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Задача про математичний сейф на матрицях The task about the mathematical safe on matrices
description	Рассматривается задача о математическом сейфе, заданная на матрице. Исследуется сейф с однотипными замками. Находятся необходимые условия существования решения задачи для простого числа состояний замков. Розглядається задача про математичний сейф, заданий на матриці. Досліджується сейф з однотиповими замками. Знаходяться умови існування розв’язку задачі для простого числа станів замків. The task about the mathematical safe, set on a matrix is considered. The safe with the same type of locks is researched. We have found the necessary conditions of the solution of the task for a prime number of states of the lock.
issn	XXXX-0013
url	https://nasplib.isofts.kiev.ua/handle/123456789/85054
citation_txt	Задача о математическом сейфе на матрицах / А.Г. Якуб, Г.А. Донец // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 124-130. — Бібліогр.: 3 назв. — рос.
work_keys_str_mv	AT âkubag zadačaomatematičeskomseifenamatricah AT donecga zadačaomatematičeskomseifenamatricah AT âkubag zadačapromatematičniiseifnamatricâh AT donecga zadačapromatematičniiseifnamatricâh AT âkubag thetaskaboutthemathematicalsafeonmatrices AT donecga thetaskaboutthemathematicalsafeonmatrices
first_indexed	2025-11-24T03:48:43Z
last_indexed	2025-11-24T03:48:43Z
_version_	1850841213414932480
fulltext	124 Теорія оптимальних рішень. 2013 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается задача о мате- матическом сейфе, заданная на матрице. Исследуется сейф с однотипными замками. Находят- ся необходимые условия сущест- вования решения задачи для прос- того числа состояний замков.  Агаи Аг Гамиш Якуб, Г.А. Донец, 2013 ÓÄÊ 519.8 ÓÄÊ 519.8 ÀÃÀÈ ÀÃ ÃÀÌÈØ ßÊÓÁ, Ã.À. ÄÎÍÅÖ ÇÀÄÀ×À Î ÌÀÒÅÌÀÒÈ×ÅÑÊÎÌ ÑÅÉÔÅ ÍÀ ÌÀÒÐÈÖÀÕ В работах [1, 2] дано общее определение математического сейфа, и изучались сейфы, заданные на графах, ориентированных или неориентированных. Из общего определения математического сейфа следует, что любой из них можно задать с помощью матрицы смежностей некоторого графа. Однако суще- ствуют математические сейфы со своей спе- цификой, позволяющей их задавать с помо- щью матриц. Существует реальная интерпретация зада- чи: на двери сейфа расположены в виде мат- рицы скважины одинаковых замков. Извест- ны состояния каждого замка – он открыт или закрыт. Если вставить ключ в одну из сква- жин и сделать один поворот, то такой же по- ворот будет сделан и во всех замках той же строки и того же столбца. Необходимо найти такую последовательность замочных сква- жин, чтобы поворотами в них ключа открыть сейф. Это произойдет при всех открытых замках. Рассмотрим в общем случае сейф, определенный в [2], у которого все замки расположены в виде прямоугольной таблицы размером m n× . Для нее mnN = , ( ) ( )1 1, 2, ..., ; 1, 2, ..., .l n i j i m j n= − + = = Обозначим lZ – множество замков, объеди- няющее замки i-й строки и j-го столбца, и пусть все замки имеют произвольное число состояний и принадлежат одному типу, т. е. .lk K= Любому начальному состоянию сейфа b r соответствует матрица ,( ) ij m n B b= , ЗАДАЧА О МАТЕМАТИЧЕСКОМ СЕЙФЕ НА МАТРИЦАХ Теорія оптимальних рішень. 2013 125 где { }0,1,..., 1ijb K∈ − . Необходимо найти такую последовательность замков и соответствующее количество поворотов в них, чтобы «открыть сейф», т. е. пе- рейти в состояние сейфа ,( 0) fin ij m n B b= = . Пусть nmijxX ,)(= – решение задачи, где ijx равно числу поворотов ключа в замке lz . Тогда условием того, что эле- мент ijb преобразуется матрицей X в нуль, представляется соотношением )(mod0 11 Kbxx ij m ik k kj n k ik ≡++∑∑ ≠ == , где 1, 2, ..., ; 1, 2, ..., .i m j n= = (1) Обозначим ( )11 12 1 21 22 2 , 1, ,......., , , ,....., ,....., , n n m n mn x x x x x x x x x−= r вектор- столбец, полученный из матрицы X последовательной записью ее строк. Аналогично из матрицы В получим вектор-столбец b r . Кроме того, пусть nℑ – матрица размера n×n, состоящая из единиц, nE – единичная матрица того же размера, а nI – вектор-строка из n единиц. Тогда условие преобразования (1) для всей матрицы В запишем в виде системы уравнений ( )KbxA mod vr ≡ , (2) где матрица А размера mn× mn состоит из 2 m клеток:                 ℑ ℑ ℑ ℑ = nnnn nnnn nnnn nnnn EEE EEE EEE EEE A .... ............ .... .... .... . (3) Эту задачу легко можно свести к решению системы линейных диофантовых уравнений, если добавить в правые части (2) слагаемые ( ), 1, 2,...,iKy i mn= , ис- пользуя известные методы. Однако специфика задачи позволяет находить ее реше- ние непосредственно, так как матрица А имеет стандартный вид и не зависит от зна- чений матрицы В. Ее ранг и определитель зависят только от значений m и n. Поскольку матрица А симметрическая, то в дальнейшем все рассуждения относительно строк матрицы справедливы и для одноименных столбцов и строк и наоборот. Если ранг матрицы A равен mn, то решение системы (2) имеет вид )(mod1 KbAx rr −−= . (4) Таким образом, проблема сводится к отысканию обратной матрицы 1.A − АГАИ АГ ГАМИШ ЯКУБ, Г.А. ДОНЕЦ 126 Теорія оптимальних рішень. 2013 В зависимости от конкретных значений m, n и K возникают различные по сложности решения задачи. Их можно разделить на три таких вида в зависимо- сти от типа замков: 1) замки с двумя состояниями; 2) однотипные замки с про- извольным числом состояний; 3) произвольные замки. Решение задачи для замков с двумя состояниями в полном объеме получено в [3]. Здесь исследуется второй случай. Если K > 2, то проблема нахождения обратной матрицы наталкивается на ряд существенных препятствий. Исследуем сначала вопрос о ее структуре. Рассмотрим симметричную квадратную матрицу порядка n, зависящую от двух параметров ( ) ( ) nnn EH ℑβ+β−α=βα, .                 αβββ βαββ ββαβ βββα =βα ... ............... ... ... ... ),(nH . (5) Используем ее для построения квадратной матрицы порядка mn, зависящей от четырех параметров и состоящей из 2 m подматриц ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) , , , . . . , , , . . . , ( , , , ) . . . . . . . . . . . . . . . . . . . . . . . . . . . , , . . . , n n n n n n m n n n n H H H H H H T H H H α β γ δ γ δ    γ δ α β γ δ α β γ δ =     γ δ γ δ α β  . (6) Матрицы такого типа будем называть T-матрицами. В этих обозначениях единичная матрица и матрица A также являются T-матрицами, а именно ( ), 1, 0, 0, 0mn m nE T= , а ( )1, 1, 1, 0mnA T= . Если можно вместо элементов подставлять подматрицы, то T-матрицы можно представлять в виде ( )),(),,(, δγβα= nnmnm HHHT . Лемма 1. Результатом умножения двух T-матриц будет также T-матрица. Для доказательства рассмотрим две T-матрицы ),,,( 4321, ααααnmT , ),,,( 4321, ββββnmT и перемножим их. Ввиду симметричности матриц элементами ij c матрицы C, полученной в результате их умножения, будут равны скалярному произведению i-й строки первой и j-й строки второй матриц. В зависимости от значений i и j эти произведения можно разбить на 4 группы. ЗАДАЧА О МАТЕМАТИЧЕСКОМ СЕЙФЕ НА МАТРИЦАХ Теорія оптимальних рішень. 2013 127 а) i = j. Тогда получаются диагональные элементы матрицы C ( ) ( ) ( ) ( )1 1 2 2 3 3 4 41 1 1 1 .iic n m m n= α β + − α β + − α β + − − α β (7) Очевидно, что таких элементов ровно mn. б) ji ≠ ; 0,)1(,1 ≥+≤≤+ knkjikn . В результате получаются неди- агональные элементы типа β диагональных подматриц ( )βα,nH . ( ) ( ) ( ) ( ) ( )1 2 2 1 2 2 3 4 4 3 4 42 1 1 1ijc n m m n= α β + α β + − α β + − α β + α β + − − α β . (8) Для фиксированного k таких элементов будет n(n–1), а всего mn (n – 1). в) jinji ≠≡− ),(mod0 . В результате получаются диагональные элементы типа γ подматриц ( )δγ,nH ( ) ( ) ( ) ( ) ( )1 3 3 1 2 4 4 2 3 3 4 41 2 2 1ijc n m m n= α β + α β + − α β + α β + − α β + − − α β . (9) Каждой строке первой матрицы соответствует (m – 1) строка второй матри- цы, поэтому таких элементов будет mn (m – 1). г) 0,0,,)1(1,)1(1),(mod ≥≥≠+≤≤++≤≤+≠ lklknljnlnkiknnji . В результате получаются недиагональные элементы типа δ подматриц ( )δγ,nH ( ) ( )1 4 4 1 2 3 3 2 2 4 4 22ijc n= α β + α β + α β + α β + − α β + α β + ( ) ( ) ( ) ( )3 4 4 3 4 42 2 2m m n+ − α β + α β + − − α β . (10) Если зафиксировать одну строку первой матрицы, то ей будут соответство- вать 1−n строк в 1−m подматрицах второй матрицы, т. е. будет ( ) ( )1 1mn m n− − элементов. Если просуммировать число элементов этих че- тырех групп, то получим число 2 2 m n . Это означает, что в результате умножения других элементов не образуется, что и доказывает справедливость леммы. Будем искать обратную матрицу 1A− системы (2) в виде T-матрицы ( )4321, 1 ,,, αααα=− nmTA . Так как mnEAA =−1 , то подставляя соответствующие значения в (7 – 10), получаем систему уравнений ( ) 1 2 3 1 2 4 1 3 4 2 3 4 ( 1) ( 1) 1 ( 1) ( 1) 0 (mod ) ( 1) ( 1) 0 3 0 n m n m K m n m n α + − α + − α ≡  α + − α + + − α ≡   α + + − α + − α ≡  + α + α + + − α ≡  . (11) АГАИ АГ ГАМИШ ЯКУБ, Г.А. ДОНЕЦ 128 Теорія оптимальних рішень. 2013 Матрица этой системы имеет вид             −+ −− −− −− = 3110 1101 1011 0111 nm nm mn mn S . (12) Нетрудно подсчитать, что ))(mod1)(1)(1(det KnmnmS −+−−−≡ . Отсюда получаем необходимое условие разрешимости системы (2): )(mod1);(mod1);(mod1 KnmknKm ≠+≠≠ . (13) В дальнейшем будем часто использовать дробные выражения типа p/q, под которыми подразумеваются целое число t, являющееся корнем (если он сущест- вует) уравнения )(mod Kpqt ≡ . (14) В результате решения системы (12) получаются следующие значения корней: ( ) [ ] [ ] ( ) )(mod det2 ,det)3(32 ,det32)3( ,det21 4 3 2 2 1 K Snm Snmnm Snnmm Snm        −+≡α −+−−≡α −+−+−≡α −+−−≡α . В результате упрощений получаем окончательно )(mod 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 43 42 41 K nmmn m n nm             −+       − + − −≡α α+ − ≡α α+ − ≡α α+− − + − ≡α . (15) Пример 1. Пусть K = 7, n = 4, m = 3, а матрица (вектор) начального состояния сейфа ( ) 0 3 1 0 5 6 0 2 ; 0, 3, 1, 0, 5, 6, 0, 1, 3, 3, 5,1 . 3 3 5 1 T B b    = =      r ЗАДАЧА О МАТЕМАТИЧЕСКОМ СЕЙФЕ НА МАТРИЦАХ Теорія оптимальних рішень. 2013 129 Матрица A имеет вид                                       = 111110001000 111101000100 111100100010 111100010001 100011111000 010011110100 001011110010 000111110001 100010001111 010001001111 001000101111 000100011111 A . Вычислим дробные значения: ).7(mod6),7(mod 6 1 1 1 );7(mod5),7(mod 3 1 1 1 );7(mod4),7(mod 2 1 1 1 33 22 11 ≡≡= −+ ≡≡= − ≡≡= − tt nm tt n tt m Вычислим по (15) элементы обратной матрицы: ( ) ).7(mod624);7(mod025 );7(mod32154);7(mod2654 32 14 ≡+=α≡+=α ≡+−+=α≡⋅+−=α Отсюда обратная матрица                                       =− 300062226222 030026222622 003022622262 000322262226 622230006222 262203002622 226200302262 222600032226 622262223000 262226220300 226222620030 222622260003 1 A . АГАИ АГ ГАМИШ ЯКУБ, Г.А. ДОНЕЦ 130 Теорія оптимальних рішень. 2013 ( ) ( )1 2, 3, 4,1, 4, 3, 0, 0, 0, 5, 3, 4 ; T T x A b −= − ≡ rr 2 3 4 1 4 3 0 0 0 5 3 4 X    = ⋅      Матрица X определяет количество поворотов ключа для каждого замка сейфа, которые приведут к открытию сейфа. Рассмотрим эту последовательность преоб- разований матрицы B, в которой очередной элемент (замок) преобразования, а также соответствующие строка и столбец выделены параллельными линиями. 2 3 4 1 4 3 5 0 3 1 0 2 5 3 2 5 1 6 5 5 6 0 2 0 6 0 2 0 2 0 2 3 3 5 1 5 3 5 1 5 6 5 1 2 5 3 2 3 6 4 3 0 6 4 3 0 2 4 2 0 2 4 3 4 6 1 0 5 6 2 1 5 6 2 2 2 6 2 2 0 2 4 3 0 0 4 3 0 2 4 3 0 0 4 3 2 2 2 2 0 0 0 0 B + + + + + + +             = → → →                              → → → →                         → →           3 3 0 0 0 3 0 0 0 0 0 0 0 3 0 0 0 0 . 3 3 3 3 0 0 0 0 finB + −        → → =           Агаі Аг Гаміш Якуб, Г.О. Донець ЗАДАЧА ПРО МАТЕМАТИЧНИЙ СЕЙФ НА МАТРИЦЯХ Розглядається задача про математичний сейф, заданий на матриці. Досліджується сейф з однотиповими замками. Знаходяться умови існування розв’язку задачі для простого числа станів замків. Aghaei Agh Ghamish Yaghoub, G.A. Donets THE TASK ABOUT THE MATHEMATICAL SAFE ON MATRICES The task about the mathematical safe, set on a matrix is considered. The safe with the same type of locks is researched. We have found the necessary conditions of the solution of the task for a prime number of states of the lock. 1. Донец Г.А., Чжан Бинь. Постановка и решение некоторых задач о математическом сейфе // Кибернетика и системный анализ.– 2006. – № 3. – С. 3 –14. 2. Донец Г.А., Чжан Бинь. Задачи о математическом сейфе на графах // Кибернетика и системный анализ. – 2006. – № 5. – С. 84 –93. 3. Донец Г.А. Решение задачи о сейфе на (0,1)-матрицах // Кибернетика и системный анализ. – 2002. – № 1. – С. 98 –105. Получено 03.04.2013

Задача о математическом сейфе на матрицах

Institution

Ähnliche Einträge