Các bản vá trên caftan

13

Ở vị trí số 1 của tạp chí «Kvant» trong năm nay, bài toán sau đây của E. B. Dynkina đã được xuất bản:

M185 *. Trên cafman có diện tích 1, đặt 5 ngọn lửa, diện tích của mỗi ngọn lửa không nhỏ hơn $1/2$. Chứng minh rằng bạn sẽ tìm được hai ngọn lửa có diện tích phần chung không nhỏ hơn $1/5$.

Chúng tôi sẽ phân tích lời giải trong số bài toán này và thảo luận về một số điểm khái quát và biến thể của nó *). Phần trình bày của chúng tôi sẽ đi kèm với các nhiệm vụ trong đó, đặc biệt, các chi tiết riêng lẻ của bằng chứng sẽ được ghi chú; những số khó nhất bài toán được đặt bằng dấu hoa thị.

Chúng ta sẽ biểu thị cả caftan và diện tích của nó (theo quy ước bằng 1) bằng chữ cái $M$; chúng tôi biểu thị các miếng vá trên caftan (và diện tích của các miếng vá này) bằng $M_1$, $M_2$, $M_3$, $M_4$ và $M_5$, và, chẳng hạn, phần đã hứa của các miếng vá $M_1$ và $M_2$ (và diện tích của phần chung này) bằng $M_{12}$; tương tự, chúng tôi biểu thị phần chung của các miếng vá $M_1$, $M_2$ và $M_3$ (và diện tích của nó) bằng $M_{123}$, v.v. Ví dụ: đối với sự cản trở, bằng $M_1$, chúng tôi biểu thị cả miếng vá (hàm hình học) và diện tích của miếng vá này (số!), không nên gây nhầm lẫn cho chúng tôi - từ văn bản mỗi lần, chúng tôi sẽ rõ ràng theo nghĩa nào chúng tôi sử dụng ký hiệu $M_1$.

Chúng ta bắt đầu giải quyết bài toán

Từ việc hứa hẹn thành quả của mọi miếng vá

$$M_1 + M_2 + M_3 + M_4 + M_5 \geq \frac{5}{2}$$

diện tích lớn $M = 1$ của caftan, theo đó các tấm của chúng ta chồng lên nhau - và bài toán là để ước tính diện tích của các phần chung của chúng (chính xác hơn là ước tính phần lớn các số $M_{12}$, $M_{13}, \dots, M_{45}$). Chúng tôi khẳng định rằng

$$M - (M_1 + M_2 + M_3 + M_4 + M_5) + (M_{12} + M_{13} + M_{14} + \dots + M_{45}) \geq 0.$$ (1)

Trên thực tế, nếu các miếng vá không chồng lên nhau thì sẽ có sự chênh lệch không âm $M - (M_1 + M_2 + M_3 + M_4 + M_5)$, bằng diện tích của phần caftan hoàn toàn không được miếng vá che phủ. Nhưng trên thực tế, các tấm của chúng tôi giao nhau - và tổng $M_1 + M_2 + M_3 + M_4 + M_5$ hóa ra lớn hơn nhiều so với tổng diện tích $S$ của phần caftan được bao phủ bởi các kế hoạch (trong đó, tất nhiên, $S \leq M = 1$): phần $M_{12}$ của caftan được tính vào tổng $M_1 + M_2 + M_3 + M_4 + M_5$ hai lần, vì nó được bao gồm trong thuật ngữ $M_1$ và trong thuật ngữ $M_2$, phần $M_{123}$ - ba lần, v.v. Bây giờ hãy thử chứng minh điều đó

$$S \geq \sum M_i - \sum M_{ij}.$$ (1')

*) Một đoạn ngắn lời giải của bài toán này được đưa ra trong «Kvant» Số 10, 1973.

14

Nếu bạn thất bại, hãy đọc phần tiếp theo của số liệu thống kê và sau đó quay lại với bất đẳng thức này.

Từ (1’), vì $M \geq S$, bất đẳng thức (1) dẫn đến.

Bất đẳng thức (1) đã cho phép chúng ta ước tính giao điểm theo cặp của các mảng $M_{12}, M_{13}, \dots$. Thật vậy, nó tuân theo $(M_{12} + M_{13} + \dots + M_{45}) \geq \geq (M_1 + M_2 + M_3 + M_4 + M_5) - M \geq \geq \frac{5}{2} - 1 = \frac{3}{2}$.

