Tổ hợp đầy màu sắc

18

đầy màu sắc
TỔNG HỢP
B.A. Korgemsky

Những buổi học đầu tiên của “lớp tổ hợp đầy màu sắc” thật đáng nhớ đối với mỗi chúng ta: trên giấy trắng - “bầu trời màu cam”, “lạc đà màu cam” và “mẹ màu cam”. Bước qua ranh giới của hình học tổ hợp “màu cam” dành cho trẻ em này, trí tưởng tượng toán học đã giới thiệu một bảng màu trong điều kiện bài toán, mang tính giải trí nhưng đồng thời nghiêm túc - bài toán về sự kết hợp của màu sắc và thẻ tô màu. Và trong một số vấn đề, hóa ra có thể sử dụng một cách sử dụng màu sắc khác: tô màu là một yếu tố lời giải, một đặc điểm riêng mang lại sự duyên dáng và ngắn gọn cho lý luận.

Đối với hình học tổ hợp, đây là một nhánh toán học non trẻ và đang phát triển. Các phương pháp của nó và đặc biệt là tô màu kết hợp với cái gọi là “nguyên tắc kiểm tra tính chẵn lẻ” của số phần liên kết đơn của một hình có thể hữu ích trong lời giải kỹ thuật bài toán tìm ra những cách tối ưu để khớp với các phần tiêu chuẩn. Dành một câu chuyện chi tiết hơn về vấn đề này cho tương lai, chúng ta hãy xem xét, “như một sự khởi động”, một số tổ hợp “đầy màu sắc” bận rộn bài toán.

Một mẹo: hãy làm theo nội dung của bài viết, mỗi lần cố gắng chuyển tác giả đến lời giải được đề xuất bài toán.

Sự kết hợp hai màu

Bài toán 1. Sáu thùy nằm trong không gian sao cho không có ba thùy nào nằm trên cùng một đường thẳng và không có bốn thùy nào thuộc cùng một mặt phẳng. Tất cả các điểm được kết nối theo cặp theo phân đoạn: xanh hoặc đỏ - theo ý của bạn. Cấu hình kết quả, chứa 15 đoạn ($C_6^2 = 15$), cũng chứa các hình tam giác. Có thể chọn phân bố màu tối đa cho các phân đoạn sao cho không hình thành một vùng duy nhất của tam giác một thanh không?

Những thử thách và cố gắng sẽ dẫn bạn đến kết quả tiêu cực đáp số. Nó cần phải được biện minh.

Lời giải. Chúng ta hãy chọn một trong sáu điểm tùy ý và ký hiệu nó bằng chữ A. Trong năm đoạn thẳng hội tụ tại A, có ít nhất ba đoạn cùng màu, vì chúng ta chỉ có hai màu; Hãy đánh dấu ba đoạn này và giả định chắc chắn rằng chúng có màu đỏ. Hãy xem xét ba đoạn nối các cặp đầu kia của các đoạn được đánh dấu. Không có đoạn nào trong số ba đoạn đang xem xét phải có màu đỏ, do đó không xuất hiện một hình tam giác, tất cả các cạnh của chúng đều có cùng màu. Nhưng rồi ba đoạn cuối cùng đều có màu xanh lam và chắc chắn tạo thành một hình tam giác một chiều.

Hãy thực hiện sàn gỗ

Bài toán 2. Hình 1 thể hiện phần bao phủ (napkem) của hình vuông $8 \times 8$ với 21 minimo phẳng ($3 \times 1$) và một monomino phẳng ($1 \times 1$). Chứng minh rằng vị trí xác định của khối là “monomino”

21

khối ferium. Liệu nó có thể đi qua tâm của tất cả các cốc và dừng lại ở khối trung tâm nếu con mối chỉ di chuyển song song với các cạnh của khối và đi qua mỗi khối một lần?

Một đồng tiền giả khác

“Một lần nữa” - theo nghĩa, có lẽ nhiều bạn đã quen thuộc với loạt bài bài toán về việc xác định một đồng tiền giả từ một loạt các đồng xu có cùng mệnh giá và loại bằng cách sử dụng số cân quy định trên cân cốc không có nấm. Tác giả của bài toán này không rõ; lời giải và nghiên cứu của họ bắt đầu xuất hiện trên các tạp chí toán học vào năm 1945.

Hãy để chúng tôi nhắc bạn rằng nếu không có thông tin về đồng xu giả (dù nặng hay nhẹ hơn đồng thật), thì ba lần cân là đủ để tách nó ra khỏi 12 đồng tiền đã cho, nhưng không đủ để tách nó ra khỏi 13. Nhưng…

Bài toán 9. Giả sử rằng ngoài 13 đồng xu, trong đó có một đồng giả (không biết nó nhẹ hơn hay mềm hơn), chúng ta có một đồng xu giả,

và cuộn dây. Màu sắc của nó như sau để mô tả nó so với những chiếc khác, nhưng không có sự thay đổi đáng chú ý nào về trọng lượng của chính nó. Chứng minh rằng trong trường hợp này có thể chọn ra một đồng xu giả từ 13 đồng xu đã cho bằng cách sử dụng ba lần cân trên một chiếc cân giả mà không cần đến nấm.

