Tìm kiếm một bất biến

32

Yu. Ionin, L. Kurlyandchik

Ponsk
bất biến

Bài viết này xem xét bài toán, tương tự về công thức. Mỗi người trong số họ nói về một số bộ số hoặc dấu hiệu nhất định và chỉ ra những gì có thể thực hiện tùy ý đối với chúng. Người đọc đã nghiên cứu kỹ bài viết sẽ khám phá ra không chỉ sự giống nhau bên ngoài của bài toán và các bài tập trong đó mà còn cả ý tưởng chung làm cơ sở cho lời giải của chúng.

Bài toán 1. Mười mặt phẳng và mười lăm phút được viết trên bảng. Được phép xóa hai ký tự bất kỳ và viết chúng thẳng hàng với nhau nếu chúng giống nhau và ngược lại. Dấu hiệu nào sẽ vẫn còn trên bảng sau hai mươi phút hoạt động?

Lời giải. Hãy thay thế mỗi mặt phẳng bằng số 1 và mỗi phút bằng số -1. Phép toán được phép khi đó được mô tả như sau: lấy hai số bất kỳ và viết tích của chúng. Do đó, tích các số ghi trên bảng không thay đổi. Vì lúc đầu tích này bằng -1 nên đến cuối số sẽ vẫn là -1, tức là ký hiệu phút.

Lý do này có thể đã được thực hiện khác nhau. Chúng ta hãy thay thế tất cả các mặt phẳng bằng số 0 và số phút bằng số 1, khi đó tổng của hai số bị xóa có cùng tính chẵn lẻ với số được viết cùng nhau. Bởi vì

Lúc đầu, tổng của tất cả các số là số lẻ (bằng 15), sau đó số cuối cùng còn lại trên bảng sẽ là số lẻ, tức là một, và do đó, số phút sẽ vẫn còn trên bảng.

Cuối cùng, nhiệm vụ cần thiết có thể đạt được, sau đó, do mỗi thao tác, số phút không thay đổi hoặc giảm đi hai. Vì bài toán số phút là số lẻ nên cuối cùng sẽ còn số phút.

Hãy phân tích cả ba lời giải.

lời giải đầu tiên dựa trên tính bất biến của tích các số được viết, thứ hai - dựa trên tính bất biến của tính chẵn lẻ của tổng của chúng và tính thứ ba - dựa trên tính bất biến của tính chẵn lẻ của số phút. Trong toán học, thuật ngữ “bất biến” được sử dụng cùng với từ “bất biến”. Chúng ta có thể nói rằng trong mỗi lời giải chúng ta đã tìm được một bất biến: tích của các số được viết, tính chẵn lẻ của tổng, tính chẵn lẻ của số phút. Lời giải tiếp theo bài toán và các bài tập cũng dựa trên việc lựa chọn thành công một bất biến.

Bài tập 1. Một số mặt phẳng và phút được viết trên bảng. Được phép xóa hai dấu hiệu bất kỳ và viết chúng thẳng hàng với nhau nếu chúng khác nhau và ngược lại. Chứng minh rằng dấu cuối cùng còn lại không phụ thuộc vào thứ tự các trang được sắp xếp ngẫu nhiên.

Bài toán 2. Trong bảng 4×4, các dấu “+” và “—” được coi như trên Hình 1. Được phép đổi dấu ngược lại cùng lúc ở tất cả các ô nằm trong cùng một hàng, trong cùng một cột hoặc dọc theo đường thẳng song song với bất kỳ đường chéo nào (cụ thể là ô góc bất kỳ). Có thể sử dụng các thao tác này để có được một bảng không chứa phút nào không?

Lời giải. Hãy thay thế mặt phẳng và phút bằng số 1 và -1. Là một bất biến, chúng ta có thể lấy tích của các số trong các ô

33

krytse được tô bóng trong Hình 2, do kết quả của hoạt động được phép, nó luôn giữ giá trị ban đầu là -1.
Nhưng điều này có nghĩa là trong số các số được tô bóng sẽ luôn có -1, do đó, không thể có được một bảng không chứa một dấu trừ nào.

Bài tập 2. Giải bài toán 2 cho bảng Hình 3-5.