Và vì tổng số giao điểm theo cặp của các mảng $M_{ij}$ bằng $C_5^2 = 10$, nên lớn nhất các số $M_{12}, M_{13}, \dots, M_{45}$ không nhỏ hơn
$$\frac{3}{2}:10 = \frac{3}{20}.$$

Tuy nhiên, ước tính mà chúng tôi thu được là x đã là ước tính bắt buộc $\frac{1}{5} \left( = \frac{4}{20} \right)$.

Đánh bại

1. Trên caftan của khu vực 1 có 9 mảng diện tích $1/5$. Chứng minh rằng bạn có thể tìm thấy hai mảnh có diện tích chung ít nhất là $1/45$.

Công thức bao gồm và loại trừ

Ước tính của chúng tôi (1’) cho diện tích $S$ của toàn bộ phần caftan được bao phủ bởi các kế hoạch là không chính xác. Hãy cố gắng xác định khu vực này chính xác hơn. Quy tắc của phần công thức (1’) sẽ không bao gồm diện tích của bất kỳ phần nào của caftan được bao phủ bởi ba kế hoạch cùng một lúc: ví dụ: $M_{123}$ sẽ được bao gồm trong các số hạng dấu cộng $M_1, M_2, M_3$ và trong các số hạng dấu trừ $M_{12}, M_{13}, M_{23}$ - nghĩa là chúng ta sẽ hoàn toàn tuân theo công thức (1’). Do đó, ước tính tốt hơn cho $S$ có thể là biểu thức
$$\sum M_i - \sum M_{ij} + \sum M_{ijk}.$$
Tuy nhiên, giá trị này vẫn chưa bằng $S$, vì phần nào của caftan $M$, được bao phủ bởi ba mặt phẳng cùng một lúc, tính đến hai

Có: trên thực tế, giả sử, giá trị $M_{1234}$ tính đến 8 số hạng $M_1, M_2, M_3, M_4; M_{123}, M_{124}, M_{134}, M_{234}$ của biểu thức cuối cùng, được bao gồm trong đó bằng dấu “cộng” và chỉ có 6 số hạng $M_{12}, M_{13}, M_{14}, M_{23}, M_{24}$ và $M_{34}$, được bao gồm trong biểu thức này với dấu “trừ”. Do đó, giá trị gần đúng với giá trị thực $S$ là biểu thức
$$\sum M_i - \sum M_{ij} + \sum M_{ijk} - \sum M_{ijkl},$$
vốn đã “gần bằng” với $S$ - nó tính đến chính xác tất cả các phần của caftan $M$, được bao phủ bởi các kế hoạch không quá bốn kế hoạch, từ biểu thức cuối cùng “vinadem”: trên thực tế, nó được bao gồm trong tất cả các điều khoản của biểu thức này, nghĩa là, cả trong 15 điều khoản $M_1, M_2, M_3, M_4, M_5; M_{123}, M_{124}, \dots, M_{345}$, có dấu cộng ở phía trước và trong 15 điều khoản $M_{12}, M_{13}, \dots, M_{45}; M_{1234}, M_{1235}, M_{1245}, M_{1345}$ và $M_{2345}$, với dấu trừ ở phía trước. Do đó, để có được biểu thức chính xác cho $S$, chúng ta phải thêm số hạng $M_{12345}$ vào tổng cuối cùng. Đây là sự bình đẳng chính xác:
$$S = \sum M_i - \sum M_{ij} + \sum M_{ijk} - \sum M_{ijkl} + M_{12345}.$$
(ở đây $i, j, k, l = 1, 2, 3, 4$ hoặc 5). Nhưng diện tích σ của phần caftan không nằm trong quy hoạch nào thì bằng $M - S$; vì $\sigma \geq 0$, chúng ta có $\sigma = M - \sum M_i + \sum M_{ij} - \sum M_{ijkl} + \sum M_{ijkl} - M_{12345} \geq 0.$

