Kvant 2014, số 4 · Trang

2

KVANT 2014/№4

Đỉnh từ tính bay lên

A.PANOV

Chúng ta hãy định nghĩa sự bay lên là sự lơ lửng tự do của các vật thể trong không khí. Chúng tôi sẽ xem xét sự bay lên từ trường độc quyền. Thật vậy, nam châm dường như là ứng cử viên phù hợp. Để làm cho một vật bay lên, bạn cần phải bù lại trọng lực bằng cách nào đó. Và các nam châm đặt đối diện nhau cùng cực thì đẩy nhau. Nếu bạn đặt chúng ở một khoảng cách nhất định so với nhau, thì lực đẩy từ sẽ có khả năng cân bằng lực hấp dẫn và nam châm phía trên sẽ lơ lửng phía trên nam châm phía dưới. Nhiều người đã cố gắng hành động theo cách tương tự, nhưng không có kết quả. Các nam châm bằng cách nào đó xoắn lại trong không khí, hóa ra là các cực đối diện nhau và bị hút. Và đó là sự kết thúc của nó - không có sự bay lên. Việc thay thế nam châm đẩy bằng toàn bộ hệ thống nam châm nằm trên mặt phẳng hoặc trong không gian cũng không giúp ích được gì - và trong trường hợp này không thể đạt được sự lơ lửng. Dường như việc bay lên là không thể. Và đã có sự xác nhận lý thuyết mạnh mẽ về điều này.

Định lý Earnshaw - sự không thể bay lên

Hãy bắt đầu với một trích dẫn kép của Geim-Berry từ bài viết “Từ tính cho mọi người” của Andrei Geim (http:// www.physics.umd.edu/grt/taj/411c/Mọi người Magnetism.pdf, http://www.scientific.ru/journal/ Translations/magn_ed.html): “Ví dụ, hãy thử làm cho một vật thể từ tính bay lên. Tất nhiên, bạn có thể dễ dàng nâng nó lên bằng một nam châm hình móng ngựa, nhưng bạn không thể làm cho nó treo lơ lửng với bất kỳ cấu hình thông minh nào của nam châm Để hiểu những gì đang diễn ra ở đây, chúng ta cần nhớ định lý Earnshaw, định lý này (được Michael Berry trình bày lại gần đây) phát biểu rằng không có vật thể đứng yên nào gồm có điện tích, nam châm và khối lượng có thể lơ lửng trong không gian bởi bất kỳ sự kết hợp cố định nào của lực điện, lực từ và lực hấp dẫn." Định lý này đã được chứng minh bởi linh mục, nhà toán học và nhà vật lý người Anh Samuel Earnshaw vào năm 1842. Nó có công thức đơn giản, cách chứng minh hay và được mọi nhà vật lý biết đến. Nhiều nhà vật lý coi đây là lệnh cấm tuyệt đối đối với lực bay từ trường, nhưng hóa ra vẫn có những cách giải quyết.

Một thí nghiệm đơn giản Hãy bắt đầu với một thí nghiệm đơn giản, thoạt nhìn không khác gì một sự mô phỏng lại hiện tượng bay lên từ trường. Ở hình 1, bạn có thể thấy hai nam châm được xâu thành chuỗi trên một thanh gỗ - một là neodymium, một là ferit, nhưng điều này vẫn chưa quá quan trọng. Điều chính là các nam châm quay về phía nhau bằng các cực giống nhau và đẩy nhau - cái trên treo phía trên cái dưới. Tại sao điều này không thể được gọi là bay lên? Nhưng vì việc treo này không tự do - chuyển động tự do của nam châm phía trên bị một thanh gỗ ngăn cản. Có mâu thuẫn ở đây với định lý Earnshaw không? Không, vì ngoại trừ Hình1. Nam châm trên một thanh Lực từ và lực hấp dẫn Nam châm phía trên chịu tác dụng của lực đàn hồi phát sinh khi nó tương tác với một thanh gỗ. Nhưng nó không tệ đến thế. Hãy tiếp tục phân tích thí nghiệm của chúng tôi. Độ cao mà nam châm trên cùng treo là độ cao mà tại đó lực hấp dẫn và lực từ tác dụng lên nó cân bằng. Chúng tôi sẽ không tháo nam châm trên cùng ra khỏi thanh mà sẽ đặt nó ở độ cao này theo chiều ngang và thả ra. Dễ dàng nhận thấy trong trường hợp này thế năng của nam châm sẽ giảm không phải do rơi thẳng đứng mà do nó quay trong từ trường. Nếu không có thanh gỗ, nam châm phía trên sẽ quay $180\infty$ - với cực đối diện của nó với nam châm phía dưới - và bị hút vào nó. Cây đũa phép ngăn chặn điều này. Nếu có thể thay thế cây gậy bằng thứ gì đó ít vật liệu hơn mà vẫn ngăn được sự quay thì có lẽ vấn đề bay lên sẽ được giải quyết. Hóa ra hiệu ứng con quay hồi chuyển có thể giúp ích cho việc này. Chính sự xoắn của vòng nam châm quanh trục có thể ngăn nó bị lật và rơi thêm. Đây là ý tưởng chính của kiểu bay lên mà chúng ta đang thảo luận. Nhưng trước hết, việc thực hiện nó không hề dễ dàng. Và thứ hai, như đã có

7

LIÊN HỆ

Bằng cách này, chúng ta hiểu được một tập hợp các ô mà bọ cánh cứng có thể di chuyển qua đó mà không cần bò qua diêm). Rõ ràng là bằng cách loại bỏ sự trùng khớp, chúng ta có thể hợp nhất không quá hai vùng thành một, tức là. Chúng ta hãy giảm số lượng vùng không quá một. Chúng tôi sẽ cần ít nhất 63 sự hợp nhất, có nghĩa là chúng tôi cần loại bỏ ít nhất 63 kết quả phù hợp. Dưới đây là một ví dụ (hình5): hãy xóa tất cả các kết quả khớp ngang bên trong và tất cả các kết quả khớp dọc bên trong ở ngang dưới cùng - tổng cộng chính xác là 63 kết quả khớp. Bài toán đã giải quyết.

Định lý kết nối đồ thị