Bài toán 3*). Một số số không, số một và số hai được viết trên bảng. Cho phép xóa hai số không bằng nhau và viết cùng một số khác với số đã xóa (2 thay vì 0 và 1, 1 thay vì 0 và 2, 0 thay cho 1 và 2).
Chứng minh rằng nếu kết quả của một số thao tác như vậy chỉ còn lại một chữ số trên bảng thì nó không phụ thuộc vào thứ tự các con được sắp xếp ngẫu nhiên.

*) Đây là bài toán M338 từ “Bài toán Kvant, xem «Kvant», 1975, số 8.

Hình 1.
Hình 2.
Hình 3.

Lời giải. Chúng ta hãy biểu thị bằng $x_0, x_1, x_2$ số lượng số 0, số một và số hai tương ứng. Bằng cách thực hiện thao tác được phép một lần, chúng ta sẽ thay đổi từng số này thành 1 và do đó thay đổi tính chẵn lẻ của cả ba số. Khi còn lại một chữ số trên bảng, hai trong số $x_0, x_1, x_2$ trở thành số 0 và số thứ ba trở thành một. Điều này có nghĩa là ngay từ đầu, hai số trong số này có một số chẵn lẻ và số thứ ba có số chẵn lẻ khác. Do đó, bất kể thứ tự phân xử của các sterem là gì, cuối cùng đoàn kết chỉ có thể bằng một trong các số $x_0, x_1, x_2$, số này ngay từ đầu đã không giống như hai số còn lại.

Từ lời giải đã cho, rõ ràng là nếu các số $x_0, x_1, x_2$ có cùng tính chẵn lẻ thì chúng ta sẽ không thể đảm bảo rằng trên bảng chỉ còn một chữ số. Chứng minh rằng nếu các số $x_0, x_1, x_2$ vừa chẵn vừa lẻ, ngoài ra có ít nhất hai số khác 0 thì tồn tại thứ tự như vậy

Hình 4.
Hình 5.
Hình 6.

34

xóa đi, chỉ để lại một số trên bảng.

Hãy thay đổi điều kiện bài toán 3: ta yêu cầu xóa hai chữ số thần kinh giống nhau hai lần và viết một chữ số khác với số đã xóa. Giả sử sau một số thao tác nhất định chỉ còn lại một đơn vị trên bảng, dựa trên số số 0, số một và số hai, bạn có đoán được đây là số nào không?

Bốn lý do không giúp ích gì ở đây, nhưng mỗi phép toán dẫn đến một trong các số $x_0, x_1, x_2$ thay đổi tính chẵn lẻ của nó và hai số còn lại duy trì tính chẵn lẻ, do đó các số có các số chẵn lẻ khác nhau giờ đây có thể có cùng một tính chẵn lẻ. Tuy nhiên, bạn có thể nhận thấy rằng số dư khi chia các số $x_0, x_1, x_2$ cho 3 thay đổi mỗi lần sao cho số dư bằng nhau vẫn bằng nhau và số dư lo lắng vẫn lo lắng. Những khác biệt tiếp theo được lặp lại lời giải bài toán 3.

Bài toán 4. Mỗi ô của bảng $8 \times 8$ chứa một số nguyên. Bạn được phép chọn bất kỳ hình vuông nào có kích thước $3 \times 3$ hoặc $4 \times 4$ trong bảng và tăng thêm một tất cả các ô số trong hình vuông đã chọn. Có phải lúc nào cũng có thể sử dụng các thao tác như vậy để chuyển bảng gốc thành bảng có số chia hết cho 3 không?

Lời giải tức là Không, không phải lúc nào cũng vậy. Chúng ta hãy tìm tổng các số được ghi trong các ô được tô bóng trong Hình 6. Vì bất kỳ hình vuông có kích thước $4 \times 4$ nào cũng chứa 12 ô được tô bóng và một hình vuông có kích thước $3 \times 3$ chứa 6 hoặc 9 ô như vậy, nên kết quả của thao tác được mô tả, phần còn lại của phép chia cho 3 của tổng này (các số trong các ô được tô bóng) sẽ không thay đổi. Do đó, nếu ngay từ đầu tổng tìm được không chia hết cho 3 thì trong số các ô được tô bóng sẽ luôn có những ô trong đó các số được viết không phải là bội số của các số đó.