Công thức (3) có được bằng cách loại trừ tuần tự các phần của caftan $M$ bằng các kế hoạch chết người và bao gồm cả những phần trong số chúng hóa ra bị loại trừ theo hai tiêu chí; đôi khi nó được gọi là công thức bao gồm và loại trừ. Công thức này được sử dụng trong nhiều phép tính tổ hợp.

15

Công thức bao gồm và loại trừ cũng có giá trị đối với một số miếng vá khác ngoài gót chân. Trong trường hợp chung $n$ công thức bản vá bao gồm và loại trừ, bề ngoài nó có nhiều điểm phức tạp, nhưng về bản chất nó có dạng hoàn toàn minh bạch:

$$\sigma = M - \sum M_{i_1} + \sum M_{i_1 i_2} - \sum M_{i_1 i_2 i_3} + \sum M_{i_1 i_2 i_3 i_4} - \dots + (-1)^{n-1} \sum M_{i_1 i_2 i_3 \dots i_{n-1}} + (-1)^n M_{123 \dots n} \geq 0$$

(ở đây tất cả các chỉ số $i_1, i_2, \dots, i_{n-1}$ có thể nhận bất kỳ giá trị nào trong số các giá trị 1, 2, 3, \dots, $n$ và đối với giao điểm của các mảng $M_{i_1 i_2 \dots i_k}$ $M_{i_1} M_{i_2} \dots M_{ik}$ tất cả các giá trị $i_1, i_2, \dots, i_k$ nhất thiết phải khác nhau).

Bài tập
2. Chứng minh công thức (4) cho $n = 6$.
3*. Chứng minh công thức (4).
4. Domponer thường xuyên được 220 học sinh đến thăm. Ở nội bộ có sáu phần thể thao: điền kinh (l), bóng chuyền (v), bóng rổ (b), bóng đá (f), phần sambo (s) và phần cờ vua (w). Số lượng người tham gia các phần này như sau: (l) - 30 người, (c) - 26 người, (b) - 32 người, (f) - 31 người, (c) - 28 người và (w) - 36 người. 53 học sinh tham dự một số phần; trong số này, 24 học sinh tham dự ba phần trở lên, 9 học sinh - ít nhất là bốn phần, và 3 học sinh - thậm chí năm phần (ba học sinh cuối cùng còn có một học sinh lập dị tham dự cả sáu phần thể thao). Có bao nhiêu học sinh theo học Domponers không tham gia bất kỳ môn thể thao nào?

Lời giải bài toán M185