Đã giải quyết và e. Chúng ta biểu thị: 13 đồng xu thử nghiệm được đánh số từ 1-13, một đồng xu thật có màu bằng hình tròn ●, cốc bên trái và bên phải của cân tương ứng với chữ L và P, trạng thái cân bằng - L=P; đĩa cân bên trái hạ xuống L/R, đĩa cân bên phải hạ xuống - L/R.

“Chất xúc tác” toán học
Quá trình tăng tốc phản ứng hóa học với sự trợ giúp của chất phụ trợ - chất xúc tác không bị tiêu hao trong quá trình phản ứng - được gọi là kamaliz. Hãy để chúng tôi chỉ ra bằng một ví dụ rằng màu sắc có thể trở thành một loại “chất xúc tác” lời giải bài toán.

| Cân lần đầu | Cân lần thứ hai | | Đồng xu giả |
| :— | :— | :— | :— |
| đồng xu trên cốc | đồng xu trên cốc | đồng xu trên cốc | đồng xu trên cốc |
| L=P | L(10; 11) P(12; ●) | L(13); P(●) | {L/R L/R L/R L/R } | 13; nặng 13; nằm xuống 12; nằm xuống 10; heavy 11; heavy 12; nặng 11; nằm xuống 10; nằm xuống |
| trái/phải | L(1, 2, 6, 7, 8) P(9, 10, 11, 12, ●) | L(3); P(4) L(1); P(2) L(6); P(7) | {L=R L/R L/R L/R } | 5; nặng 3; nặng 4; heavy 9; lay down 1; heavy 2; heavy 8; lay down 6; lay down 7; nằm xuống |
| trái/phải | | | | |

Tìm hiểu điều gì là quan trọng nhất

22

Cơm. 9.

Bài toán 10. Xác định số lượng dừa tối thiểu mà năm thủy thủ đổ bộ lên đảo sau một vụ đắm tàu ​​có thể thu thập được, nếu họ chia số quả dừa như sau: người đầu tiên thu hoạch một quả martin và lấy $1/5$ một phần số quả còn lại; mạnh mẽ, lần lượt 4 thủy thủ còn lại cũng chấp nhận; Sau Emodo, lần thứ sáu, họ thu hoạch một hạt từ martynika và chia đều phần còn lại cho mình.

Trong một phiên bản được sửa đổi một chút, bài toán này đã được thảo luận trong bài viết của tác giả “Loài bài toán này đã hơn 1600 năm tuổi” («Kvant» Số 4, 1973).

Đại số lời giải dẫn đến một phương trình tuyến tính không xác định với các hệ số cồng kềnh, tuy nhiên, như đã trình bày trong bài viết đã đề cập, phương trình này có thể dễ dàng giải bằng phương pháp “so sánh modulo”. Nhưng bất kỳ ai đam mê toán học có thể sẽ hài lòng khi quay lại với bài toán này và, trình bày thêm, sẽ cố gắng tìm ra một mô hình lý luận mới, sử dụng như một “chất xúc tác” lời giải bài toán các hạt bổ sung, được sơn màu vàng (để phân biệt chúng với những hạt ban đầu).

M. Gardner trong cuốn sách “Câu đố toán học và giải trí” (Thế giới, 1971) lưu ý rằng “Tô màu như một phương pháp lời giải bài toán được Giáo sư N. Anning phát triển lần đầu tiên vào năm 1912. Nhiệm vụ của ông liên quan đến việc ba người chia táo cho nhau” (xem trang 238). Sau đó, M. Gardner chỉ ra cách áp dụng phương pháp của Anning cho lời giải bài toán về dừa.

Thật không may, đây là chỗ cuốn sách chứa đựng những tuyên bố sai lầm có thể phát sinh do bản dịch không chính xác.

Lời giải. Bài toán sẽ dễ giải quyết hơn nhiều nếu bạn không phải đưa hạt cho khỉ. Sáu lần tách $1/5$ các hạt khỏi đống, chúng ta sẽ để lại $4/5$, $(4/5)^2$, $(4/5)^3$, …, $(4/5)^6$ các hạt trong đống. Số hạt nhỏ nhất mà $(4/5)^6$ là số nguyên là $5^6$, vì nó phải chứa đa thức năm sáu lần.

Nhưng chúng ta vẫn cần đưa hạt cho khỉ, nên ngay cả số hạt ban đầu cũng không được giảm đi 5 hạt. Để làm cho nó chia hết cho 5, hãy thêm bốn hạt màu vàng vào đống. Hãy xem điều gì sẽ xảy ra.

Vì vậy, chúng tôi thêm bốn quả hạch màu vàng nữa vào đống hạt được các thủy thủ thu thập. Chúng ta sẽ chia đống này thành năm đống bằng nhau và chia lần lượt các hạt màu vàng thành bốn đống. Bốn thủy thủ đã chuẩn bị một đống hạt màu vàng, và một trong số họ đã chuẩn bị một đống trong đó tất cả các loại hạt đều là thật. Chúng ta hãy lấy ra một hạt từ đống: từ bốn - một hạt màu vàng, và từ hạt cuối cùng - một hạt thật. Các thủy thủ sẽ nhận được phần hạt bằng nhau, con khỉ sẽ được một hạt, còn bốn quả màu vàng để lại. Mọi thứ diễn ra theo điều kiện bài toán.

Bây giờ, theo điều kiện, một nhóm bốn thủy thủ lại với nhau và cộng thêm bốn hạt còn lại. Theo điều kiện, đống này