Н. Макарова

 

ПОСТРОЕНИЕ ПАР ОДЛК 22-го ПОРЯДКА

 

 

Данная страница является продолжением страницы

http://www.natalimak1.narod.ru/diagon.htm

 

 

В указанной выше статье были построены пары ортогональных диагональных латинских квадратов (ОДЛК) порядков 14, 15 и 18. Для порядка 15 построена даже целая группа из четырёх попарно ортогональных диагональных латинских квадратов. Для порядков 14 и 18 построена не одна пара ОДЛК, а целая группа неизоморфных пар; для порядка 14 в этой группе 1152 пары, а для порядка 18 – 2880 пар. Это краткое изложение результатов предыдущей статьи. Здесь будет рассказано о построении группы неизоморфных пар ОДЛК 22-го порядка, состоящей из 576 пар. Эта группа построена на основе одной пары ОЛК, которая найдена мной в статье “The Existence of N2 Resolvable Latin Squares” (A. J. Wolfe, A. C. H. Ling, J. H. Dinitz. 2008). В статье приведена квази-разностная матрица (КРМ) для построения пары ОЛК. Покажу сначала эту КРМ (рис. 1).

 

a

0

2

13

b

5

1

13

c

3

0

9

d

5

1

3

11

11

0

1

3

12

0

7

4

0

8

a

0

1

6

b

0

2

6

c

5

1

2

d

4

0

5

1

4

3

12

5

1

2

0

0

1

2

a

9

0

14

b

1

3

0

c

1

7

0

d

7

0

10

0

9

4

6

5

0

2

3

3

17

8

a

10

0

2

b

15

5

12

c

13

3

1

d

1

0

9

4

0

17

4

0

0

10

 

Рис. 1

 

Читатели могут сами построить пару ОЛК по данной КРМ. Я построила несколько другую пару ОЛК изоморфную паре из статьи. В моей паре ОЛК оба латинских квадрата начинаются с числа 0. Для преобразования латинских квадратов я применила трансформацию тождественной перестановки чисел, являющуюся циклическим сдвигом. И КРМ своей пары я записываю в виде, предложенном мной в предыдущих статьях. На рис. 2 вы видите эту КРМ.

 

 

a

b

c

d

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

a

b

c

d

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

8

9

12

2

17

6

12

10

0

2

5

d

15

c

11

3

14

16

7

9

4

8

13

1

a

b

3

12

17

1

7

3

10

6

0

12

11

8

17

2

a

b

15

5

c

13

16

1

4

d

14

9

 

Рис. 2

 

Понятно, что латинские квадраты пары ОЛК, определяемой данной КРМ, содержат латинский подквадрат 4х4; он задаётся символьными элементами a, b, c, d, которые принимают значения 18, 19, 20, 21 в любой комбинации. На рис. 3 – 4 показаны латинские квадраты пары ОЛК, определяемой данной КРМ. В квадратах символьные элементы заменены конкретными числовыми значениями: a = 18, b = 19, c = 20, d = 21.

 

Первый латинский квадрат

 

0

19

18

4

17

13

10

16

15

7

6

14

5

20

11

21

3

1

8

9

12

2

2

1

19

18

5

0

14

11

17

16

8

7

15

6

20

12

21

4

9

10

13

3

5

3

2

19

18

6

1

15

12

0

17

9

8

16

7

20

13

21

10

11

14

4

21

6

4

3

19

18

7

2

16

13

1

0

10

9

17

8

20

14

11

12

15

5

15

21

7

5

4

19

18

8

3

17

14

2

1

11

10

0

9

20

12

13

16

6

20

16

21

8

6

5

19

18

9

4

0

15

3

2

12

11

1

10

13

14

17

7

11

20

17

21

9

7

6

19

18

10

5

1

16

4

3

13

12

2

14

15

0

8

3

12

20

0

21

10

8

7

19

18

11

6

2

17

5

4

14

13

15

16

1

9

14

4

13

20

1

21

11

9

8

19

18

12

7

3

0

6

5

15

16

17

2

10

16

15

5

14

20

2

21

12

10

9

19

18

13

8

4

1

7

6

17

0

3

11

7

17

16

6

15

20

3

21

13

11

10

19

18

14

9

5

2

8

0

1

4

12

9

8

0

17

7

16

20

4

21

14

12

11

19

18

15

10

6

3

1

2

5

13

4

10

9

1

0

8

17

20

5

21

15

13

12

19

18

16

11

7

2

3

6

14

8

5

11

10

2

1

9

0

20

6

21

16

14

13

19

18

17

12

3

4

7

15

13

9

6

12

11

3

2

10

1

20

7

21

17

15

14

19

18

0

4

5

8

16

1

14

10

7

13

12