Chúng tôi đã thấy rằng công thức “rút gọn” bao gồm và loại trừ $M - \sum M_i + \sum M_{ij} \geq 0$ (1) không đưa ra ước tính chính xác về giá trị mà chúng tôi quan tâm tối đa $M_{ij}$ (giá trị lớn nhất $M_{ij}$); do đó chúng ta sẽ phải sử dụng công thức “hoàn chỉnh” $M - \sum M_i + \sum M_{ij} - \sum M_{ijk} + \sum M_{ijkl} - M_{12345} \geq 0$. (3')

Bây giờ chúng ta hãy áp dụng công thức bao gồm và loại trừ (4) (trong đó chúng ta hiện giả định rằng $n = 4$) cho phần $M_1$ của caftan $M$, được bao phủ bởi các miếng vá $M_{12}, M_{13}, M_{14}$ và $M_{15}$. chúng tôi nhận được

$$\sigma_1 = M_1 - \sum M_{1i} + \sum M_{1ij} - \sum M_{1ijk} + M_{12345} \geq 0,$$

trong đó $\sigma_1$ là một phần của bản vá $M_1$ không được bao phủ bởi các bản vá khác và các số (hoặc chỉ số) $i, j, k$ chạy qua tất cả các giá trị có thể có 2, 3, 4 hoặc 5. Các bất đẳng thức tương tự có thể được viết cho các phần $M_2, M_3, M_4$ và $M_5$ của caftan:

$$\sigma_2 = M_2 - \sum M_{2i} + \sum M_{2ij} - \sum M_{2ijk} + M_{12345} \geq 0,$$

$$\sigma_5 = M_5 - \sum M_{5i} + \sum M_{5ij} - \sum M_{5ijk} + M_{12345} \geq 0.$$

Cộng 5 bất đẳng thức thu được theo cách này, tương ứng với các tiết diện $M_1, M_2, \dots, M_5$ của caftan, ta được (kiểm tra cái này):

$$\sum M_i - 2 \sum M_{ij} + 3 \sum M_{ijk} - 4 \sum M_{ijkl} + 5 M_{12345} \geq 0.$$ (5)

Bây giờ chúng ta hãy tìm sự kết hợp của các bất đẳng thức (3’) và (5) trong đó thiếu tổng $\sum M_{ijk}$ của “ba mảng chồng chéo”. Rõ ràng, để làm được điều này, chỉ cần cộng vào (3’) bất đẳng thức (5) nhân với $1/3$ là đủ. Ta thu được bất đẳng thức sau

$$M - \frac{2}{3} \sum M_i + \frac{1}{3} \sum M_{ij} - \frac{1}{3} \sum M_{ijkl} + \frac{2}{3} M_{12345} \geq 0.$$ (6)

Từ đó cũng suy ra rằng

$$M - \frac{2}{3} \sum M_i + \frac{1}{3} \sum M_{ij} \geq 0.$$ (7)

Thật vậy, phần $M_{12345}$ của caftan được bao gồm trong mỗi phần $M_{ijkl}$ của nó, do đó $\sum M_{ijkl} > 5M_{12345}$ và

16

Công thức tổng quát bài toán;
trường hợp hai lớp

Trên một cafman M của vùng 1 có n lớp $M_1, M_2, \dots, M_n$, diện tích adb của mỗi lớp không nhỏ hơn số $\alpha$ mà chúng ta đã biết; cần phải ước tính diện tích adb của hầu hết các giao điểm của lớp $M_{ij}$.

Nói cách khác, đối với mỗi cấu hình của $n$ lớp trên caftan, chúng tôi tìm mức tối đa $M_{ij}$, sau đó tìm mức tối thiểu của mức tối đa $M_{ij}$ này trên tất cả các cấu hình có thể có của các lớp*). Loại “minimax” này (nghĩa là liên quan đến việc tìm cực tiểu của một số cực đại nhất định) bài toán đóng một vai trò rất quan trọng trong toán học hiện đại.

Tất nhiên, số được yêu cầu tối thiểu tối đa $M_{ij}$ phụ thuộc vào số đã cho $\alpha$, nghĩa là nó là hàm của $\alpha$; vì nó cũng phụ thuộc vào số lượng $n$ của lớp, nên chúng tôi biểu thị hàm này bằng $f_n(\alpha)$ (trong đó, rất thuận tiện, $0 \leqslant \alpha \leqslant 1$ và $n \geqslant 2$). Lời giải bài toán M185 rút gọn về chứng minh đẳng thức

$$f_5\left(\frac{1}{2}\right) = \frac{1}{5};$$

tổng quát bài toán yêu cầu một công thức biểu thị $f_n(\alpha)$ theo $\alpha$ và $n$.

Để hiểu loại đáp số mà chúng ta có thể mong đợi trong bài toán chung này, chúng ta bắt đầu với trường hợp (rất đơn giản!) $n = 2$. Vì vậy, chúng tôi tin rằng trên caftan M của khu vực 1 có hai lớp $M_1$ và $M_2$, diện tích adb của mỗi lớp không nhỏ hơn $\alpha$; chúng ta cần chỉ ra diện tích nhỏ nhất có thể $f_2(\alpha)$ giao điểm $M_{12}$ của hai lớp này.

Rõ ràng là nếu $\alpha \leqslant 1/2$, thì các mảng có thể xuất hiện ở tất cả các giao lộ (Hình 2, a); nếu $\alpha \geqslant 1/2$ thì diện tích nhỏ nhất có thể có $f_2(\alpha)$ của giao lộ

*) Chúng tôi giả định rằng mức tối thiểu như vậy tồn tại, mặc dù điều này không mấy thuận tiện.

17

M$_{12}$ của các miếng vá bằng $2\alpha - 1$ (Hình 2, b). Như vậy,

$$f_2(\alpha) = \begin{cases} 0 & \text{при } 0 \leqslant \alpha \leqslant 1/2, \\ 2\alpha - 1 & \text{при } 1/2 \leqslant \alpha \leqslant 1, \end{cases}$$

• tức là đồ thị của hàm số $y = f_2(\alpha)$ là một đường đứt nét (Hình 3). Trường hợp này được gọi là đường đứt đoạn.