Giải pháp bài toán 1 và 2 có điểm gì chung? Ở đây và ở đó đều có những vật thể khác nhau (quả bóng, ô) mà chúng tôi kết hợp thành các nhóm (khu vực) và chìa khóa của lời giải là ý tưởng theo dõi số lượng các nhóm (khu vực) đó. Trong cả hai bài toán đều có mối liên hệ giữa các cặp đối tượng: một cạnh của khối lập phương nối một cặp đỉnh, một que diêm đóng vai trò là ranh giới giữa một cặp ô lân cận. Các kết nối ở đây rất rõ ràng và điều này làm cho chúng dễ đếm hơn. Để tránh lặp lại cùng một lý luận trong các tình huống khác nhau, nếu có thể, các nhà toán học đưa ra các khái niệm tổng quát. Các cấu trúc trong đó có các kết nối giữa các cặp đối tượng được gọi là đồ thị. Biểu diễn trực quan của đồ thị như sau: một hệ thống các điểm được mô tả - các đỉnh của đồ thị, trong đó một số cặp đỉnh được nối với nhau bằng các đường thẳng - các cạnh của đồ thị. Trong trường hợp này, việc các đỉnh nằm ở đâu trên mặt phẳng hoặc các cạnh trông như thế nào không quan trọng - ở dạng đoạn thẳng hoặc đường cong. Khi vẽ đồ thị, chúng ta cũng không chú ý đến giao điểm có thể có của các cạnh tại các điểm không phải là đỉnh. Bạn có thể tạo một mô hình đồ thị từ các nút-đỉnh và các cạnh luồng. Bằng cách đặt một mô hình như vậy lên bàn hoặc gây nhầm lẫn cho nó theo bất kỳ cách nào, chúng tôi không thay đổi biểu đồ. Trong một mô hình được tạo thành từ các nút và ren, các phần được kết nối - các thành phần - có thể nhìn thấy rõ ràng: mô hình có thể được chia thành các thành phần như vậy mà không làm đứt các sợi. Hãy nói nghiêm túc hơn về khả năng kết nối trong biểu đồ. Một đồ thị được gọi là liên thông nếu từ bất kỳ đỉnh nào của nó, người ta có thể đến bất kỳ đỉnh nào khác bằng cách di chuyển dọc theo các cạnh (tức là di chuyển nhiều lần từ đỉnh này sang đỉnh khác dọc theo một cạnh). Cho đỉnh A cố định trong đồ thị tùy ý. Chúng ta gọi tập hợp các đỉnh có thể đi tới từ một đỉnh A cho trước bằng cách di chuyển dọc theo các cạnh là thành phần liên thông của đỉnh A và ký hiệu nó là K ( A ). Trong trường hợp này, giả sử rằng chính đỉnh A được bao gồm trong thành phần K(A). Nếu bạn có thể đi từ đỉnh A đến đỉnh B bằng cách di chuyển dọc theo các cạnh thì các thành phần liên thông K(A) và K(B) trùng nhau, nếu không chúng không có đỉnh chung (chứng minh đi!). Như vậy, nhiều

Hình 6

VỚI

ĐẾM

Tập hợp tất cả các đỉnh của đồ thị được chia thành các thành phần liên thông (cụ thể, tập hợp các đỉnh của đồ thị liên thông đại diện cho một thành phần). hình 6 hiển thị ví dụ về biểu đồ chỉ có 4 thành phần được kết nối. Chúng ta hãy chú ý đến thực tế là một thành phần cũng có thể bao gồm một đỉnh cô lập. Chúng ta hãy xây dựng một định lý kết nối quan trọng và được sử dụng thường xuyên. Định lý. 1. Cho một đồ thị liên thông có n đỉnh. Khi đó nó có ít nhất n – 1 cạnh. 2. Cho một đồ thị có n đỉnh được chia thành k phần tử liên thông. Khi đó nó có ít nhất n – k cạnh. Bằng chứng. (Nó thực sự tái tạo lý do từ lời giải mà chúng tôi đã phân tích bài toán.) Hãy xóa tất cả các cạnh trong biểu đồ. Khi đó tất cả các đỉnh của nó sẽ bị cô lập, tức là đồ thị sẽ chia thành n thành phần liên thông. Hãy bắt đầu khôi phục từng xương sườn một. Mỗi cạnh được vẽ sẽ kết nối hai thành phần được kết nối thành một hoặc không thay đổi phân vùng thành các thành phần theo bất kỳ cách nào. Như vậy, việc khôi phục một cạnh có thể giảm số lượng thành phần không quá 1. Do đó, để giảm số lượng thành phần từ n xuống k, cần phải thực hiện ít nhất n – k cạnh. Cụ thể, để tạo một đồ thị liên thông (tức là làm cho k = 1) cần vẽ ít nhất n – 1 cạnh. Chúng ta hãy thử quay lại bài toán 1 và 2 một lần nữa và phân tích xem định lý kết nối liên quan đến chúng như thế nào. Hình ảnh trên hình 1 gần như trùng khớp với cách thể hiện trực quan của đồ thị và ngay lập tức theo định lý rằng để duy trì khả năng kết nối thì phải để lại ít nhất 7 cạnh. Hình ảnh có các kết quả trùng khớp trên hình 4 cũng là hình ảnh của biểu đồ, nhưng không phải là hình ảnh cần thiết cho lời giải bài toán. Và không có gì đáng ngạc nhiên: xét cho cùng, để tạo ra sự kết nối giữa các ô, chúng ta sẽ loại bỏ phần khớp! Hãy để chúng tôi mô tả biểu đồ chúng ta cần. Hãy đặt các đỉnh ở tâm của các ô (tổng cộng 64 đỉnh) và sử dụng một cạnh để kết nối các cặp tâm của các ô lân cận nếu không có sự trùng khớp trên đường viền giữa chúng. Xem xét đồ thị như vậy, chúng ta rút gọn hoàn toàn bài toán về tình huống được mô tả trong định lý. Có lẽ ý tưởng đếm số vùng được thấy rõ hơn trong bài toán về sự trùng khớp (và lời giải của nó trông còn đơn giản hơn so với việc chứng minh định lý).