4

3

11

2

20

8

21

0

16

15

19

18

5

6

9

17

18

2

15

11

8

14

13

5

4

12

3

20

9

21

1

17

16

19

6

7

10

0

19

18

3

16

12

9

15

14

6

5

13

4

20

10

21

2

0

17

7

8

11

1

17

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

18

19

20

21

6

7

8

9

10

11

12

13

14

15

16

17

0

1

2

3

4

5

21

20

19

18

12

13

14

15

16

17

0

1

2

3

4

5

6

7

8

9

10

11

19

18

21

20

10

11

12

13

14

15

16

17

0

1

2

3

4

5

6

7

8

9

20

21

18

19

 

Рис. 3

 

Второй латинский квадрат:

 

0

10

16

21

8

6

4

2

20

14

7

19

18

15

13

5

9

11

3

12

17

1

12

1

11

17

21

9

7

5

3

20

15

8

19

18

16

14

6

10

4

13

0

2

11

13

2

12

0

21

10

8

6

4

20

16

9

19

18

17

15

7

5

14

1

3

8

12

14

3

13

1

21

11

9

7

5

20

17

10

19

18

0

16

6

15

2

4

17

9

13

15

4

14

2

21

12

10

8

6

20

0

11

19

18

1

7

16

3

5

2

0

10

14

16

5

15

3

21

13

11

9

7

20

1

12

19

18

8

17

4

6

18

3

1

11

15

17

6

16

4

21

14

12

10

8

20

2

13

19

9

0

5

7

19

18

4

2

12

16

0

7

17

5

21

15

13

11

9

20

3

14

10

1

6

8

15

19

18

5

3

13

17

1

8

0

6

21

16

14

12

10

20

4

11

2

7

9

5

16

19

18

6

4

14

0

2

9

1

7

21

17

15

13

11

20

12

3

8

10

20

6

17

19

18

7

5

15

1

3

10

2

8

21

0

16

14

12

13

4

9

11

13

20

7

0

19

18

8

6

16

2

4

11

3

9

21

1

17

15

14

5

10

12

16

14

20

8

1

19

18

9

7

17

3

5

12

4

10

21

2

0

15

6

11

13

1

17

15

20

9

2

19

18

10

8

0

4

6

13

5

11

21

3

16

7

12

14

4

2

0

16

20

10

3

19

18

11

9

1

5

7

14

6

12

21

17

8

13

15

21

5

3

1

17

20

11

4

19

18

12

10

2

6

8

15

7

13

0

9

14

16

14

21

6

4

2

0

20

12

5

19

18

13

11

3

7

9

16

8

1

10

15

17

9

15

21

7

5

3

1

20

13

6

19

18

14

12

4

8

10

17

2

11

16

0

7

8

9

10

11

12

13

14

15

16

17

0

1

2

3

4

5

6

18

19

20

21

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

0

1

2

20

21

18

19

10

11

12

13

14

15

16

17

0

1

2

3

4

5

6

7

8

9

21

20

19

18

6

7

8

9

10

11

12

13

14

15

16

17

0

1

2

3

4

5

19

18

21

20

 

Рис. 4

 

Заметьте: в обоих латинских квадратах неправильная только одна диагональ, а в другой диагонали все элементы различны. А теперь превращаем эти ортогональные латинские квадраты в диагональные ортогональные латинские квадраты тем же методом, который описан в предыдущей статье. На рис. 5 – 6 вы видите пару ОДЛК, полученную из данной пары ОЛК.

 

Первый диагональный латинский квадрат:

 

0

19

18

4

17

13

10

16

15

8

9

12

2

1

3

21

11

20

5

14

6

7

2

1

19

18

5

0

14

11

17

9

10

13

3

4

21

12

20

6

15

7

8

16

5

3

2

19

18

6

1

15

12

10

11

14

4

21

13

20

7

16

8

9

17

0

21

6

4

3

19

18

7

2

16

11

12

15

5

14

20

8

17

9

10

0

1

13

15

21

7

5

4

19

18

8

3

12

13

16

6

20

9

0

10

11

1

2

14

17

20

16

21

8

6

5

19

18

9

13

14

17

7

10

1

11

12

2

3

15

0

4

11

20

17

21

9

7

6

19

18

14

15

0

8

2

12

13

3

4

16

1

5

10

3

12

20

0

21

10

8

7

19

15

16

1

9

13

14

4

5

17

2

6

11

18

14

4

13

20

1

21

11

9

8

16

17

2

10

15

5

6

0

3

7

12

18

19

17

0

1

2

3

4

5

6

7

18

19

20

21

16

15

14

13

12

11

10

9

8

6

7

8

9

10

11

12

13

14

21

20

19

18

5

4

3

2

1

