Nghiên cứu về bán bất biến

Kvant 1989, số 7 tr. 63, 65, 66, 67, 68 Thẻ UBAD

Bản dịch tự động sơ bộ, chất lượng thấp: có thể còn lỗi và câu chữ chưa tự nhiên. Bản này sẽ được thay bằng bản dịch tốt hơn. Bản gốc →

Bản phác thảo
về bán bất biến

L. D. KURLYANDCHIK, D. V. FOMIN

Nếu bạn muốn kết hợp công việc kinh doanh với niềm vui, thì hãy chuẩn bị sẵn một túi hội nghị và chơi trò chơi này cùng với một người bạn. Đặt hai chồng phần thưởng trên bàn, chồng thứ nhất có 12 phần thưởng và chồng thứ hai có 13. Trong mỗi lượt, mỗi bạn có thể ăn hai phần thưởng từ một chồng hoặc di chuyển một phần thưởng từ chồng đầu tiên sang chồng thứ hai. Người nào không thể di chuyển sẽ thua.

Nếu tài nguyên của bạn cho phép bạn chơi trò chơi tuyệt vời này trong thời gian dài, thì bạn sẽ nhận thấy một điều kỳ lạ: người mới bắt đầu luôn thua! Tuy nhiên, lý do cho điều này là dễ hiểu. Thực tế là với mỗi lần di chuyển, sự khác biệt giữa số lượng hội nghị ở cọc thứ hai và cọc thứ nhất thay đổi hai. Điều này có nghĩa là số dư khi chia số chênh lệch này cho 4 sẽ thay đổi theo một cách xác định chặt chẽ: 1, 3, 1, 3, 1, 3,… Ta thấy rằng với mỗi nước đi của người chơi thứ hai, số dư này sẽ bằng trem. Nhưng trò chơi chỉ dừng lại nếu hết kẹo hoặc chỉ còn lại một viên kẹo và ở đống thứ hai. Tình huống này không thể xảy ra trong quá trình di chuyển của người chơi thứ hai.

Rất có thể bạn biết ý tưởng của lý luận này, cụ thể, nếu “kinh nghiệm đọc sách” của bạn đủ lâu, bạn có thể bắt gặp lý luận tương tự ở quốc gia “Ponishk bất biến” («Kvant», 1976, số 2). Nhớ? Một bất biến là một cái gì đó không thay đổi. Và ở đây, cứ mỗi hai nước đi, số dư không thay đổi khi chia cho số chênh lệch chẵn về số hội nghị trong các nhóm. (Tất nhiên, thông báo này áp dụng cho bất kỳ số hội nghị nào khác.) Tuy nhiên,

một hình ảnh bao gồm $n$ đường thẳng và $n$ đường vuông góc. Hãy chọn hai đường vuông góc giao nhau trên đó và áp dụng thao tác của chúng ta: thay thế hai đường vuông góc này bằng hai đường vuông góc khác có tổng độ dài nhỏ hơn. Trong hình ảnh kết quả, chúng ta sẽ lại tìm thấy hai đường vuông góc giao nhau, một lần nữa áp dụng thao tác của chúng ta với chúng, v.v. Sau đó, ở một bước nào đó, chúng ta sẽ có được một bức tranh có các đường vuông góc rời nhau theo từng cặp, hoặc cuối cùng chúng ta sẽ có được một bức tranh có tổng độ dài tối thiểu có thể có của các đường vuông góc (vì tổng này chỉ có thể có một số giá trị hữu hạn; tại sao?). Hình ảnh này là một ngoại lệ: nếu hai đường vuông góc trên nó giao nhau, thì khi áp dụng lại thao tác của chúng ta, chúng ta sẽ có được một hình ảnh có tổng chiều dài của các đường vuông góc thậm chí còn nhỏ hơn.

Hãy cùng phân tích hai lời giải này. Chúng tôi đã hành động với chúng theo một sơ đồ: chúng tôi đã đưa ra một đại lượng nhất định (trong sơ đồ đầu tiên, bài toán là tổng của tất cả các số trong bảng và trong sơ đồ thứ hai, tổng độ dài của các đường vuông góc) và một phép toán, kết quả là đại lượng này thay đổi theo một cách nhất định: trong sơ đồ thứ nhất, bài toán tăng lên và trong sơ đồ thứ hai, giảm đi. Lời giải dựa trên thực tế là giá trị đã nhập chỉ có thể nhận một số hữu hạn các giá trị khác nhau. Do đó, thao tác này chỉ có thể được áp dụng với một số lần hữu hạn và chắc chắn chúng ta sẽ đi đến tình huống cần thiết trong bài toán.