Bài tập 1. Thanh sô cô la $4 \times 6$ được chia rãnh thành 24 ô vuông. Trong một lần di chuyển, bạn có thể bẻ gãy bất kỳ quân cờ nào ở bất kỳ vị trí nào và theo bất kỳ hướng nào, nhưng luôn dọc theo các rãnh. Số lần ngắt nhỏ nhất có thể được sử dụng để tách hoàn toàn một thanh sô cô la thành các thanh là bao nhiêu? 2. Giải bài toán2 với giả định rằng có thể loại bỏ các đường biên phù hợp và con bọ có thể bò ra khỏi bảng (nhưng con bọ chỉ muốn có thể đi qua tất cả 64 ô vuông). Gợi ý. Chúng ta có thể giả sử rằng lúc đầu chúng ta có 65 khu vực, bao gồm cả khu vực bên ngoài. 3. Cho một đồ thị liên thông có n đỉnh và k cạnh,

8

KVANT 2014/№4

trong đó k > n – 1. Chứng minh rằng bạn có thể loại bỏ một cạnh để đồ thị vẫn liên thông. Gợi ý. Bạn có thể sử dụng thủ thuật mà chúng tôi đã thấy: trước tiên hãy loại bỏ tất cả các cạnh rồi khôi phục từng cạnh một.

Theo Bài tập 3, bạn luôn có thể thu được các ví dụ trong bài toán 1 bằng cách cắt lần lượt 5 cạnh, chỉ quan tâm đến việc duy trì kết nối.

Bài tập 4 (D. Khramtsov, Olympic toàn Nga, giai đoạn cấp huyện, 1998). Một khối lập phương có cạnh $n \ge 3$ được chia thành các khối đơn vị bằng các vách ngăn. Số vách ngăn tối thiểu giữa các hình khối phải được loại bỏ để có thể chạm tới ranh giới của hình khối từ mỗi hình khối là bao nhiêu?

Đồ thị phụ trợ bất thường

Các tình huống điển hình có thể dễ dàng mô tả bằng ngôn ngữ đồ thị rất rõ ràng: đó là những thành phố và những con đường (hãng hàng không) kết nối chúng, những người gặp nhau trong một công ty nào đó… Tiếp theo chúng ta sẽ xem xét bài toán, trong đó việc sử dụng đồ thị (và cụ thể là định lý kết nối) không quá rõ ràng nhưng rất hiệu quả. Gợi ý về việc sử dụng biểu đồ trong lời giải của cái này hay cái khác bài toán có ​​thể là kết nối giữa các cặp đối tượng hoặc thậm chí chỉ là một tập hợp các cặp đã chọn. Bài toán 3 (dựa trên bài toán của I. Raskina). Có m người hâm mộ: một số người trong số họ (có thể là tất cả hoặc không ai) ủng hộ Spartak, số còn lại ủng hộ Dynamo. Bạn được phép hỏi hai người bất kỳ xem họ có ủng hộ các đội khác nhau hay không và họ sẽ thành thật trả lời “có” hoặc “không”. Cần đặt người hâm mộ trên hai xe buýt để mỗi chiếc chỉ chở người hâm mộ của một đội. Điều này có thể được thực hiện với số lượng câu hỏi tối thiểu là bao nhiêu? Đáp số: m – 1. Lời giải. Ví dụ. Nếu bạn đặt câu hỏi cho người thứ nhất và thứ hai, thứ nhất và thứ ba, …, thứ nhất và m, thì sẽ dễ dàng có chỗ ngồi: những người trả lời “có” sẽ được đưa lên xe buýt cùng với người thứ nhất, và những người còn lại - trên một chiếc xe buýt khác. Cấp. Bây giờ hãy xem xét một tình huống trong đó không quá m – 2 câu hỏi được hỏi. Hãy xây dựng một biểu đồ câu hỏi: các đỉnh tương ứng với các fan và các cạnh kết nối các cặp fan được hỏi câu hỏi. Đồ thị của chúng ta có m đỉnh và không quá m – 2 cạnh, có nghĩa là theo định lý kết nối thì nó không được kết nối. Nhưng liệu từ một biểu đồ không liên kết có thể hiểu được cách phân chia quạt một cách chính xác không? Hãy xem xét một trong các thành phần được kết nối A. Tập A được chia thành hai tập con A¢ và A¢¢ (quạt Spartak và quạt Dynamo tương ứng). Tương tự, thành phần B được kết nối được chia thành các tập con B¢ và B¢¢. Các quạt từ bộ A¢ cần được đặt trên một trong các bus, nhưng không biết nên thêm tập hợp con B¢ và B¢¢ nào vào chúng. Trên thực tế, nếu nhóm B¢ trở thành người hâm mộ của “Dynamo” và B¢¢ - của “Spartak”, họ sẽ đưa ra câu trả lời giống hệt nhau cho tất cả các câu hỏi được đặt ra cho họ

giống nhau đáp số (tất cả các câu hỏi đều được hỏi bên trong thành phần được kết nối). Và cách sắp xếp chỗ ngồi lẽ ra phải khác. Điều này có nghĩa là việc sắp xếp chỗ ngồi không thể được khôi phục rõ ràng dựa trên các câu trả lời.

Bài tập 5 (I. Raskin, Giải đấu A.P. Savin, 2011). Giải bài toán trước nếu bạn biết thêm rằng m = 2n và có chính xác n người ủng hộ Spartak và n ủng hộ Dynamo.

