công viên toán học

Bảo tàng toán học ngoài trời “Công viên toán học” là một bộ sưu tập các đồ vật nghệ thuật được tích hợp vào không gian đô thị để minh họa các sự kiện và khái niệm toán học. Mục tiêu của dự án là phổ biến toán học, khơi dậy niềm yêu thích và động lực nghiên cứu môn khoa học này ở trẻ em và người lớn. Một công viên toán học đã được thành lập tại thành phố Maykop, Cộng hòa Adygea, trên cơ sở Trường Toán học và Khoa học Cộng hòa (REMSH). Trong 20 năm qua, cô đã chuẩn bị cho những học sinh giỏi nhất của Cộng hòa Adygea đạt đến trình độ đoạt giải và đoạt giải Olympic toàn Nga ở nhiều môn học khác nhau. Khoảng 50 sinh viên tốt nghiệp hàng năm vào các trường đại học tốt nhất ở thủ đô. Những tấm thảm đỏ ở sân REMSH minh họa câu nói nổi tiếng bài toán về những cây cầu Königsberg, vọng lâu là một hình tam giác. Dải Möbius (xem trang 1 của bìa), là logo REMSH, được làm bằng dolomite. Trên một mặt của nó có khắc ba hình ảnh của những phát hiện khảo cổ học nổi tiếng thế giới được phát hiện trong các ụ chôn cất ở Adygea: một chiếc bình bằng bạc có phần cuối điêu khắc là hình con ngựa có cánh Pegasus, một tấm bảng bằng vàng có hình một con nai đang nằm, một tấm bảng vàng bảo vệ có hình con báo. Những phát hiện này cho thấy sự giàu có

di sản lịch sử và văn hóa của chúng ta ở Adygea. Hươu bay, được tìm thấy trong một gò đất ở thành phố Maykop, thuộc về nền văn hóa lâu đời nhất được biết đến tồn tại trên lãnh thổ nước Nga hiện đại (cuối thiên niên kỷ thứ 4 - giữa thiên niên kỷ thứ 2 trước Công nguyên). Nền văn hóa này được gọi là Maikop. Khối mười hai mặt là một trong năm khối đa diện đều trong không gian ba chiều.

Ý tưởng về tác phẩm điêu khắc thuộc về Asya Eutykh, thành viên của Liên minh Nghệ sĩ Nga, Nghệ sĩ Nhân dân Cộng hòa Adygea, và việc thực hiện là Tatyana Vaganova, nhà thiết kế, thành viên của Liên minh Nghệ sĩ Nga. Giải thích hình học cổ điển của định lý Pythagore, với hình vuông, hậu-

27

NHÂN VIÊN VẤN ĐỀ

TRÊN). Được biết, khi xác định được bất kỳ đứa trẻ nào, 99 đứa trẻ còn lại có thể chia thành 33 nhóm ba người sao cho trong mỗi nhóm cả ba đều là bạn của nhau theo cặp. Tìm số cặp trẻ em thân thiện nhỏ nhất có thể.