Từ quan điểm này, bài toán thứ hai khó hơn lần đầu tiên, vì trong đó, chúng ta không chỉ phải tính đến số lượng mong muốn, sự thay đổi mà chúng ta phải theo dõi mà còn cả chính hoạt động đó.

Ngoài ra, bài toán thứ hai là một ví dụ tuyệt vời về mức độ dễ dàng có được một dấu vết sai: các đường vuông góc mới $AA_2$ và $BB_2$ không giao nhau, và do đó mỗi dấu vết chịu trách nhiệm về số điểm giao nhau của các đường vuông góc $n$ của chúng ta, mà thoạt nhìn, luôn giảm theo thao tác được mô tả. Tuy nhiên điều này không đúng (hãy xây dựng ví dụ cho phù hợp).

Việc học cách đưa ra cặp thao tác-số lượng cần thiết không còn dễ dàng nữa. Điều này đòi hỏi kinh nghiệm và trực giác.

Một đại lượng thay đổi đơn điệu và chỉ nhận một số hữu hạn các giá trị khác nhau sẽ được gọi là đại lượng nhận.

bài toán tiếp theo cũng có thể được phân loại là nổi tiếng.

Bài tập 3. Chứng minh rằng mọi điểm 2 $n$ trên mặt phẳng đều là điểm cuối của $n$ đoạn thẳng cắt nhau.

Chúng ta hãy vẽ các đoạn $n$ có điểm cuối tại các điểm này một cách tùy ý. Nếu không có hai trong số chúng giao nhau thì yêu cầu bài toán được thỏa mãn. Ngược lại, hãy xem xét một cặp phân đoạn giao nhau $AB$ và $CD$ (hình2). Như một ngoại lệ, điều tự nhiên là xem xét việc thay thế giao điểm của các đoạn $AB$ và $CD$ bằng giao điểm của các đoạn $AC$ và $BD$ .

Vẫn còn phải tìm giá trị kết quả - một đại lượng hoạt động đơn điệu trong quá trình hoạt động này. Vì tổng độ dài các đường chéo $AB$ và $CD$ của tứ giác lồi $ACBD$ lớn hơn

tổng độ dài các cạnh đối diện AC và BD; tổng độ dài của n đoạn có thể được coi là nửa biến thể. Rõ ràng là tổng này chỉ có thể nhận một số hữu hạn các giá trị. Lập luận theo cách tương tự như trong bài toán trước, chúng ta thu được một tập hợp gồm n đoạn có tổng độ dài tối thiểu. Dễ hiểu là không có hai đoạn nào giao nhau trong đó.

Trên thực tế, ở bài toán 3, lúc đầu không có hoạt động hay lệnh nửa vời. Tuy nhiên, một khi chúng ta đã chọn thao tác thì việc chọn một nửa biến thể không khó.

Bài toán 4. Có n số dọc theo hình tròn. Nếu có các số a, b, c và d thẳng hàng và (a-d)(b-c)>0 thì các số b và c bị cắt và hoán đổi cho nhau. Chứng minh rằng sau vài bước chúng ta không thể thực hiện được hoán vị nào như vậy.*)

Ở đây hoạt động thay thế số được đưa ra. Mặc dù thực tế là nó chỉ ảnh hưởng đến hai số, nhưng thật thuận tiện khi nhận thức thao tác này trên toàn bộ tập hợp số, vì phép toán này không thay đổi tất cả các số khác: xét cho cùng, theo “triết lý lời giải” của chúng tôi, cần phải chọn một giá trị neoctor tùy thuộc vào toàn bộ tập hợp số.

Vì vậy, đường đi của các số liên tiếp a, b, c và d sao cho (a-d)(b-c)>0, tức là ab+cd>ac+bd. Khi thực hiện phép tính, chúng ta chuyển từ bộ tứ a, b, c, d sang bộ tứ a, c, b, d và ta thấy tổng tích của các số lân cận đã giảm: ab+bc+cd>ac+cb+bd.