Chúng ta hãy xem thêm một vài bài toán về hình ca rô. Trong bài toán tiếp theo, như trong bài toán 2, một biểu đồ minh họa vùng lân cận của các ô sẽ giúp chúng ta. Bài toán 4. Một đa giác có diện tích n ô được vẽ trên giấy ca rô. Phác thảo của nó theo các đường lưới. Chu vi lớn nhất của đa giác là gì? (Cạnh của ô là 1.) Đáp số: 2n + 2. Lời giải. Ví dụ. Hình chữ nhật n ¥ 1. Ước tính. Tổng chu vi của n ô là 4n. Từ các chu vi này, chu vi của đa giác và tổng gấp đôi chiều dài của các đoạn lưới bên trong đa giác được cộng lại: xét cho cùng, các ô nằm liền kề với từng đoạn bên trong ở cả hai phía. Để ước tính tổng chiều dài của các đoạn bên trong, ta xây dựng đồ thị: các đỉnh là các ô của hình chữ nhật, các cạnh nối các ô với một cạnh chung. Biểu đồ này được kết nối: quân xe có thể di chuyển tự do giữa tất cả các ô bên trong đa giác. Theo định lý, đồ thị có ít nhất n – 1 cạnh, tức là tổng chiều dài các đoạn trong ít nhất là n – 1. Nhưng khi đó chu vi của đa giác không quá 4 n - 2 ( n - 1 ) = 2 n + 2. Nhận xét. Tất nhiên, ước tính này cũng có thể được chứng minh bằng quy nạp về số lượng tế bào. Nhưng một phát biểu quy nạp phải được xây dựng một cách khéo léo. Trong lớp học vòng tròn toán học, nhiều học sinh đã cố gắng dựa vào câu lệnh có vẻ hiển nhiên (và thực tế là gần với bài tập 3): “có thể thu được một đa giác từ ô thứ (k + 1) bằng cách cộng một ô với một số đa giác từ k ô,” nhưng các em chưa bao giờ chứng minh được điều đó… Lưu ý rằng trong nhiều bài toán, việc xây dựng một “đồ thị kép” tổng quát hơn là hữu ích, khi các vùng trong một số “bản đồ” trên mặt phẳng được khai báo là các đỉnh và nếu hai vùng đỉnh có một phần chung của đường viền thì chúng được kết nối với nhau bằng một cạnh.

Bài tập 6 (A. Shapovalov, Giải đấu A.P. Savin, 2009). Một ngàn hình được vẽ trên giấy ca rô với các cạnh dọc theo ranh giới của các ô. Số lượng tế bào nhỏ nhất có thể chứa là bao nhiêu?

Bài toán 5 (Giải đấu X của các thành phố). Tờ vở được sơn 23 màu trong các ô (có tất cả các màu). Một cặp màu được gọi là tốt nếu có hai ô liền kề được tô bằng các màu này. Số lượng cặp tốt tối thiểu là bao nhiêu? Đường dẫn đến lời giải. Trong số tất cả các cặp màu có thể có, những cặp màu tốt sẽ được làm nổi bật rõ ràng. Đây là một gợi ý về khả năng xây dựng một biểu đồ “màu sắc” và ước tính số cạnh trong đó! Đáp số: 22 cặp.

LIÊN HỆ

Lời giải. Ví dụ. Không khó để xây dựng một ví dụ với 22 cặp màu tốt. Ví dụ: thu được 22 cặp tốt nếu “đảo” của mỗi màu trong số 22 màu còn lại nổi trên “biển” của màu đầu tiên. Ở đây, các cặp màu tốt chính xác là những cặp có màu đầu tiên. Cấp. Hãy chứng minh rằng không thể có ít hơn 22 cặp tốt. Hãy xem xét biểu đồ G sau: với mỗi màu, chúng ta liên kết một đỉnh của biểu đồ (tổng cộng 23 đỉnh), với mỗi cặp màu tốt, chúng ta nối các đỉnh tương ứng với một cạnh. Nếu ta chứng minh đồ thị Γ liên thông thì theo định lý kết nối nó sẽ có ít nhất 22 cạnh. Chúng ta lấy G bất kỳ cặp đỉnh hoa A, B nào và trên tờ vở chúng ta sẽ đánh dấu ô K màu A và ô L màu B. Chúng ta sẽ di chuyển, bắt đầu từ ô K, đến các ô liền kề và sau một vài lần di chuyển chúng ta sẽ đến ô L. Theo chuyển động dọc theo tờ vở, chúng ta sẽ di chuyển dọc theo các đỉnh của đồ thị G: nếu ở bước tiếp theo chúng ta di chuyển từ ô M màu C sang ô N liền kề có màu D khác, thì trong đồ thị G chúng ta đi từ đó đỉnh C đến đỉnh D (C và D được kết nối bằng một cạnh, vì các ô M và N liền kề nhau); nếu màu của ô không thay đổi thì ở cột D chúng ta giữ nguyên. Đây là cách chúng ta có được trong đồ thị G một đường đi dọc theo các cạnh từ đỉnh A đến đỉnh B. Điều này chứng tỏ tính liên thông của đồ thị G.

Bài tập 7. Các ô vuông trên bàn cờ được sơn đúng 33 màu. Chúng ta sẽ gọi một cặp có màu khác nhau là tốt nếu có thể đặt một cặp hiệp sĩ đánh nhau trên các ô vuông có màu này. Tìm số lượng cặp tốt nhỏ nhất có thể. Gợi ý. Ở đây chúng ta không quan tâm đến các cặp ô lân cận mà là các cặp ô, từ ô này hiệp sĩ có thể di chuyển sang ô khác.

Bài toán 6 (S. Tokarev). Cho một hình chữ nhật ca rô m ¥ n. Mỗi ô của nó được cắt dọc theo một trong các đường chéo. Số phần nhỏ nhất mà một hình chữ nhật có thể chia thành là bao nhiêu? Đáp số: m + n. Lời giải. Ví dụ. Có thể thực hiện các đường cắt song song ở tất cả các ô (hình7), khi đó số phần sẽ là m + n. Cấp. Hãy thực hiện một vết cắt trong mỗi ô

Hình 7

Hình 8

dọc theo một trong các đường chéo. Hãy xây dựng một biểu đồ: các đỉnh sẽ tương ứng với các hình tam giác - một nửa số ô bị cắt và chúng ta sẽ vẽ một cạnh giữa các đỉnh nếu các hình tam giác tương ứng có một cạnh chung. Không khó hiểu khi mỗi phần mà hình chữ nhật được chia thành tương ứng với một thành phần liên thông của biểu đồ của chúng ta (ví dụ: tại hình 8). Số đỉnh bằng gấp đôi số ô, tức là 2mn. Số cạnh bằng số ranh giới giữa các cạnh lân cận

VỚI

ĐẾM

9 ô, tức là m ( n - 1 ) + n ( m - 1 ) = 2 mn - ( m + n ).