Bài tập
5. Mô tả hàm $y = f_3(\alpha)$.
Gợi ý e: xét ba cung $M_1, M_2$ và $M_3$ của hình tròn $M$, các trục đối xứng $l_1, l_2$ và $l_3$ trong đó xếp thành từng cặp tạo thành các góc bằng $120^\circ$ và các góc ở tâm (được đo bằng phân số của một góc đầy!) bằng $\alpha$; bắt đầu với các giá trị nhỏ $\alpha$ (Hình 4) và xem điều gì xảy ra khi bạn tăng $\alpha$ lên đến $\alpha = 1$.

Trường hợp miếng dán gót chân
Bây giờ chúng ta chuyển sang trường hợp ban đầu gồm 5 bản vá $M_1, M_2, M_3, M_4$

Hình 3.

Hình 4.

2 «Kvant» № 2

18

bằng 0 và tất cả $M_{ij}$ phải có cùng giá trị $\frac{1}{2}\alpha - \frac{1}{10}$. Nhưng nếu tất cả $M_{ijk} = 0$, thì mỗi mảng của khu vực $\alpha$ (ví dụ: mảng $M_1$) “miếng vá trên miếng vá” $M_{12}, M_{13}, M_{14}$ và $M_{15}$ khu vực $\frac{1}{2}\alpha - \frac{1}{10}$ phải bao phủ mà không chồng chéo, điều này chỉ có thể thực hiện được nếu $4\left(\frac{1}{2}\alpha - \frac{1}{10}\right) \leq \alpha$ và do đó, $\alpha \leq \frac{2}{5}$ (so sánh với phân tích ở trên trong trường hợp chuyển đổi hàm $f_5(\alpha)$ thành 0).

Vì vậy, chúng ta có thể tiếp tục biểu đồ của hàm $y = f_5(\alpha)$:

$$f_5(\alpha) = \frac{1}{2}\alpha - \frac{1}{10}$$ tại $\frac{1}{5} \leq \alpha \leq \frac{2}{5}$.

Tiếp theo chúng ta sẽ phải chuyển sang bất đẳng thức (7) (tr. 15), đây là công cụ chính của lời giải bài toán M185. Từ bất đẳng thức này suy ra rằng

$$\sum M_{ij} \geq 2\sum M_i - 3M \geq 2(5\alpha) - 3 = 10\alpha - 3,$$

Ở đâu

$$f_5(\alpha) \geq \frac{1}{10}(10\alpha - 3) = \alpha - \frac{3}{10}.$$

Bất đẳng thức (10) được thỏa mãn với mọi $\alpha$ (tức là đồ thị của hàm $y = f_5(\alpha)$ nằm hoàn toàn phía trên đường thẳng $y = \alpha - \frac{3}{10}$; Hình 7); tuy nhiên, nó chỉ trở thành đẳng thức tại $\frac{2}{5} \leq \alpha \leq \frac{3}{5}$ (xem Bài tập 6,a).

Tiếp theo, chúng ta sẽ phải áp dụng công thức bao gồm và loại trừ không chỉ cho vùng $M_i$ của caftan mà còn cho các vùng $M_{ij}$ và $M_{ijh}$. Do đó, áp dụng công thức này cho caftan $M_{12}$, được bao phủ bởi phần thứ ba $M_{123}, M_{124}$ và $M_{125}$, chúng ta thu được

$$\sigma_{12} = M_{12} - \sum M_{12i} + \sum M_{12ij} - M_{12345} \geq 0.$$

Viết ra 10 bất đẳng thức tương tự tương ứng với 10 giao điểm của các mảng $M_{ij}$, rồi cộng tất cả chúng lại, chúng ta được (kiểm tra cái này!) rằng

$$\sum M_{ijh} - 4\sum M_{ijkl} + 10M_{12345} \geq 0.$$

19

Hình 8.

Bây giờ chúng ta có bốn bất đẳng thức (3′), (5), (11) và (12) liên quan đến các đại lượng giống nhau $M$, $\sum M_i$, $\sum M_{ij}$, $\sum M_{ijk}$, $\sum M_{ijkl}$ và $M_{12345}$.