Bây giờ rõ ràng là nửa biến số trong bài toán này là tổng của các tích từng cặp của các số lân cận của toàn bộ tập hợp. Với thao tác này, nửa biến thể bị giảm đi và vì nó chỉ có thể nhận một số hữu hạn giá trị (tại sao?), nên thao tác của chúng ta chỉ có thể được áp dụng một số lần hữu hạn.

bài toán tiếp theo chúng tôi lấy từ cuốn sách của V.V. Prasolov “Bài toán trên cung thiên văn” (Phần 2, 21, 25).

Bài toán 5. Các thao tác sau được thực hiện với một đa giác nhỏ. Nếu nó nằm trên một phía của đường thẳng AB, trong đó A và B là các đỉnh không liền kề của đa giác, thì một trong những phần mà đường viền của đa giác được chia cho các điểm A và B sẽ được phản xạ đối xứng tâm so với phần giữa của đoạn AB. Chứng minh rằng sau vài phép tính như vậy đa giác trở nên lồi.

Vì vậy, thao tác được thực hiện lại - đây là phép biến đổi đa giác. Bán biến, tăng đơn điệu trong thao tác này, ở đây chúng ta có thể thấy rõ rằng tổng tích của các số lân cận đã giảm: ab+bc+cd>ac+cb+bd.

Bây giờ rõ ràng là nửa biến số trong bài toán này là tổng các tích cặp 相邻 của các số lân cận của toàn bộ tập hợp. Với thao tác này, nửa biến thể bị giảm đi và vì nó chỉ có thể nhận một số hữu hạn giá trị (tại sao?), nên thao tác của chúng ta chỉ có thể được áp dụng một số lần hữu hạn.

bài toán tiếp theo được đề xuất bởi vận động viên cổ điển thứ tám tại Olympic toàn Liên minh năm 1979. Nó chỉ được giải quyết bởi ba người tham gia.

Bài toán 6. Mỗi paramenta có không quá ba kẻ thù. Chứng minh rằng quốc hội có thể chia thành hai viện sao cho mỗi viện

một nghị sĩ ở cùng phòng với ông ta sẽ không có nhiều hơn một kẻ thù.*)

Hãy chia quốc hội thành các viện một cách tùy tiện. Nếu mỗi nghị viện có không quá một kẻ thù trong cùng một phường thì yêu cầu bài toán được đáp ứng. Nếu không, hãy xem xét một parlamentaria $A$ có ít nhất hai kẻ thù trong cùng một phường. Là một đa biến, hãy xem xét số lượng cặp kẻ thù nằm trong một buồng. Rõ ràng là bằng cách di chuyển phòng họp $A$ sang phòng khác, chúng tôi đã giảm con số này. Tất cả những gì còn lại là tạo ra cụm từ tiêu chuẩn: “Một đa biến chỉ có thể nhận một số giá trị hữu hạn”.

bài toán tiếp theo được đưa ra tại Thế vận hội Thành phố Moscow năm 1964. Nó khó đến mức không một người tham gia Olympic nào giải được nó.

Bài toán 7. Khi Vua Arthur gặp hai người, 2N hiệp sĩ tập hợp lại và mỗi người trong số họ có không quá $N-1$ kẻ thù trong số họ. Chứng minh rằng Merlin, cố vấn của Arthur, có thể xếp các hiệp sĩ vào Bàn tròn theo cách mà không ai trong số họ ngồi cạnh kẻ thù của mình.

Chúng ta sẽ sắp xếp các hiệp sĩ vào Bàn tròn một cách tùy ý. Nếu không có hai kẻ thù nào ngồi cạnh nhau thì yêu cầu bài toán được đáp ứng. Ngược lại, hãy xem xét hiệp sĩ $A$ ngồi bên trái kẻ thù của mình $B$ (hình 4, a).

*) Xem thêm bài toán M580 («Kvant», 1979, số 8).

Như trong bài toán trước, với tư cách là một đa biến (điều này được đề xuất bởi các điều kiện bài toán), chúng tôi xem xét số lượng các cặp kẻ thù lân cận. Chúng ta cần phải đưa ra một thao tác làm giảm con số này. Đây là phần khó nhất lời giải.