Độ pha loãng Y 3. Từ bất kỳ bảng nào, với điều kiện bài toán 4, có thể thu được một bảng không chứa các số chẵn?

Bài toán 5. Các số 1, 2, 3, …, $n$ được sắp xếp theo thứ tự nào đó. Được phép hoán đổi vị trí của hai số liền kề bất kỳ. Chứng minh rằng nếu thực hiện một số lẻ các phép toán như vậy thì chắc chắn bạn sẽ có được cách sắp xếp khác của các số 1, 2, 3, …, $n$ so với cách sắp xếp ban đầu.

Lời giải. Giả sử $a_1, a_2, ..., a_n$ là một hoán vị tùy ý của các số 1, 2, 3, …, $n$. Chúng ta sẽ nói rằng các số $a_i$ và $a_j$ hình thành sự đảo ngược trong hoán vị này nếu $i < j$ nhưng $a_i > a_j$, tức là số lớn hơn sẽ đứng trước số nhỏ hơn. Bằng cách hoán đổi hai số liền kề trong một hoán vị, chúng ta sẽ tăng hoặc giảm số nghịch đảo lên 1. Bằng cách thực hiện một số lẻ các thao tác như vậy, chúng ta sẽ thay đổi tính chẵn lẻ của số nghịch đảo và do đó thay đổi hoán vị.

Phép giãn Y 4. Chứng minh rằng mệnh đề bài toán 5 vẫn đúng nếu hai số bất kỳ trong hoán vị hoán đổi cho nhau.

U vạc tức là Chứng minh rằng hai số bất kỳ có thể hoán đổi cho nhau bằng cách thực hiện phép tính số lẻ được mô tả trong bài toán 5.

Sự chuyển đổi từ một hoán vị của các số 1, 2, 3, …, $n$ sang một hoán vị khác của các số này, trong đó hai số bất kỳ được hoán đổi và phần còn lại giữ nguyên vị trí, được gọi là chuyển vị. Kết quả bài tập 4 có thể hình thành như sau: thực hiện một số lẻ chuyển vị ta sẽ thay đổi được hoán vị.

Bài toán 6. Tại nhiều điểm khác nhau, số lượng súng máy cùng lúc theo một hướng được đánh dấu bằng 25 súng máy. Theo quy định, chúng có thể tự động bỏ qua nhau, nhưng việc bỏ qua hai lần đều bị cấm. Những chiếc xe được đón cùng một lúc tại cùng một điểm đã được đón. Chứng minh rằng trong zonka có số chỉ định chẵn.

Lời giải. Chúng tôi sẽ sơn một trong các máy màu vàng và phần còn lại sẽ được gán số tự động.

35

1, 2, 3, …, 24 theo thứ tự chúng nằm ở điểm xuất phát phía sau máy màu vàng. Ở giữa tác giả có cài đặt một thuộc tính bảng, trên đó sau mỗi lần vượt, chúng ta sẽ chỉ ra số lượng máy theo thứ tự đi theo máy màu vàng. Sau đó vượt, trong đó xe số tự động màu vàng không tham gia dẫn đến 2 số liền kề đổi chỗ trên đèn hiển thị.

Hãy xem điều gì sẽ xảy ra nếu có xe số tự động vượt xe màu vàng. Nếu trước đó vượt qua các số trên bàn tạo thành hoán vị $a_1, a_2, a_3, ..., a_{24}$ thì sau khi vượt qua chúng tạo thành hoán vị $a_2, a_3, ..., a_{24}, a_1$. Lưu ý rằng có thể đạt được sự sắp xếp lại tương tự bằng cách thực hiện 23 chuyển vị liên tiếp:

$$a_1, a_2, a_3, ..., a_{24} \rightarrow a_2, a_1, a_3, ..., a_{24}, a_1.$$

Nếu xe số tự động màu vàng vượt thì từ hoán vị $a_1, a_2, a_3, ..., a_{24}$ ta được hoán vị $a_{24}, a_1, a_2, a_3, ..., a_{24}, a_1.$

Sự chuyển đổi này cũng có thể được thay thế bằng hai số chuyển vị liền kề.