Cộng các bất đẳng thức (3′); (5) nhân với $1/2$; (11) nhân với $1/6$, ta thu được bất đẳng thức

$$M - \frac{1}{2} \sum M_i + \frac{1}{6} \sum M_{ij} - \frac{1}{6} M_{12345} \geq 0,$$

(13)

từ đó cả thuật ngữ $\sum M_{ijk}$ và thuật ngữ $\sum M_{ijkl}$ đều bị loại bỏ. Từ (13), rõ ràng suy ra rằng còn hơn thế nữa

$$M - \frac{1}{2} \sum M_i + \frac{1}{6} \sum M_{ij} \geq 0$$

và, do đó,

$$\sum M_{ij} \geq 3 \sum M_i - 6M \geq 3(5\alpha) - 6,$$

Ở đâu

$$f_5(\alpha) \geq \frac{1}{10}(15\alpha - 6) = \frac{3}{2}\alpha - \frac{3}{5}.$$

(14)

Như vậy, đồ thị của hàm $y = f_5(\alpha)$ không nằm dưới đường thẳng $y = \frac{3}{2}\alpha - \frac{3}{5}$ (Hình 8).

Tương tự, cộng các bất đẳng thức (3′); (5) nhân với $3/5$;

(11) nhân với $3/10$; (12), nhân với $1/10$, ta thu được bất đẳng thức

$$M - \frac{2}{5} \sum M_i + \frac{1}{10} \sum M_{ij} \geq 0,$$

(15)

từ đó tất cả các số hạng ngoại trừ $M$, $\sum M_i$ và $\sum M_{ij}$ đã bị loại bỏ. Từ (15), hiển nhiên suy ra rằng

$$\sum M_{ij} \geq 4 \sum M_i - 10M \geq 4(5\alpha) - 10 = 20\alpha - 10$$

và, do đó,

$$f_5(\alpha) \geq \frac{1}{10}(20\alpha - 10) = 2\alpha - 1.$$

Như vậy, đồ thị của hàm $y = f_5(\alpha)$ không nằm dưới đường thẳng $y = \frac{3}{2}\alpha - \frac{3}{5}$ (Hình 8).

Bài tập

6. Chứng minh rằng

a) $f_5(\alpha) = \alpha - \frac{3}{10}$ tại $2/5 \leq \alpha \leq 3/5$;

b) $f_5(\alpha) = \frac{3}{2}\alpha - \frac{3}{5}$ tại $3/5 \leq \alpha \leq 4/5$;

b) $f_5(\alpha) = 2\alpha - 1$ tại $4/5 \leq \alpha \leq 1$.

7. Mô tả chức năng

a) $f_4(\alpha)$; b) $f_6(\alpha)$.

20

Trường hợp $n$ bản vá lỗi

Trường hợp này được xử lý tương tự như trường hợp $n = 5$; Hãy để chúng tôi phác thảo ngắn gọn lý do tương ứng.

Trước hết, rõ ràng là để các miếng vá $n$ $M_1, M_2, \dots, M_n$, diện tích của mỗi miếng không nhỏ hơn $\alpha$, không bị chồng lên nhau thì tổng diện tích của chúng $\sum M_i \geq n\alpha$ không vượt quá diện tích $M = 1$ của caftan; Đó là lý do tại sao

$$f_n(\alpha) = 0 \text{ при } 0 \leq \alpha \leq \frac{1}{n}.$$

Tiếp theo, xét bất đẳng thức chính (4) (công thức bao gồm và loại trừ, trang 15). Từ bất đẳng thức này suy ra rằng

$$M - \sum M_i + \sum M_{ij} \geq 0 \tag{16}$$

(Tại sao?); và, do đó,

$$\sum M_{ij} \geq \sum M_i - M \geq n\alpha - 1.$$

Và vì tổng số “giao điểm theo cặp của các miếng vá” $M_{ij}$ trong trường hợp chung bằng với số $C_n^2 = \frac{n(n-1)}{2}$ tương ứng từ $n$ x 2, nên

$$f_n(\alpha) \geq \frac{1}{n(n-1)/2} (n\alpha - 1) = \frac{2}{n-1} \alpha - \frac{2}{n(n-1)}. \tag{17}$$