Trong số những người bạn của hiệp sĩ $A$ , bạn phải tìm một hiệp sĩ $C$ sao cho người hàng xóm bên phải của anh ta $D$ là bạn của hiệp sĩ $B$ (nếu không thì hiệp sĩ $B$ có nhiều hơn $N-1$ kẻ thù). Bây giờ, hãy “mở rộng” toàn bộ phần của từ từ $B$ đến $C$ (ở bên phải $B$ , hình 4, b) theo hướng “đảo ngược” (hình 4, b). Trong trường hợp này, hiệp sĩ $B$ sẽ trở thành hàng xóm của hiệp sĩ $D$ , hiệp sĩ $C$ sẽ trở thành hàng xóm của hiệp sĩ $A$ . Các cặp hàng xóm còn lại sẽ không thay đổi. Do đó, đa biến thực sự giảm.

Trong các bài toán liên quan đến thực tế đa biến, câu hỏi đặt ra là về thời gian mà quá trình đang xem xét kết thúc. Chúng tôi khuyên bạn nên phân tích tất cả bài toán đã được tháo rời theo quan điểm này. Bạn sẽ thấy rằng đây thường không phải là một câu hỏi dễ dàng. Chúng tôi sẽ chỉ đưa ra một ví dụ.

Bài toán 8. $N$ các số được viết ngẫu nhiên liên tiếp trên bảng, mỗi số bằng $+1$ hoặc $-1$ . Trong một lần di chuyển, bạn được phép đổi dấu của một số số liên tiếp. Hỏi có thể hoàn thành số bước di chuyển nhỏ nhất để có được một tập hợp đơn vị duy nhất từ tập hợp ban đầu là bao nhiêu?

Phép toán được trao cho chúng tôi và với tư cách là một đa biến, chúng tôi xem xét số lượng các cặp lân cận có dấu hiệu khác nhau. Khi thực hiện một thao tác thay thế ký tự, đa biến này có thể thay đổi không quá hai.

Hình 4.

Bây giờ chúng ta hãy chứng minh rằng từ tập hợp số -1, +1, -1, +1, … không thể thu được tập hợp số +1, +1, +1, … với ít hơn [(N+1)/2] bước. ([x] biểu thị phần nguyên của số x.) Khoảng cách của N ngẫu nhiên và lẻ riêng biệt. Đặt N=2k, tức là [(N+1)/2]=k. Khi đó lúc đầu kết quả bằng 2k - 1, còn lúc cuối kết quả phải bằng 0. Nhưng không thể thêm số lượng cần thiết trong k-1 nước đi.

Đặt N=2k+1, tức là [(N+1)/2]=k+1. Trong trường hợp này, mức tăng của tập ban đầu bằng 2k, do đó, trong k-1 nước đi, tập ban đầu không thể chuyển đổi hoàn toàn thành tập hợp chỉ có một. Hãy chứng minh rằng điều này không thể thực hiện được trong k bước đi. Để làm được điều này, chỉ cần thay thế ít nhất một lần giá trị kết quả sẽ thay đổi không quá một (điều này sẽ xảy ra khi thao tác thay thế các dấu hiệu ảnh hưởng đến một số cực trị -1).

Vẫn còn phải chứng minh rằng trong [(N+1)/2] nước đi người ta có thể thu được một tập hợp duy nhất từ bất kỳ tập hợp ban đầu nào. Chúng ta hãy chọn trong tập hợp ban đầu tất cả các nhóm trong một hàng số -1, không có nhiều hơn [(N+1)/2]. Bây giờ sau khi cộng ta hãy đổi dấu các số của các nhóm này.

Chuyển sang kết luận ban đầu bài toán về kẹo, chúng ta lưu ý rằng trong đó các giá trị 2a+b có thể được lấy làm đại lượng thu được, trong đó a là số kẹo ở đống đầu tiên và b là số kẹo ở đống thứ hai.

Tại nhà vợ

