Bài toán 16—20

26

KVANT 2008/№1

Cuộc thi mang tên A.P. Savin

“Toán 6–8”

Chúng tôi đang hoàn thành một cuộc thi khác về lời giải toán bài toán dành cho học sinh lớp 6–8. Gửi Lời giải bài toán trong vòng một tháng sau khi nhận được số tạp chí này đến địa chỉ: 119296 Moscow, Leninsky Prospekt, 64-A, «Kvant» (được đánh dấu là “Cuộc thi “Toán học 6–8”). Hãy nhớ điền tên, lớp và địa chỉ nhà của bạn. Như trước đây, chúng tôi hoan nghênh sự tham gia vào cuộc thi không chỉ của từng học sinh mà còn của các câu lạc bộ toán học. Chúng tôi yêu cầu vòng tròn lãnh đạo cung cấp địa chỉ email hoặc số điện thoại liên hệ Theo truyền thống, các câu lạc bộ chiến thắng trong cuộc thi thư từ sẽ được mời tham dự giải đấu trực tiếp cuối cùng.

16. Với những số tự nhiên nào n > 2, chúng ta có thể viết các số từ 1 đến n trên một dòng sao cho trong ba số viết trên một hàng bất kỳ, một số không nhỏ hơn tổng của hai số còn lại? I. Akulich

19. Dãy số $f_{0}, f_{1}, f_{2}$, … được xây dựng như sau:

20. Tìm tất cả các lũy thừa tự nhiên của các số nguyên tố có thể biểu diễn dưới dạng tổng của hai lập phương các số tự nhiên. V. Người gửi

Chứng minh rằng mọi số trong dãy này đều là số nguyên. V. Letsko

18. Điểm D nằm trong tam giác nhọn ABC, đối xứng với ba cạnh AB, BC, CA. Hóa ra ba điểm mới tương ứng $C_{1}, A_{1}, B_{1}$ nằm trên đường tròn ngoại tiếp tam giác ABC. Sau đó, các điểm $A_{1}, B_{1}, C_{1}$ vẫn còn trên bản vẽ và mọi thứ khác đều bị xóa. Vẽ lại tam giác ABC bằng ba điểm đó. S. Dvoryaninov

$f 0 =^{0}, f_{n} +_{1} =$

$3 f_{n} + 5 f_{n}^{2} + 4$

2

, n = 0, 1, 2, …

20. Các số tự nhiên x và y sao cho xy + 1 là bình phương của số nguyên. Chứng minh rằng tồn tại một số tự nhiên z sao cho các số yz + 1, zx + 1 và số xy + yz + zx + 1 đều là các số nguyên. V.Proizvolov

Bóng ma của Leonardo

I.AKULICH

Đừng để ai không phải là nhà toán học đọc tôi.

Leonardo da Vinci. Văn xuôi khoa học

NỬA THIÊN KỶ TÁCH CHÚNG TA KHỎI LEONARD VĨ ĐẠI trước da Vinci, nhưng nhân loại cho đến ngày nay vẫn không ngừng tìm kiếm đáp số cho câu hỏi: ông ta là ai? Nghệ sĩ? Nhà phát minh? Nhà triết học? Một thiên tài đi trước thời đại, hay thậm chí là sứ giả của trí thông minh ngoài hành tinh? Bằng chứng về sự quan tâm lâu dài đối với gã khổng lồ thời Phục hưng này là cuốn sách (và sau đó là bộ phim) Mật mã Da Vinci rất được hoan nghênh, cũng như trò chơi máy tính hấp dẫn $игра^{1}$. Cô ấy thẳng-

1 Ví dụ, hãy xem www.1980-games.com/us/reflexion-games/reflexion-others/026.php hoặc www.1980-games.com/us/reflexion-games/reflexion-others/debout.php vẫn còn đầy rẫy các nhiệm vụ, câu đố và những khó khăn khác, khiến nó cực kỳ khó nhưng cũng rất thú vị. Một trong những bài toán của trò chơi này là điểm khởi đầu của câu chuyện mà chúng tôi sẽ trình bày bây giờ. Vì vậy, cho một hình vuông ca rô có kích thước 5 × 5 ô, mỗi ô có thể có màu trắng hoặc đen (ban đầu tất cả các ô đều có màu trắng, mặc dù điều này không quan trọng). Bạn được phép chọn bất kỳ ô nào, đồng thời tô màu lại ô đó và tất cả các ô có điểm chung với nó (chúng ta sẽ gọi chúng là hàng xóm) bằng màu đối diện. Cần phải sơn lại tất cả các ô của hình vuông bằng màu đối diện trong một số thao tác như vậy. Thật khó để nói liệu chính Leonardo da Vinci có nhúng tay vào việc này bài toán hay không, nhưng rất có thể là ông ấy đã làm như vậy. TRONG

27