0

17

16

15

12

13

14

15

16

17

0

1

2

19

18

21

20

11

10

9

8

7

6

5

4

3

10

11

12

13

14

15

16

17

0

20

21

18

19

9

8

7

6

5

4

3

2

1

19

18

3

16

12

9

15

14

6

7

8

11

1

17

0

2

21

10

20

4

13

5

18

2

15

11

8

14

13

5

4

6

7

10

0

19

16

17

1

21

9

20

3

12

1

14

10

7

13

12

4

3

11

5

6

9

17

18

19

15

16

0

21

8

20

2

13

9

6

12

11

3

2

10

1

4

5

8

16

0

18

19

14

15

17

21

7

20

8

5

11

10

2

1

9

0

20

3

4

7

15

12

17

18

19

13

14

16

21

6

4

10

9

1

0

8

17

20

5

2

3

6

14

7

11

16

18

19

12

13

15

21

9

8

0

17

7

16

20

4

21

1

2

5

13

3

6

10

15

18

19

11

12

14

7

17

16

6

15

20

3

21

13

0

1

4

12

8

2

5

9

14

18

19

10

11

16

15

5

14

20

2

21

12

10

17

0

3

11

6

7

1

4

8

13

18

19

9

 

Рис. 5

 

Второй диагональный латинский квадрат:

 

0

10

16

21

8

6

4

2

20

3

12

17

1

11

9

5

13

15

18

19

7

14

12

1

11

17

21

9

7

5

3

4

13

0

2

10

6

14

16

18

19

8

15

20

11

13

2

12

0

21

10

8

6

5

14

1

3

7

15

17

18

19

9

16

20

4

8

12

14

3

13

1

21

11

9

6

15

2

4

16

0

18

19

10

17

20

5

7

17

9

13

15

4

14

2

21

12

7

16

3

5

1

18

19

11

0

20

6

8

10

2

0

10

14

16

5

15

3

21

8

17

4

6

18

19

12

1

20

7

9

11

13

18

3

1

11

15

17

6

16

4

9

0

5

7

19

13

2

20

8

10

12

14

21

19

18

4

2

12

16

0

7

17

10

1

6

8

14

3

20

9

11

13

15

21

5

15

19

18

5

3

13

17

1

8

11

2

7

9

4

20

10

12

14

16

21

6

0

7

8

9

10

11

12

13

14

15

18

19

20

21

6

5

4

3

2

1

0

17

16

3

4

5

6

7

8

9

10

11

20

21

18

19

2

1

0

17

16

15

14

13

12

10

11

12

13

14

15

16

17

0

21

20

19

18

9

8

7

6

5

4

3

2

1

6

7

8

9

10

11

12

13

14

19

18

21

20

5

4

3

2

1

0

17

16

15

9

15

21

7

5

3

1

20

13

2

11

16

0

17

10

8

4

12

14

18

19

6

14

21

6

4

2

0

20

12

5

1

10

15

17

8

16

9

7

3

11

13

18

19

21

5

3

1

17

20

11

4

19

0

9

14

16

13

7

15

8

6

2

10

12

18

4

2

0

16

20

10

3

19

18

17

8

13

15

21

12

6

14

7

5

1

9

11

1

17

15

20

9

2

19

18

10

16

7

12

14

3

21

11

5

13

6

4

0

8

16

14

20

8

1

19

18

9

7

15

6

11

13

0

2

21

10

4

12

5

3

17

13

20

7

0

19

18

8

6

16

14

5

10

12

15

17

1

21

9

3

11

4

2

20

6

17

19

18

7

5

15

1

13

4

9

11

12

14

16

0

21

8

2

10

3

5

16

19

18

6

4

14

0

2

12

3

8

10

20

11

13

15

17

21

7

1

9

 

Рис. 6

 

И вот первый магический квадрат 22-го порядка, построенный методом латинских квадратов из пары ОДЛК (рис. 7). В цикле статей “Новые аспекты метода латинских квадратов” был построен методом латинских квадратов магический квадрат 22-го порядка из пары ОЛК. Для этого мне пришлось преобразовывать недиагональные латинские квадраты. Понятно, что из пары ОДЛК магический квадрат строится сразу, без предварительного преобразования латинских квадратов. Второй магический квадрат получится, если поменять местами латинские квадраты в формуле для построения магических квадратов.

 

1

429

413

110

383

293

225

355

351

180

211

282

46

34

76

468

256

456

129

328

140

169

57

24

430

414

132

10

316

248

378

203

234

287

69

99

469

279

457

151

350

163

192

373

122

80

47

431

397

154

33

339

271

226

257

310

92

470

302

458

173

372

186

215

395

5

471

145

103

70

432

398

176

56

362

249

280

333

115