Trên mặt phẳng có 2N điểm, trong đó không có 3 điểm nào thẳng hàng. N trong số chúng được hiển thị bằng màu sặc sỡ, phần còn lại có màu xanh lam. Chứng minh rằng những điểm này có thể được nối bởi N đoạn thẳng rời nhau, mỗi đoạn sẽ nối điểm cực trị với màu xanh. («Kvant», 1975, số 1, bài toán M301.)
Có N điểm trên một mặt phẳng cho trước, những điểm không bị xoắn được nối với nhau bằng các đoạn thẳng. Được biết, không quá 11 đoạn kéo dài từ bất kỳ điểm nào. Chứng minh rằng các điểm này có thể khai triển thành bốn màu sao cho không quá N đoạn có một điểm cuối.
Một số chấm màu đỏ và một số chấm màu xanh được chỉ định. Một số trong số chúng được kết nối bởi các phân đoạn. Người ta biết rằng một điểm là đặc biệt nếu hơn một nửa số điểm nối với nó có màu khác với màu của nó. Nếu ít nhất một điểm cụ thể được chọn thì bất kỳ điểm cụ thể nào cũng được chọn và sơn lại bằng màu khác. Chứng minh rằng sau hữu hạn số bi sẽ không còn điểm kỳ dị nào. («Kvant», 1974, số 8, bài toán M277; Thế vận hội toàn năng, 1974)
Trên mỗi mặt của khối lập phương có một số được viết và không phải tất cả các số này đều giống nhau. Mỗi số được viết sẽ được thay thế bằng trung bình số học của các số được viết trên bốn mặt liền kề. Có thể nào sau một số thao tác như vậy, các số ban đầu sẽ xuất hiện trên tất cả các hạt?
N số tự nhiên được viết xung quanh một vòng tròn. Giữa hai số liền kề nhau viết ước số chung lớn nhất của chúng. Sau đó, các số trước đó sẽ bị xóa và thao tác tương tự được thực hiện với các số còn lại. Chứng minh rằng sau vài quả bóng thì tất cả các số trên hình tròn đều bằng nhau. (Thế vận hội thành phố Leningrad, 1973.)
Có 10 số được viết trên bảng: một và chín số không. Bạn được phép chọn bất kỳ số nào và thay thế mỗi số bằng giá trị trung bình số học của chúng. Số lớn nhất có thể xuất hiện ở vị trí số 1 sau một loạt các phép toán như vậy là bao nhiêu? (Thế vận hội thành phố Leningrad, 1984.)
Trên tờ giấy trắng ca rô dài vô tận, có nhiều hình vuông được sơn đen. Tại các thời điểm t=1, 2, 3, …, việc đổi màu đồng thời tất cả các ô của trang tính được thực hiện theo quy tắc sau: mỗi ô K lấy màu mà hầu hết ba ô có ở thời điểm trước đó: chính ô K và các ô lân cận ở bên phải và phía trên. Chứng minh rằng sau một thời gian không còn ô đen nào trên tờ giấy. (Thế vận hội toàn năng, 1973.)
Có vài bạn đứng thành vòng tròn, mỗi bạn có vài chiếc kẹo. Theo hiệu lệnh của người dẫn đầu, mọi người chuyển một nửa số kẹo của mình cho người đứng bên phải (nếu số kẹo là số lẻ thì người dẫn đầu sẽ thêm một viên kẹo cho người đó). Điều này được lặp đi lặp lại nhiều lần. Chứng minh rằng một ngày nào đó tất cả mọi người đều có số kẹo như nhau. (Thế vận hội thành phố Leningrad, 1983.)
Ở một bên của hành lang vô tận có vô số phòng, được đánh số theo thứ tự số nguyên và mỗi bên có một cây đàn piano. Một số lượng hữu hạn các pinastics sống trong những căn phòng này (một số pinastics có thể sống trong một phòng). Hàng ngày, có hai pinastic sống ở các phòng lân cận - phòng thứ k và (k+1) -th - đi đến kết luận rằng chúng gây nhiễu lẫn nhau và giao nhau trong phòng thứ (k-1) và (k+2)-th tương ứng. Chứng minh rằng sau hữu hạn ngày các giao lộ này sẽ dừng lại. («Kvant», 1984, số 6, bài toán M870.)
Trong thư viện, N tập bách khoa toàn thư Britannica được sắp xếp ngẫu nhiên trên kệ. Thủ thư robot thực hiện những việc sau mỗi phút: anh ta lấy một tập tùy ý không ở đúng vị trí của nó và đặt nó vào vị trí của nó (tức là, nếu số tập là k thì nó sẽ đặt nó vào thứ k trong một hàng). Chứng minh rằng sau một thời gian tất cả các tập sách vẫn ở nguyên vị trí của chúng. (Thế vận hội thành phố Leningrad, 1987.)