Do đó, việc vượt sẽ được giảm xuống số lượng chuyển vị lẻ. Nếu tổng số lần vượt là số lẻ thì tổng số lần chuyển vị cũng sẽ là số lẻ. Vẫn còn sử dụng kết quả kiểm soát 4.

Bài tập
5. Bốn số một và năm số không được viết theo thứ tự ngẫu nhiên xung quanh vòng tròn. Số 1 được viết giữa hai chữ số giống nhau và số 0 giữa các chữ số khác nhau, sau đó tất cả các chữ số gốc sẽ bị xóa. Có thể bằng cách lặp lại thao tác này nhiều lần để thu được một bộ chín số không?
6. Pete xé một mảnh giấy thành mười mảnh, một số mảnh lại xé thành mười mảnh, v.v. Liệu Pete có thể lấy được 1975 mảnh giấy bằng cách này không?
7. Trên bảng viết các số 1, 2, 3,…, 1975. Bạn được phép xóa hai số bất kỳ

và viết lại các số đã xóa, phần dư của tổng các số này cho 13. Sau một số thao tác nhất định trên bảng vẫn còn một số. Nó có thể là gì?

8. Mỗi số từ 1 đến 1.000.000 được thay bằng một số bằng tổng các chữ số của nó. Thao tác tương tự được thực hiện trên các số kết quả và việc này được thực hiện cho đến khi các số trở thành một chữ số. Những số nào dẫn đến số lớn hơn: một hoặc hai?
9. Từ một số có ba chữ số tôi sẽ tính các chữ số của nó. Với con số kết quả, họ bán cùng một thứ, v.v. - thế thôi. Số kết quả là gì?
10. Vòng tròn được chia thành 10 phần, mỗi phần chứa một số. Trong một lần di chuyển, bạn có thể di chuyển hai chip bất kỳ sang các khu vực liền kề, nhưng sao cho các chip di chuyển theo hướng ngược nhau. Có thể thu thập tất cả các chip trong một lĩnh vực không?
    11a). Ở trên cùng $A_{12}$ của 12 giác đúng $A_1A_2A_3...A_{12}$ đặt một điểm trừ và ở các đỉnh còn lại có các ô. Bạn được phép chọn bất kỳ ba đỉnh nào tạo thành một tam giác đều gián tiếp và thay đổi các dấu được viết ở các đỉnh này thành các đỉnh đối diện. Liệu với sự trợ giúp của các thao tác như vậy, liệu có thể đảm bảo rằng đỉnh $A_1$ có ​​điểm trừ và các đỉnh còn lại có đồ thị không?
    6). Kết quả của phép kiểm tra a) có được bảo toàn nếu chúng ta cho phép đổi dấu ở phần trên của bất kỳ tam giác đều nào, kể cả tam giác vuông? *).
11. Trong mỗi ô của bảng $4 \times 4$ một mặt phẳng được viết. Cho phép đổi đồng thời dấu sang dấu ngược lại ở tất cả các ô của một hàng hoặc một cột. Số trừ nhỏ nhất có thể đạt được khi bắt đầu từ một bảng nhất định được gọi là đặc số của bảng này. Một đặc tính có thể nhận những giá trị nào?
12. Có 30 quân chip xung quanh vòng tròn - 10 quân trắng và 20 quân đen. Được phép đổi chỗ cho hai chip bất kỳ, giữa đó có thêm ba chip nữa. Hai cách sắp xếp mã thông báo được cho là tương đương nếu một trong số chúng có thể được lấy từ cách kia bằng cách áp dụng thao tác đã chỉ định nhiều lần. Có bao nhiêu cách sắp xếp chip không bằng nhau?
13. Các số 1,2,3,…,1975 được viết theo thứ tự. Bạn được phép chọn bất kỳ số nào và đặt chúng vào những vị trí mà chúng chiếm giữ, nhưng theo thứ tự ngược lại. Có thể sử dụng các thao tác như vậy để đến được vị trí 1975, 1974, …, 3, 2, 1 không?

*) bài toán này được gửi đến «Kvant» bởi Vilayam Guseov, một học sinh lớp 10 tại trường số 3 ở Nakhivan.