Trong trường hợp này, bất đẳng thức (17) chỉ có thể chuyển thành đẳng thức nếu nó biến thành đẳng thức (16), nghĩa là, nếu trong công thức bao gồm và loại trừ (4) tất cả các số hạng theo sau $\sum M_{ij}$ chuyển thành 0 (và ngoài ra, nếu tất cả các mảng $M_i$ có diện tích $\alpha$ và che phủ hoàn toàn caftan $M$). Nhưng trong trường hợp này, $n - 1$ của “điểm giao nhau của các bản vá theo cặp” $M_{12}, M_{13}, \dots, M_{1n}$ che bản vá $M_1$ mà không chồng chéo (vì tất cả đều là $M_{ij} = 0$). Và vì trong trường hợp này mọi thứ

$$M_{1i} = \frac{2}{n-1} \alpha - \frac{2}{n(n-1)},$$

Cái đó

$$(n - 1) \left[ \frac{2}{n-1} \alpha - \frac{2}{n(n-1)} \right] \leq \alpha,$$

và do đó $\alpha \leq \frac{2}{n}$ (và tất nhiên là $\alpha \geq \frac{1}{n}$).

Tiếp theo, chúng ta sẽ phải áp dụng công thức được bao gồm và loại trừ cho các bản vá $M_i$ (thay vì toàn bộ caftan $M$), cho các giao điểm của chúng $M_{ij}, M_{ijh}$, v.v. Ví dụ: chúng ta hãy áp dụng công thức này cho bản vá $M_1$, được bao phủ bởi “các bản vá thứ hai” $M_{12}, M_{13}, \dots, M_{1n}$:

$$M_1 - \sum M_{1i} + \sum M_{1i1} i_2 - \sum M_{1i1} i_2 i_3 + \dots + (-1)^{n-2} \sum M_{1i1} i_2 \dots i_{n-2} + (-1)^{n-1} M_{123} \dots n \geq 0$$

(trong đó $i_1, i_2, \dots, i_{n-2} = 2, 3, \dots, n$).

Cộng $n$ các bất đẳng thức tương ứng với các mảng $M_1, M_2, \dots, M_n$, ta thu được bất đẳng thức

$$\sum M_i - 2 \sum M_{i1} i_2 + 3 \sum M_{i1} i_2 i_3 - \dots + (-1)^{n-2}(n-1) \sum M_{i1} i_2 \dots i_{n-1} + (-1)^{n-1} n M_{123} \dots n \geq 0 \tag{18}$$

(xem bất đẳng thức (5) ở trang 15). Từ bất đẳng thức (4) và (18), không khó để sử dụng thuật ngữ $\sum M_{i1} i_2 i_3$ - đối với điều này, chỉ cần cộng (4) với phép nhân với 1/3 với bất đẳng thức (18):

$$M - \frac{2}{3} \sum M_{i1} + \frac{1}{3} \sum M_{i1} i_2 - \frac{1}{3} \sum M_{i1} i_2 i_3 i_4 + \dots + (-1)^{n-1} \frac{n-3}{3} \times M_{123} \dots n \geq 0. \tag{19}$$

Từ (19) suy ra rằng

$$M - \frac{2}{3} \sum M_{i1} + \frac{1}{3} \sum M_{i1} i_2 \geq 0 \tag{19a}$$

và, do đó,

$$\sum M_{i1} i_2 \geq 2 \sum M_{i1} - 3 M \geq 2 (n\alpha) - 3 = 2n\alpha - 3.$$

Như vậy,

$$f_n(\alpha) \geq \frac{1}{n(n-1)} (2n\alpha - 3) =$$

21

$$\frac{4}{n-1} \alpha - \frac{6}{n(n-1)},$$

Hơn nữa, đẳng thức (20) chỉ biến thành $\frac{2}{n} \leqslant \alpha \leqslant \frac{3}{n}$ (xem Bài tập 8).

Tiếp tục làm tương tự như trên, cuối cùng ta sẽ tìm được

$$f_n(\alpha) = 2 \frac{r-1}{n-1} \alpha - \frac{r(r-1)}{n(n-1)}$$

tại $\frac{r-1}{n} \leqslant \alpha \leqslant \frac{r}{n}$, $r=1, 2, \ldots, n$.

Bài tập