Theo định lý, số thành phần liên thông trong đồ thị như vậy không nhỏ hơn m + n.

Bài tập 8 (I. Akulich, Giải đấu các thành phố XXIV). Số ô vuông lớn nhất trên một bảng 9 ¥ 9 có thể được cắt dọc theo cả hai đường chéo mà bảng không bị vỡ là bao nhiêu? Gợi ý. Xây dựng một đồ thị có các đỉnh là toàn bộ ô hoặc một phần tư ô bị cắt (số đỉnh trong biểu đồ phụ thuộc vào số lượng ô bị cắt).

Bài tập cuối cùng rất thú vị vì đồ thị phụ trong đó có thể được xây dựng theo nhiều cách. Nhân tiện, đáp số còn lâu mới rõ ràng. Bây giờ chúng ta hãy cho lời giải bài toán M2339 “Bài toán Kvant. Bài toán 7 (V.Mokin, bài toán M2339, tổng quát hóa bài toán M1295). Cho một bảng $m \times n$, được chia thành các ô đơn. Đầu tiên, một con chip được đặt trong ( m - 1 ) ( n - 1 ) + 1 ô. Giả sử tại một thời điểm nào đó có bốn ô. các ô trên bảng, tâm của chúng là các đỉnh của một hình chữ nhật có các cạnh song song với các cạnh của bảng, sao cho có đúng một trong các ô này chứa một con chip; khi đó con chip này có thể bị loại bỏ. Chứng minh rằng không thể loại bỏ ít nhất một con chip khỏi bảng bằng cách chỉ thực hiện các thao tác được mô tả Lời giải Hãy xây dựng một biểu đồ: các đỉnh là dọc và ngang, có tổng cộng m + n. mn - ( m - 1 ) ( n - 1 ) - 1 = = m + n - 2 ô tự do, tức là số cạnh nhỏ hơn m + n – 1. Theo định lý, đồ thị của chúng ta không liên thông. Ô tại giao điểm của chiều ngang h và chiều dọc v sẽ được ký hiệu là (h, v), và nếu ô này tự do thì (h, v) cũng sẽ biểu thị cạnh từ h đến v. Điều gì xảy ra khi tháo chip ra như mô tả trong điều kiện? Cho bốn tâm của ô nằm ở các đỉnh của hình chữ nhật tại giao điểm của các đường ngang p, q và các đường thẳng đứng r, s và lấy đi một mảnh khỏi ô (p, r). Khi đó, theo điều kiện, các ô (p, s), (q, s) và (q, r) là tự do. một đường dẫn từ p đến r, tức là p và r nằm trong cùng một thành phần được kết nối. Bằng cách loại bỏ một mã thông báo, chúng ta thêm một cạnh ( p, r ) vào biểu đồ, nhưng điều này không làm thay đổi thành phần được kết nối. Do đó, biểu đồ đã và vẫn không được kết nối. Lưu ý rằng trên một bảng trống, mỗi chiều dọc được kết nối với mỗi chiều ngang. chúng ta không thể loại bỏ tất cả các chip. Đường dẫn đến lời giải. Đồ thị được xây dựng có vẻ khác thường. Tuy nhiên, đối với các nhà toán học, một bảng gồm các số 0 và một là một cách khá quen thuộc để biểu diễn cái gọi là đồ thị lưỡng cực: trong các đồ thị như vậy, các đỉnh được chia thành hai loại (hai phần) và các cạnh chỉ có thể kết nối các đỉnh thuộc các loại khác nhau. Bàn cờ từ bài toán cuối cùng tự nhiên biến thành một bảng gồm các số 0 và một nếu các chip được thay thế bằng 0 và trống

“SỐ LƯỢNG” CHO HỌC SINH THI

Bài toán

1. Tìm tất cả các câu đố lời giải có thể

BẠN + BẠN + BẠN + BẠN + BẠN = BẠN.

Văn hóa dân gian

4. Bên trong tam giác đều được đánh dấu

Trong một cuộc đua gián, 20 con gián lần lượt chạy ra ngoài, cách nhau 1 phút và chạy với tốc độ không đổi. Người thứ hai bắt kịp người thứ nhất 2 phút sau khi bắt đầu, người thứ ba đuổi kịp người thứ hai - 3 phút sau khi bắt đầu, …, người thứ hai mươi chín - 20 phút sau khi bắt đầu. Sau bao nhiêu phút kể từ lúc xuất phát, con gián thứ 20 đuổi kịp con thứ nhất? A. Điểm Shapovalov, nối nó với các đỉnh và cắt hình tam giác dọc theo các đoạn này. Có thể chọn một điểm sao cho từ các hình tam giác thu được không có nếp gấp hoặc chồng lên nhau có thể gấp một hình tam giác khác được không? A. Bannikova

88x49

5. Trong số sáu đồng xu, có hai đồng nhẹ hơn là tiền giả.

Những bài toán này chủ yếu dành cho học sinh lớp 6–8. Những bài toán này đã được đưa ra tại Giải đấu Mùa hè XX mang tên A.P. Savin.

Minh họa của D. Grishukova

Có hai cây cột ở khoảng cách 5 mét gần một con đường thẳng. Chiều cao của cột cao hơn cũng là 5 mét. Có một sợi dây căng giữa các đầu cột. Gió thổi và một cây cột nhỏ rơi xuống đường theo hướng cột cao như hình hình. Điều gì đã xảy ra với sợi dây: nó có bị chùng xuống, bị căng trở lại hay bị đứt? M. Raskin, E. Bakaev

Có cân cốc, mỗi lần cân bạn phải trả trước một xu. Nếu đồng xu được trả là thật, cân sẽ hiển thị kết quả chính xác, nhưng nếu đó là tiền giả thì ai biết được điều gì. Làm thế nào để tìm (và không lãng phí) một đồng tiền thật? V. Kleptsyn, A. Zaslavsky

Khối đa diện xung quanh chúng ta

