назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [ 97 ] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]


97

сумма этих трех расстояний равна нулю и что, обратно, любая тройка

« = {«1, а2, а3}, для которой эта сумма равна нулю, соответствует некоторой, точке.

Итак, представление на плоскости на рис. 31 выражает в точности

условие (32:2); поэтому оставшееся условие (32:2) равносильно ограниче-

->

нию, наложенному на точку а в плоскости на рис. 31. Это ограничение, очевидно, состоит в том, что точка должна лежать на треугольнике или

Рис. 31. Рис. 32.

Таким образом, заштрихованная область, которую мы называем

фундаментальным треугольником, представляет векторы а, которые удовлетворяют условиям (32:2) и (32:3), т. е. все дележи.

Рис. 33. Рис. 34.

W$ 32.1.3. Опишем теперь в этом графическом представлении отношение-доминирования. Так как п = 3, мы знаем из (31 :Н) (см. также обсуждение (31:8) в конце п. 31.1.5), что среди подмножеств S множества / = = (1, 2, 3) подмножества из двух элементов являются заведомо необходимыми, а все остальные - заведомо не необходимыми. Другими словами, множества, которые мы должны рассмотреть при нахождении всех, решений V, таковы: (1,2); (1,3); (2, 3). Таким образом, для

а = {аи а2, а3}, j3 = (р1э р2, р3}



а е- р

означает, что

(32:4) Либо (*! > р!, а2 > р2; либо аА > р4, а3 > р3; либо а2 > р2г

аз > Рз-

Графически: па рис. 33 а доминирует точки в заштрихованных областях и не доминирует никакие другие точки г).

Следовательно, точка а доминирует три из шести секторов, обозначу

ченных на рис. 34 (а именно А, С, Е). Отсюда легко получить, что а доминируется тремя другими секторами (а именно В, D, F). Итак, все те точки..

-у -у

которые не доминируют а и не доминируются а, лежат на трех прямых (т. е. на шести полупрямых), которые разделяют эти секторы. Это означает следующее:

(32:5) Если ни один из дележей а, р не доминирует другого, то

направление от а к р параллельно одной из сторон фундаментального треугольника. 32.1.4. Теперь можно начать систематические поиски всех решений. Рассмотрим решение V, т. е. множество в фундаментальном треугольнике, которое удовлетворяет условиям (30:5:а) и (30:5:Ь) из п. 30.1.1. В дальнейшем мы будем все время использовать эти условия, не ссылаясь на них явно в каждом случае.

Поскольку игра является существенной, множество V должно содержать хотя бы две точки 2), скажем

аир. На основании (32:5) направле- л

-у -v

ние от а к р параллельно одной из сторон фундаментального треугольника; переставляя номера игроков 1, 2, 3, мы можем считать ее стороной аА = -1, т.е. горизонтальной. Стало

-у -у

быть, точки аир лежат на горизонтальной прямой Z. Теперь появляются J две возможности, и мы рассмотрим их отдельно: (а) каждая точка множества V лежит на Z; (Ь) некоторые точки множества V не лежат на L

32.2. Нахождение всех решений

32.2.1. Рассмотрим сначала (Ь). Всякая точка, не лежащая на Z, должна удовлетворять условию (32:5)

-у -у

по отношению к а и к р, т. е. она

должна быть третьей вершиной одного из двух равносторонних треуголь-

-у -у -у -у

ников с основанием а, р, т. е. одной из двух точек а, а" на рис. 35. Итак,

-у -у

либо а, либо а" принадлежит множеству V. Любая точка множества Vr

х) В частности, не доминирует точек на границах этих областей. 2) Это также непосредственно видно из рис. 33.



отличная от точек а, р и а или а", должна снова удовлетворять условию

(32:5), но теперь уже по отношению ко всем трем точкам а, р и а или а". Это, однако, невозможно, как показывает непосредственное рассмотрение рис. 35. Итак, множество V состоит ровно из этих трех точек, т. е. из трех вершин треугольника, который расположен либо в виде треугольника /, либо в виде треугольника на рис. 36 и 37. Сравнение рис. 36, 37 с рис. 33 или 34 показывает, что вершины треугольника / оставляют недоминируемыми точки из внутренности этого треугольника. Это исключает из рассмотрения треугольник / х).

То же самое сравнение показывает, что вершины треугольника 77 не доминируют области, заштрихованные на рис. 38. Следовательно, треугольник 77 должен быть помещен относительно фундаментального треугольника таким образом, чтобы эти заштрихованные области оказались полностью вне фундаментального треугольника. Это означает, что три вершины треугольника должны лежать на трех сторонах фундаментального треугольника, как это показано на рис. 39. Следовательно, эти три вершины являются средними точками трех сторон фундаментального треугольника.

Сравнение рис. 39 с рис. 33 или 34 показывает, что множество V действительно является решением. Легко проверить, что эти три средние точки являются точками (векторами)

(32:6) {-l-y.ir}, {у, -1,4-}. {у. у -1}.

т. е. что это решение V является множеством, представленным табл. 23.

Рис. 36. Рис. 37. Рис. 38.

32.2.2. Рассмотрим теперь случай (а) из п. 32.1.4. В этом случае все элементы множества V лежат на горизонтальной прямой Z. На основании (32:5) никакие две точки прямой I не доминируют друг друга, так что никакая точка на I не доминируется множеством V. Следовательно, каждая точка прямой I (в фундаментальном треугольнике) должна принадлежать множеству V. Другими словами, множество V является в точности той частью прямой /, которая находится в фундаментальном тре-

->

угольнике. Таким образом, элементы а = {а4, а2, а3} множества V характеризуются уравнением (32:7) at = c.

г) Это приводит к примеру из п. £0.3.6. Три вершины треугольника / не доминируют друг друга, т. е. они образуют удовлетворяющее множество в указанном выше смысле. Тем не менее они не являются подходящими в качестве подмножества решения.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [ 97 ] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]