dù sao đi nữa, có vẻ như vậy. Rất nhiều… nhưng sẽ nói nhiều hơn về điều đó sau. Tất nhiên, nhiều người dùng trò chơi máy tính đã giải câu đố “ngẫu nhiên”, nhấp chuột vào các ô khác nhau theo lệnh của linh hồn. Nhưng chúng tôi sẽ cố gắng tiếp cận vấn đề một cách khoa học. Để bắt đầu, hãy gọi việc sơn lại một ô (và đồng thời tất cả các ô lân cận của nó) là di chuyển đến ô đó. Chúng ta hãy thực hiện một số bước di chuyển nhất định vào một số ô và đạt được mục tiêu của mình bằng cách sơn lại tất cả các ô của hình vuông bằng màu đối lập. Hãy xem xét bất kỳ ô nào. Với mỗi lần di chuyển vào chính nó hoặc vào bất kỳ ô nào liền kề với nó, nó sẽ thay đổi màu sắc. Do đó, nếu cuối cùng ô nhận được màu đối lập thì tổng số lần di chuyển đến ô này và tất cả các ô liền kề với nó phải là số lẻ. Trong trường hợp này, thứ tự các nước đi rõ ràng không quan trọng chút nào - tổng (và đặc biệt là tính chẵn lẻ) không thay đổi khi sắp xếp lại các số hạng. Sau khi suy ngẫm, chúng ta có thể rút ra một kết luận khác không kém phần quan trọng: nếu có ít nhất hai lần di chuyển được thực hiện ở bất kỳ ô nào, thì bằng cách giảm số lần di chuyển đến ô này đi 2, chúng ta sẽ đi đến kết quả tương tự. Luật ngang bằng cũng có tác dụng ở đây. Nhưng nếu vậy thì bằng cách giảm số lần di chuyển đến mỗi ô càng lâu càng tốt, chúng ta sẽ đưa số lần di chuyển đến mỗi ô xuống còn một hoặc không có gì cả. Nói cách khác, nếu có thể đạt được kết quả mong muốn bằng cách sử dụng một số bước di chuyển nhất định đến một số ô, thì điều tương tự cũng có thể đạt được bằng cách thực hiện không quá một lần di chuyển đến mỗi ô. Kết luận này cho phép chúng ta chia các ô thành hai loại: ô nào đã thực hiện một nước đi (loại duy nhất!) và một nước nào không được thực hiện. Do đó, hãy đánh dấu các ô mà chúng ta cần di chuyển và suy nghĩ xem cấu hình kết quả phải đáp ứng những điều kiện nào. Lưu ý rằng mỗi ô được đánh dấu phải liền kề với một số chẵn các ô được đánh dấu (tức là không có, hoặc hai hoặc bốn) và mỗi ô không được đánh dấu phải liền kề với một số lẻ các ô được đánh dấu (tức là một hoặc ba). Không còn nghi ngờ gì nữa, hầu hết độc giả sẽ đồng ý với điều này mà không do dự, nhưng đối với những người còn nghi ngờ, chúng tôi sẽ giải thích chi tiết hơn. Hãy xem xét bất kỳ ô A không được đánh dấu nào. Nó nằm liền kề với một số lẻ các ô được đánh dấu. Vì khi di chuyển đến bất kỳ ô lân cận nào như vậy, ô A sẽ đổi màu nên sau mỗi lần di chuyển nó sẽ đổi màu

M

Sh

Minh họa của V. Ivanyuk

ĐẾN

một số lẻ lần, và cuối cùng màu của nó sẽ ngược lại với màu ban đầu. Bây giờ hãy xem xét bất kỳ ô B được đánh dấu nào. Nó liền kề với một số ô chẵn được đánh dấu. Vì khi di chuyển đến bất kỳ ô lân cận nào như vậy, ô B sẽ đổi màu, nên sau khi di chuyển đến các ô được đánh dấu liền kề, nó sẽ đổi màu số lần chẵn. Ngoài ra, nó sẽ đổi màu một lần khi di chuyển đến ô B. Như vậy, cuối cùng màu của nó sẽ trở nên đối lập với màu ban đầu. Chà, chúng tôi đã cố gắng chuyển đổi “động” bài toán (trong đó các ô thỉnh thoảng thay đổi màu sắc) thành phiên bản “tĩnh”, trong đó bạn chỉ cần đánh dấu một số ô vuông của bảng theo một cách nhất định: sao cho mỗi ô vuông được đánh dấu liền kề với một số ô vuông được đánh dấu chẵn và mỗi ô vuông không được đánh dấu liền kề với một số ô vuông được đánh dấu lẻ. Hãy bắt đầu. Đối với hình vuông 5 ѣ 5 lời giải có sẵn (hình1, các ô được đánh dấu có màu đỏ). Bằng cách xoay và phản chiếu, bạn có thể có thêm ba lời giải, nhưng điều thú vị nhất là không có lời giải nào khác! Chỉ riêng điều này đã gợi ý rằng Leonardo vĩ đại có thể đã tham gia vào bài toán như vậy - xét cho cùng, theo trực giác, có vẻ như lời giải phải “đối xứng hơn”, ít nhất là đối với trục dọc và trục ngang. Tất nhiên, chúng ta sẽ không giới hạn mình ở hình vuông 5 ѣ 5 mà sẽ “chạm” vào các hình vuông n ѣ n đối với n khác.