Bạn có thể bắt đầu làm quen với thế giới khối đa diện mà không cần chờ đợi những bài học về lập thể ở trường trung học. Đôi khi chỉ cần nhìn vào một số sáng tạo của các kiến ​​trúc sư là đủ. Hầu hết các tòa nhà cao tầng hiện đại đều có hình dạng song song hình chữ nhật. Đôi khi chúng được gọi một cách ngẫu nhiên là các hộp (trong tiếng Anh, “hình chữ nhật song song” dài cũng thường được thay thế bằng “hộp” ngắn). Điều này có thể dễ dàng giải thích - việc xây dựng các hộp sẽ dễ dàng hơn. Đúng, có những tòa nhà khác thường trong số các hộp. Đồng ý rằng, không phải lúc nào bạn cũng bắt gặp một ngôi nhà có hình khối gần như hình khối, giống như thư viện thành phố Stuttgart (ảnh 1)!

vyh, trung tâm triển lãm và các tòa nhà khác theo hình kim tự tháp. Đôi khi các nhà thiết kế và kiến ​​trúc sư đề xuất thay đổi ý tưởng của chúng ta về kim tự tháp (ảnh 3).

Ảnh 3. Tòa nhà này có Tòa thị chính Tempe (Arizona, Mỹ)

Tuy nhiên, chiếc hộp có thể trông hoàn toàn bất ngờ. Một trong những tòa nhà trong khuôn viên Đại học Nottingham có vẻ như là một chiếc hộp nghiêng, một phần kéo dài xuống lòng đất.

Ảnh 1

Các cấu trúc kim tự tháp cổ đại nổi tiếng nhất là kim tự tháp Ai Cập. Các kim tự tháp nghi lễ của người Maya trên bán đảo Yucatan của Mexico cũng có hình dạng kim tự tháp, hay chính xác hơn là các kim tự tháp cắt cụt với hình vuông ở đáy (ảnh 2). Ngày nay, một số lượng lớn các hoạt động thể thao, thương mại,

Ảnh 4

Ảnh 2

(ảnh 4). Hãy cố gắng hiểu đa giác nằm dưới nền của tòa nhà này có bao nhiêu cạnh. Có thể thực hiện một dự án ẩn một phần trong lòng đất của một chiếc hộp có hình tam giác ở đáy không? Còn hình ngũ giác hay hình lục giác thì sao? Bạn có thể tạo ra các hình dạng mới từ hộp bằng cách cắt bỏ các góc (ảnh 5). Hình bình hành hình chữ nhật là trường hợp đặc biệt của lăng kính. Đáy của lăng kính có thể là

Ảnh 5. Tòa tháp cao tầng ở thành phố Regina của Canada

Ảnh 8

Ảnh 6. “Diễn đàn” Barcelona

bất kỳ đa giác nào, ví dụ như một hình tam giác (ảnh 6). Tòa nhà cao tầng của Trung tâm Thương mại Thế giới ở New York có hình dạng được gọi là phản lăng kính tứ giác (ảnh 7). Các đáy của phản lăng kính có hai hình vuông bằng nhau, một trong số đó quay được 45 độ so với hình kia. Ngoài hai đáy, phản lăng kính còn có các mặt bên là hình tam giác (có bao nhiêu mặt?). Điều gì xảy ra nếu phản lăng kính bị cắt ở giữa với một phần song song với các đáy? Để trả lời câu hỏi này, bạn có thể sử dụng một bức ảnh

8, được chụp khi Trung tâm Thế giới mới được xây dựng một nửa. Hãy kết thúc chuyến tham quan ngắn ngày của chúng ta ở Minsk. Tòa nhà Thư viện Quốc gia Belarus có hình khối thoi (ảnh 9). Như một bài tập

Ảnh 9 bạn có thể đếm xem nó có bao nhiêu đỉnh, cạnh và mặt của mỗi loại. Tài liệu được chuẩn bị bởi S. Dvoryaninov, P. Kozhevnikov

Nguồn ảnh:

Ảnh 7

1 – http://www.home-designing.com/ 2 – http://en.wikipedia.org/wiki/Chichen_Itza 3 – http://en.wikipedia.org/wiki/Tempe_Municipal_Building 4 – http://bof.co.uk/project/13 5 – http://www.workopolis.com/ 6 – http://www.pushpullar.com 7 – http://en.wikipedia.org/wiki/New_York_City 8 – http://www.the atlantic.com 9 – http://www.calend.ru

Thế Vận Hội

Giải đấu thành phố XXXV

MỤC ĐÍCH CỦA DU LỊCH XUÂN

Tùy chọn cơ bản

lớp 8–9

1 (3). 100 con số được đưa ra. Khi mỗi số đó tăng lên 1 thì tổng bình phương của chúng không thay đổi. Mỗi số lại tăng thêm 1. Liệu tổng bình phương lần này có thay đổi không, và nếu có thì thay đổi bao nhiêu? A. Shapovalov

1

2 (4). Mẹ nướng những chiếc bánh trông giống hệt nhau: 7 chiếc với bắp cải, 7 chiếc với thịt và một chiếc với quả anh đào, rồi xếp chúng thành hình tròn trên đĩa tròn theo thứ tự đó. Sau đó tôi cho đĩa vào lò vi sóng để hâm nóng. Olya biết cách đặt bánh nướng, nhưng không biết món ăn diễn ra như thế nào. Cô ấy muốn ăn một chiếc bánh anh đào, nhưng lại coi phần còn lại là vô vị. Làm sao Ole có thể chắc chắn đạt được điều này sau khi cắn không quá ba chiếc bánh vô vị? A. Khachaturian

3 (4). Xem bài toán M2350 “Bài toán Kvant”.

4 (5). Trên cạnh BC của tam giác ABC, chọn điểm L sao cho AL gấp đôi đường trung tuyến CM. Hóa ra góc ALC bằng $45\infty$. Chứng minh rằng AL và CM vuông góc với nhau. R.Zhenodarov

5 (6). Một hàng dài xếp hàng để qua eo biển Bosphorus: người đầu tiên là Ali Baba, theo sau là 40 tên cướp. Chỉ có một chiếc thuyền, hai hoặc ba chiếc có thể đi trên đó (bạn không thể chèo thuyền một mình). Trong số những người chèo thuyền không nên có những người không phải là bạn bè của nhau. Liệu tất cả họ có thể vượt qua nếu cứ hai người đứng cạnh nhau trong hàng đợi đều là bạn, và Ali Baba vẫn là bạn với tên cướp đứng cách anh ta một người? A. Shapovalov