Đáp số: 198. Hãy dịch bài toán sang ngôn ngữ đồ thị, liên kết đứa trẻ với một đỉnh và tình bạn với một cạnh. Khi đó chúng ta biết rằng trong một đồ thị có 100 đỉnh, nếu bỏ đi một đỉnh nào đó thì các đỉnh còn lại có thể chia thành 33 bộ ba sao cho các đỉnh trong mỗi bộ ba được nối thành từng cặp. Điều cần thiết là tìm số cạnh tối thiểu có thể có trong đồ thị như vậy. Đầu tiên, hãy xây dựng một ví dụ có chính xác 198 cạnh. Hãy chia 99 đỉnh, trừ đỉnh A, thành 33 nhóm 3 đỉnh. Hãy nối các đỉnh trong mỗi bộ ba theo cặp; cuối cùng, kết nối A với tất cả các đỉnh khác. Khi đó các điều kiện bài toán được thỏa mãn: khi A bị xóa, phân vùng thành ba phần đã bị giảm và khi bất kỳ đỉnh B nào khác trong cùng phân vùng bị xóa thì chỉ cần thay B bằng A. Hơn nữa, trong biểu đồ được mô tả chỉ có 33 3 99 198 cạnh. Vẫn còn phải chứng minh rằng đại lượng này là nhỏ nhất. Gọi đồ thị có 3k + 1 đỉnh là tốt nếu khi loại bỏ bất kỳ đỉnh nào, 3k đỉnh còn lại được chia thành k bộ ba kết nối theo cặp. Chúng ta hãy chứng minh bằng quy nạp theo k rằng một đồ thị tốt có ít nhất 6k cạnh trên 3k + 1 đỉnh; với k = 33 chúng ta thu được ước lượng cần thiết. Cơ sở của k = 1 rất đơn giản: vì khi loại bỏ bất kỳ đỉnh nào, ba đỉnh còn lại được nối thành cặp, hai đỉnh bất kỳ phải được kết nối, tức là số cạnh là $C_{4}^{2} 6$. Hãy chứng minh sự chuyển tiếp của quy nạp. Nếu có ít nhất 4 cạnh đi ra từ mỗi đỉnh thì tổng số cạnh ít nhất là 3 k 1 4 2 2 3 k 1, thậm chí còn nhiều hơn yêu cầu 6k. Ngược lại, có một đỉnh A nối với nhiều nhất ba đỉnh khác. Nếu bạn loại bỏ bất kỳ đỉnh nào ngoại trừ A, thì A sẽ trở thành một loại bộ ba nào đó, có nghĩa là nó ít nhất được kết nối với nhau.

“QUANTA”

với hai đỉnh. Nếu một trong các đỉnh này bị loại bỏ thì A sẽ còn lại ít nhất hai đỉnh liền kề, tức là có ít nhất ba đỉnh trong số đó. Vì vậy, A được nối với chính xác ba đỉnh B, C và D. Sau đó, giả sử khi loại bỏ B, các đỉnh A, C và D tạo thành một bộ ba, tức là C và D được nối với nhau; tương tự ta thấy B, C và D được nối thành từng cặp. Bây giờ chúng ta hãy xóa các đỉnh A, B, C và D khỏi biểu đồ của mình và thay vào đó thêm một đỉnh X, được kết nối với tất cả các đỉnh mà ít nhất một trong các đỉnh B, C và D được kết nối. Lưu ý rằng trong trường hợp này số cạnh giảm ít nhất là 6 (tức là bằng số cạnh giữa A, B, C và D). Hãy để chúng tôi chứng minh rằng đồ thị mới thu được là tốt; từ đây sẽ diễn ra quá trình chuyển đổi quy nạp, vì khi đó đồ thị mới sẽ có ít nhất 6 k 1 cạnh, nghĩa là đồ thị ban đầu sẽ có ít nhất 6 k 1 6 6 k cạnh. Hãy loại bỏ một số đỉnh Y z X khỏi biểu đồ mới. Nếu bỏ nó khỏi đồ thị ban đầu thì các đỉnh còn lại sẽ bị chia thành các bộ ba; Đặt đỉnh A, để xác định, nằm trong bộ ba có B và C, và đỉnh D nằm trong bộ ba khác. Sau đó, bạn có thể chia đồ thị mới theo cách tương tự, đặt đỉnh X vào bộ ba nơi có đỉnh D. Cuối cùng, nếu bạn loại bỏ đỉnh X khỏi biểu đồ mới, bạn có thể thực hiện thao tác tương tự, giả sử rằng đỉnh D đã bị xóa khỏi biểu đồ ban đầu (khi đó A, B và C sẽ tự động nằm trong cùng một bộ ba). Như vậy, quá trình chuyển dịch cảm ứng đã được chứng minh. Lưu ý rằng ví dụ đưa ra trong bài toán không phải là ví dụ duy nhất. Lý luận từ phần thứ hai lời giải về cơ bản cho thấy rằng nhiều ví dụ tối ưu khác nhau có thể được xây dựng theo phương pháp quy nạp như sau. Với k = 1, lấy 4 đỉnh và nối tất cả các cặp với các cạnh. Khi chuyển từ k sang k + 1, chúng ta sẽ cộng ba đỉnh B, C, D, nối chúng theo cặp với nhau và cũng nối tất cả chúng với một số đỉnh A hiện có. Trong ví dụ như vậy sẽ luôn có 6k cạnh và nó sẽ thỏa mãn điều kiện bài toán. S. Berlov, N. Vlasova