28

KVANT 2008/№1

Hình 1

Với n nhỏ, điều này có thể được thực hiện không mấy khó khăn. Cách dễ nhất để có được đáp số với n = 1 chỉ đơn giản là đánh dấu một ô. Với n = 2, chúng ta có bốn ô được tô bóng và lời giải cũng là ô duy nhất. Giá trị n = 3 mang lại một cấu hình đẹp, lại là duy nhất (hình2).

Hình 2

Sự phân tán không mong muốn của các cấu hình khác nhau được tạo ra bởi n = 4. Có năm cách khác nhau về cơ bản để đánh dấu các ô (hình3).

Hình 3

Hai cái đầu tiên trong số chúng được “chia đôi” với sự trợ giúp của phép quay và phản xạ, và ba cái còn lại là “tăng gấp bốn lần”. Tổng cộng có 16 cách. Một kết quả rất “nổi bật” so với phần còn lại đã được xem xét. Hơn nữa lời giải cho đến n = 8 vẫn có thể được chọn thủ công (nhân tiện, chúng tôi lưu ý rằng bài toán đối với hình vuông 8 ѣ 8, tức là chính bàn cờ, đã được đề xuất trong cuộc thi “Toán học 6–8” của năm học hiện tại (bài toán 5) - vì vậy chúng tôi đã giải nó cùng lúc). Đồng thời, các cấu hình rất hấp dẫn với mức độ đối xứng cao (hình4) đã được phát hiện. Ở giai đoạn này, mặc dù đã đạt được những thành công nhưng những điềm báo u ám mơ hồ vẫn xuất hiện. Thứ nhất, không thể tìm ra những cách “tổng quát” để đánh dấu các ô theo yêu cầu. Những nỗ lực sử dụng kết quả tìm thấy cho n nhỏ hơn khi tìm kiếm lời giải cho n lớn hơn cũng không thành công. Đúng, cấu hình cho n = 8, như dễ thấy, có được bằng cách thêm một “đường viền” vào cấu hình

Hình 4

radio với n = 6, nhưng thành công này quá khiêm tốn (và thành thật mà nói, nó đã được bộc lộ sau này). Phải làm gì? Chúng tôi phải sử dụng những thành tựu của công nghệ điện toán hiện đại và hướng dẫn máy tính tìm kiếm những n ô khác có thể được đánh dấu (đồng thời đếm số cách để làm điều này cho mỗi n). Sau khi khởi động mạnh mẽ, máy tính chỉ đạt n = 28, bởi vì khi n tăng thêm, nó bắt đầu suy nghĩ trong một thời gian dài vô duyên. Tuy nhiên, việc phân tích kết quả hóa ra lại ấn tượng đến mức giả định về sự liên quan của da Vinci vào bài toán được đề cập chỉ trở nên mạnh mẽ hơn. Thẩm phán cho chính mình. Đầu tiên, máy tính xác nhận tính duy nhất của lời giải với n = 6, 7 và 8. Hơn nữa, hóa ra là lời giải tồn tại với tất cả n được xem xét và với n = 10, 12, 13, 15, 18, 20, 21, 22, 25, 26, 27 và 28 thì nó là duy nhất. Do đó, nó có tính đối xứng đối với tất cả các trục đối xứng của chính bảng (nếu không, lời giải bổ sung sẽ xuất hiện, thu được bằng cách quay và phản xạ). Hơn nữa, với n = 17 (cũng như với n = 5 đã biết), có 4 lời giải, với n = 14 và 24 có 16 lời giải, với n = 11, số lời giải đạt 64, với n = 9 và 16, nó bằng 256. Và sau đó - một sự gia tăng thực sự đáng kinh ngạc: với n = 23, số lời giải “nhảy” mạnh lên 16384 và với n = 19 – đến 65536. Lưu ý rằng mỗi số xuất hiện ở đây (1, 4, 16, 64, 256, 16384 và 65536) là lũy thừa số nguyên không âm của 4. Đồng thời, đã xuất hiện các cấu hình không có đối xứng trục và đối xứng quay (mặc dù một số mảnh của chúng có thể đối xứng). Ví dụ: đây là một trong những kết quả có thể xảy ra đối với bảng 19 ѣ 19 (hình5). Một loại ảo ảnh nào đó! Những loại kết quả này chỉ đơn giản là đáng kinh ngạc, và dường như ở đâu đó gần đó, giống như một cái bóng không thể nghe thấy, hồn ma của Leonardo, trỗi dậy từ vực sâu của nhiều thế kỷ, đang đi ngang qua. Anh ấy có thực sự linh cảm về điều gì đó như thế này không (như bạn biết, việc thiếu máy tính đối với một thiên tài không phải là một trở ngại)? Bằng cách này hay cách khác, nhưng sau đó

Hình 5