lớp 10–11

1 (4). Cheburashka có một bộ gồm 36 viên đá có khối lượng 1 g, 2 g,…, 36 g, và Shapoklyak có keo siêu dính, với một giọt bạn có thể dán hai viên đá thành một (theo đó, bạn có thể dán 3 viên đá bằng hai giọt, v.v.). Shapoklyak muốn dán các viên đá lại với nhau để Cheburashka không thể chọn một hoặc nhiều viên đá có tổng khối lượng là 37 g từ bộ kết quả. Hỏi số giọt keo nhỏ nhất sẽ đủ để cô ấy thực hiện được kế hoạch của mình là bao nhiêu? E. Bakaev

2 (4). Tứ giác lồi ABCD có hai đường chéo vuông góc. Trên các cạnh AD và CD lần lượt đánh dấu các điểm M và N sao cho các góc ABN và CBM là các góc vuông. Chứng minh hai đường thẳng AC và MN song song. A. Polyansky

3 (5). Xem bài toán 5 cho lớp 8 – 9.

1 Trong ngoặc đơn sau số bài toán số điểm tối đa được trao cho lời giải của nó được biểu thị. Kết quả được tóm tắt theo ba nhiệm vụ đã đạt được kết quả tốt nhất.

4 (5). Các số tự nhiên a, b, c, d là các số nguyên tố cùng nhau thỏa mãn đẳng thức ab + cd = ac – 10bd. Chứng minh rằng trong số đó có ba số trong đó một số bằng tổng của hai số còn lại. B.Frenkin

5 (5). Cho tứ giác lồi ABCD. Người đi bộ Petya rời đỉnh A, đi dọc theo cạnh AB rồi dọc theo đường viền của tứ giác. Người đi bộ Vasya rời đỉnh A cùng lúc với Petya, đi dọc theo đường chéo AC và đồng thời cùng Petya đến C. Người đi bộ Tolya rời đỉnh B vào thời điểm Petya đi qua nó, đi dọc theo đường chéo BD và đồng thời với Petya đến D. Vận tốc của người đi bộ là không đổi. Liệu Vasya và Tolya có thể đến giao điểm của đường chéo O cùng lúc không? B.Frenkin

Tùy chọn phức tạp

lớp 8–9

1 (3). Ông già Noel đã phát 47 viên sôcôla cho trẻ em, sao cho mỗi bé gái nhận được nhiều hơn một bé trai. Sau đó, ông già Noel đã phát 74 hạt thạch cho các em giống nhau, sao cho mỗi bé trai nhận được nhiều hơn một hạt thạch so với mỗi bé gái. Tổng cộng có bao nhiêu đứa trẻ? E. Bakaev

2 (5). Trên bảng ca rô $5 \times 5$ Petya đánh dấu một số ô vuông. Vasya sẽ thắng nếu anh ta có thể bao phủ tất cả các ô này bằng các góc của ba ô không chồng lên nhau và không vượt ra ngoài đường viền của hình vuông (các góc chỉ có thể được đặt “trong các ô”). Số ô vuông nhỏ nhất mà Petya phải đánh dấu để Vasya không thể thắng là bao nhiêu? A. Shapovalov

3 (6). Một chiếc khăn trải bàn hình vuông được đặt trên một chiếc bàn vuông sao cho không có góc nào bị che khuất, nhưng mỗi bên của bàn treo một mảnh khăn trải bàn hình tam giác. Biết rằng có hai mảnh liền kề bằng nhau. Chứng minh rằng hai phần còn lại cũng bằng nhau. (Khăn trải bàn không chồng lên nhau ở bất cứ đâu; kích thước của nó có thể khác với kích thước của bàn.) E. Bakaev

4 (7). Vua gọi hai nhà thông thái đến. Ông đưa cho 100 tấm thẻ trống đầu tiên và yêu cầu anh ta viết một số tự nhiên lên mỗi tấm thẻ (các số này không nhất thiết phải khác nhau) mà không cho người thứ hai xem. Sau đó, người đầu tiên có thể cho người thứ hai biết một số số khác nhau, mỗi số được viết trên một thẻ nào đó hoặc bằng tổng các số trên một số thẻ (mà không chỉ rõ cách lấy chính xác từng số). Người thứ hai phải xác định 100 số nào được ghi trên thẻ. Nếu không làm được điều này, cả hai sẽ bị chặt đầu; nếu không thì râu của mỗi người sẽ bị bứt nhiều như số con số đầu tiên nói với con số thứ hai. Làm thế nào các nhà hiền triết, nếu không đồng ý, có thể sống sót và mất đi một lượng lông tối thiểu? I. Bogdanov

5 (7). Một số chấm trắng và một số chấm đen được đưa ra. Từ mỗi chấm trắng có một mũi tên tới mỗi chấm đen,

44

KVANT 2014/№4

mỗi mũi tên có một số tự nhiên được viết trên đó. Biết rằng nếu bạn đi theo một đường mũi tên khép kín bất kỳ thì tích các số trên mũi tên đi ngược chiều chuyển động sẽ bằng tích các số trên mũi tên đi ngược chiều chuyển động. Vậy có cần thiết phải đặt một số tự nhiên tại mỗi điểm sao cho số trên mỗi mũi tên bằng tích của các số ở hai đầu mũi tên không? A. Pakharev

6 (9). Từ hình khối $1 \times 1 \times 1$ khối $3 \times 3 \times 3$ được dán. Số khối lập phương lớn nhất có thể được ném ra khỏi nó là bao nhiêu để một hình có hai tính chất sau: i nhìn từ cạnh của bất kỳ mặt nào của hình lập phương ban đầu, hình này trông giống như một hình vuông $3 \times 3$ (nhìn vuông góc với mặt này, chúng ta sẽ không thấy khoảng trống - có thể nhìn thấy 9 khối của hình này); tôi di chuyển trong một hình từ khối này sang khối khác qua mặt chung của chúng, liệu có thể đi từ khối này sang khối khác không? A. Marachev