8. Chứng minh rằng (20) chỉ trở thành đẳng thức với $\frac{2}{n} \leqslant \alpha \leqslant \frac{3}{n}$.

9*. Chứng minh rằng $f_n(\alpha) = \frac{6}{n-1} \alpha - \frac{12}{n(n-1)}$ cho $\frac{3}{n} \leqslant \alpha \leqslant \frac{4}{n}$.

10*. Chứng minh đẳng thức (21).

Ghi chú bổ sung

1. Tất nhiên, ngay cả những công thức “tổng quát” (21) cũng chưa làm hết phạm vi của ghi chú này; nó có thể được tiếp tục khá xa hơn.

2°. Phương pháp “cân bằng bản vá”. Bài toán M185 đã nhận được khá nhiều lời giải thư từ độc giả «Kvant»; Một số độc giả cũng đưa ra thảo luận về $n$ các mảng diện tích, không nhỏ hơn $\alpha$ trên caftan của khu vực 1. Tuy nhiên, chỉ có V. Khonin từ Pervouralsk trong bức thư rất thú vị của mình đã giải được hoàn toàn “tổng quát” bài toán này và tìm ra các công thức về cơ bản tương đương với các công thức (21). Đồng thời, con đường mà V. Khonin đi theo về cơ bản khác với con đường được phát triển trong ghi chú này. Về cơ bản, Khonin tiến hành từ Hình 1, mô tả lớp phủ “tối ưu” của caftan với năm miếng vá: từ hình này, rõ ràng là trong tình huống thuận lợi nhất, tất cả các phần của caftan đều được che phủ bằng hai hoặc ba miếng vá, và tất cả các giao điểm của miếng vá $M_{ij}$ (trong đó $i$ và $j=1, 2, \ldots, 5$) và tất cả các giao điểm $M_{ijh}$ đều bằng nhau.

Dựa trên điều này, Khonin phát triển một quy trình độc đáo để “cắt lại” các miếng vá nhằm cân bằng diện tích của chúng và diện tích các giao điểm của chúng, trong đó, việc loại trừ các giá trị tối đa $M_{ij}$ không phải lúc nào cũng tăng; Bằng cách này, anh ta chứng minh rằng trong trường hợp tổng quát, vị trí “tối ưu” của chúng (mà chúng ta đạt được trong quá trình xây dựng “sự căn chỉnh” các miếng vá) sẽ gần với Hình 1, cho phép anh ta tìm ra các công thức (21). Đồng thời, phương pháp lời giải bài toán do V. Khonin đề xuất rất hứa hẹn trong trường hợp bài toán phức tạp hơn.

Trong khi chuẩn bị xuất bản bài báo, người biên tập đã nhận được một bức thư từ A. Makarevich, một học sinh lớp 9 ở Lvov, trong đó cách tiếp cận lời giải bài toán M185 và dạng tổng quát của nó, tương tự như phương pháp do V. Khonin đề xuất, đã được phát triển. Thật không may, do thiếu chỗ nên chúng tôi không thể xuất bản ghi chú thú vị này.

3°. Về các phương pháp “quy hoạch tuyến tính”. Hình 9 cho thấy rằng lời giải của “tổng quát” bài toán giảm xuống còn lời giải một hệ bất đẳng thức tuyến tính liên hệ giá trị $y (=f_n(\alpha))$ với số $\alpha$. Các câu hỏi liên quan đến lời giải hệ bất đẳng thức tuyến tính đóng một vai trò lớn trong các ứng dụng hiện đại của các phương pháp toán học vào các bài toán kinh tế; đối với họ lời giải các phương pháp đặc biệt đã được phát triển - cái gọi là “phương pháp lập trình tuyến tính” *). Vào năm 1968, phương pháp quy hoạch tuyến tính đã được sử dụng cho lời giải “tổng quát” bài toán bởi sinh viên Đại học Moscow Sergei Pirogov, và ông không chỉ chứng minh được công thức (21) mà còn giải được nhiều hơn bài toán.

*) Ví dụ, hãy xem cuốn sách nổi tiếng: S. Gass, Journey to the Land of Linear Programming, M., “Mir”, 1973; xem thêm chương. 13 cuốn sách xuất sắc: A. Kofman, R. Faure, Let’s Do Operations Research, M., “Mir”, 1966.