325

441

195

394

209

238

21

28

294

348

472

168

126

93

433

399

198

79

272

303

356

138

442

217

20

232

243

43

51

317

385

443

353

473

191

149

116

434

400

220

295

326

379

161

239

42

255

266

65

74

340

12

102

261

444

376

474

214

172

139

435

401

318

331

6

184

64

278

289

87

97

363

35

125

242

86

283

445

3

475

237

177

162

436

341

354

29

207

301

312

109

120

386

58

148

264

402

324

108

305

446

26

476

260

200

185

364

377

52

230

335

131

143

13

81

171

286

403

419

382

9

32

55

78

101

124

147

170

415

438

461

484

359

336

313

290

267

244

221

216

193

136

159

182

205

228

251

274

297

320

483

462

437

416

113

90

67

62

39

16

389

366

343

275

298

321

344

367

390

17

40

45

440

417

482

459

252

229

206

183

160

137

114

91

68

227

250

273

296

319

342

365

388

15

460

481

418

439

204

181

158

135

112

89

84

61

38

428

412

88

360

270

202

332

329

146

157

188

259

23

392

11

53

467

233

455

107

306

117

411

66

337

247

179

309

307

123

94

134

165

236

18

427

369

384

30

466

210

454

85

284

44

314

224

156

304

285

100

71

262

111

142

213

391

410

426

346

361

7

465

187

453

63

291

201

133

281

263

77

48

240

41

106

119

190

368

22

409

425

323

338

380

464

164

452

178

128

258

241

54

25

218

19

451

83

96

167

345

268

396

408

424

300

315

357

463

141

105

235

219

31

2

196

393

450

118

60

73

144

322

155

245

374

407

423

277

292

334

480

212

197

8

375

174

371

449

95

479

37

50

121

299

82

150

222

352

406

422

254

269

311

175

381

370

152

349

448

72

478

288

14

27

98

276

189

59

127

199

330

405

421

231

246

358

347

130

327

447

49

477

265

223

387

4

75

253

153

166

36

104

194

308

404

420

208

 

Рис. 7

 

Вернёмся к КРМ, изображённой на рис. 2. В КРМ выделена секция,  содержащая четыре группы чисел: 2, 8, 9, 12;  6, 10, 12, 17;  1, 3, 12, 17 и 3, 6, 7, 10. В этих четырёх группах числа могут переставляться. Понятно, что в каждой группе возможны 24 перестановки, а во всех четырёх группах – 331776 перестановок. Однако далеко не все перестановки сохраняют ортогональность латинских квадратов. Чтобы  ортогональность сохранилась, третья и четвёртая строки КРМ должны быть совместимы по известному критерию. Составив и выполнив программу, я получила 576 вариантов КРМ. Значит, можно составить 576 неизоморфных пар ОЛК 22-го порядка, подобных паре ОЛК, приведённой на рис. 3 - 4. Покажу здесь только один вариант - № 576. На рис. 8 показана КРМ этого варианта.

 

 

a

b

c

d

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

a

b

c

d

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

12

9

8

2

17

12

10

6

0

2

5

d

15

c

11

3

14

16

7

9

4

8

13

1

a

b

17

12

3

1

7

10

6

3

0

12

11

8

17

2

a

b

15

5

c

13

16

1

4

d

14

9

 

Рис. 8

 

Пропускаю этап построения латинских квадратов пары ОЛК, определяемой данной КРМ, и сразу показываю полученную из этой пары ОЛК пару ОДЛК (рис. 9 – 10).

 

Первый диагональный латинский квадрат (решение № 576):

 

0

19

18

4

17

13

10

16

15

12

9

8

2

1

3

21

11

20

5

14

6

7

2

1

19

18

5

0

14

11

17

13

10

9

3

4

21

12

20

6

15

7

8

16

5

3

2

19

18

6

1

15

12

14

11

10

4

21

13

20

7

16

8

9

17

0

21

6

4

3

19

18

7

2

16

15

12

11

5

14

20

8

17

9

10

0

1

13

15

21

7

5

4

19

18

8

3

16

13

12

6

20

9

0

10

11

1

2

14

17

20

16

21

8

6

5

19

18

9

17

14

13

7

10

1

11

12

2

3

15

0

4

11

20

17

21

9

7

6

19

18

0

15

14

8

2

12

13

3

4

16

1

5

10

3

12

20

0

21

10

8

7

19

1

16

15

9

13

14

4

5

17

2

6

11

18

14

4

13

20

1

21

11

9

8

2

17

16

10

15

5

6

0

3

7

12

18

19

17

0

1

2

3

4

5

6

7

18

19

20

21

16

15

14

13

12

11

10

9

8

12

13

14

15

16

17

0

1

2

21