7 (9). Có 10 điểm được đánh dấu trên đường tròn, được đánh số theo chiều kim đồng hồ: $A_{1}, A_{2},..., A_{10}$, và được biết chúng có thể chia thành từng cặp đối xứng nhau qua tâm đường tròn. Ban đầu, một con châu chấu đậu ở mỗi điểm đã đánh dấu. Mỗi phút, một con châu chấu nhảy dọc theo vòng tròn qua người hàng xóm của nó để khoảng cách giữa chúng không thay đổi. Đồng thời, bạn không thể bay qua những con châu chấu khác và đến điểm mà một con châu chấu đã đậu sẵn. Sau một thời gian, hóa ra có khoảng 9 con châu chấu đang đậu ở các điểm $A_{1}, A_{2},..., A_{9}$, và con châu chấu thứ mười đang đậu trên vòng cung $A_{9} A_{10} A_{1}$. Chúng ta có thể nói rằng anh ấy ngồi chính xác tại điểm $A_{10}$ không? E. Bakaev

lớp 10–11

1 (3). Dunno khoe rằng anh ấy đã viết nhiều đơn vị liên tiếp, đặt dấu “+” hoặc dấu “$\times$” giữa mỗi đơn vị liền kề, đặt dấu ngoặc đơn và nhận được biểu thức có giá trị là 2014; Hơn nữa, nếu trong biểu thức này chúng ta thay đồng thời tất cả các dấu “+” bằng dấu “$\times$” và dấu “$\times$” bằng dấu “+”, chúng ta vẫn sẽ nhận được năm 2014. Liệu anh ấy có đúng không? V. Kleptsyn

2. Có đúng là bất kỳ đa giác lồi nào cũng có thể được cắt dọc theo một đường thẳng thành hai đa giác nhỏ hơn có chu vi bằng nhau và a) (4) các cạnh dài nhất bằng nhau; b) (4) các cạnh nhỏ nhất bằng nhau? A. Shapovalov

3 (6). Vua gọi hai nhà thông thái đến. Ông đưa cho 100 tấm thẻ trống đầu tiên và yêu cầu anh ta viết một số dương trên mỗi tấm thẻ (các số này không nhất thiết phải khác nhau) mà không cho người thứ hai xem. Sau đó, người đầu tiên có thể cho người thứ hai biết một số số khác nhau, mỗi số được viết trên một thẻ nào đó hoặc bằng tổng các số trên một số thẻ (mà không chỉ rõ chính xác cách lấy được từng số). Người thứ hai phải xác định 100 số nào được ghi trên thẻ. Nếu không làm được điều này, cả hai sẽ bị chặt đầu; nếu không thì râu của mỗi người sẽ bị bứt nhiều như số con số đầu tiên nói với con số thứ hai. Làm thế nào các nhà hiền triết, nếu không đồng ý, có thể sống sót và mất đi một lượng lông tối thiểu? I. Bogdanov

4 (7). Xem bài toán M2351 “Bài toán Kvant”.

5 (8). Xem bài toán M2354 “Bài toán Kvant”.

6 (9). Mỗi thành phố ở một quốc gia nhất định được gán một số riêng. Có một danh sách trong đó với mỗi cặp số sẽ cho biết liệu các thành phố có những số này có được kết nối bằng đường sắt hay không. Hóa ra, dù bạn lấy hai số M và N từ danh sách như thế nào, bạn vẫn có thể đánh số lại các thành phố sao cho thành phố có số M sẽ nhận được số N, nhưng danh sách vẫn đúng. Có đúng là nếu lấy hai số M và N trong danh sách, bạn có thể đánh số lại các thành phố sao cho thành phố có số M sẽ nhận được số N, thành phố có số N sẽ nhận được số M, nhưng danh sách vẫn đúng? A. Pakharev, M. Skopenkov, A. Ustinov

7 (10). Đa thức P ( x ) thỏa mãn điều kiện: $P ( 0 ) = 1 ; 2 ( P ( x ) ) = 1 + x + x^{100} Q ( x )$, trong đó Q ( x ) là một đa thức nhất định. Chứng minh rằng hệ số $x^{99}$ trong đa thức 100 ( P ( x ) + 1 ) bằng 0. D. Zvonkin

TOUR NÓI DÀNH CHO LỚP 11

1. Trong tập {1, 2, 3,…, 2014} ta chọn tập con A. Hóa ra không có tam thức bình phương nào mà cả ba hệ số đều thuộc A, có nghiệm thực. Số phần tử lớn nhất mà A có thể có là bao nhiêu? G. Zhukov

2. Cho tam giác ABC. Một tia kẻ từ đỉnh B đi qua trung điểm AC cắt phân giác ngoài của góc A tại điểm P. Đường thẳng PC cắt đường thẳng chứa phân giác trong của góc A tại điểm Q. Chứng minh BA = BQ. F.Ivlev

3. Xem bài toán M2349 “Bài toán Kvant”.

4. Trong tứ diện đẳng diện ABCD, các điểm $A ', B ', C ', D '$ là tâm của các hình cầu lệch tâm. Chứng minh rằng A, B, C, D là tâm các hình cầu lệch tâm của tứ diện $A ' B ' C ' D '$. (Một tứ diện được gọi là đẳng diện nếu các mặt của nó là các tam giác bằng nhau. Hình cầu ngoại tiếp là một hình cầu tiếp xúc với một trong các mặt và phần kéo dài của các mặt còn lại.) A. Zaslavsky

5. Trong hình chữ nhật ca rô màu trắng, có cạnh lớn hơn 10, ô K được sơn màu đen. Tiếp theo, trong khi di chuyển, chọn một hàng (ngang hoặc dọc) trong đó có ít nhất 10 ô màu đen và sơn đen tất cả các ô trắng trong hàng này. Sau vài lần di chuyển như vậy, tất cả các ô đều trở thành màu đen. Chứng minh rằng $K \ge 100$. P.Kozhevnikov

6. Chứng minh rằng không có đa thức nào cho hai biến P ( x, y ) mà tập lời giải của bất đẳng thức P ( x, y ) > 0 là góc phần tư { ( x, y ): x > 0, y > 0 }. L.Stunzhas

Ấn phẩm được biên soạn bởi S. Dorichenko, L. Mednikov, A. Semenov