Vô hạn trong nhiệm vụ

32

Vô hạn trong nhiệm vụ

Mỗi bài toán của kính vạn hoa này xử lý theo cách này hay cách khác một thứ gì đó vô hạn (ví dụ: mặt phẳng hoặc phân số thập phân). Tất nhiên, bạn có thể nghĩ ra bao nhiêu bài toán tùy thích, trong đó có liên quan đến điều gì đó vô hạn. Chúng tôi sẽ giới hạn trong một số lượng rất nhỏ các chủ đề và trong mỗi chủ đề, chúng tôi sẽ đưa ra một số ví dụ hay.

Hình trên mặt phẳng

1. Có thể bao phủ một mặt phẳng với vô số hình vuông, trong đó có đúng hai hình giống hệt nhau không? Hình vuông không thể chồng lên nhau.

Đáp số: vâng, bạn có thể. Hãy vẽ một hình vuông có cạnh 1, thêm một hình vuông có cạnh 1 vào bên trái để có hình chữ nhật 1 × 2, thêm một hình vuông có cạnh 2 vào hình chữ nhật này từ bên dưới để có hình chữ nhật 2 × 3, đặt một hình vuông có cạnh 3 ở bên phải, v.v.: chúng ta sẽ tô mặt phẳng “theo hình xoắn ốc”, mỗi lần thêm một hình vuông vào hình hiện có sao cho cạnh của nó trùng với một trong các cạnh của hình. Rõ ràng là bất kỳ điểm nào trên mặt phẳng sẽ bị bao phủ bởi một trong các hình vuông. Nhân tiện, độ dài các cạnh của các hình vuông này tạo thành dãy Fibonacci 1, 1, 2, 3, 5, 8, 13, … - nó được mô tả chi tiết trong số tạp chí này trong phần “Vòng tròn toán học”. Hãy xem xét một câu hỏi khó hơn: liệu có thể bao phủ một mặt phẳng với vô số hình vuông không chồng lên nhau, không có hình nào giống hệt nhau không?

2. Có thể bao phủ một mặt phẳng với số lượng hữu hạn a) phần bên trong của parabol; b) phần trong của các góc có tổng nhỏ hơn 360 o?

Hãy cho lời giải từ điểm a). Đáp số: không thể được. Chúng ta hãy giả sử rằng những parabol như vậy tồn tại. Lưu ý rằng phần bên trong của một parabol chỉ giao nhau với một đường dọc theo một mảnh vô hạn nếu đường thẳng đó song song với trục của parabol. Hãy vẽ một đường thẳng không song song với bất kỳ trục nào của parabol của chúng ta (điều này là có thể, vì chúng có số lượng hữu hạn). Khi đó, mỗi parabol sẽ cắt đường này dọc theo một đoạn và vì sẽ có số đoạn hữu hạn nên ngay cả đường này cũng sẽ không bị che.

Đồ thị vô hạn 3. Hãy biết rằng nhân loại là bất tử và mọi người đều là phàm nhân. Số lượng người trong mỗi thế hệ là hữu hạn. Chứng minh rằng có một chuỗi vô hạn những người bắt đầu từ Adam (người tiếp theo trong chuỗi là con của người trước).

Hãy xây dựng một hình ảnh như thế này. Ở tầng đầu tiên chúng ta sẽ đặt một điểm - nó sẽ tượng trưng cho Adam. Chúng tôi sẽ để bạn thoát khỏi nó

số lượng mũi tên mà Adam có là con trai lên tầng hai (đầu mũi tên tương ứng với các con trai của Adam). Từ mỗi điểm—một người ở tầng hai—chúng ta sẽ bắn mũi tên lên tầng ba (các mũi tên lại tương ứng với những người con trai), v.v. Chúng ta nhận được một hệ thống điểm và mũi tên từ vô số tầng (vì loài người là bất tử), nhưng trên mỗi tầng sẽ có một số điểm hữu hạn. Rõ ràng là có vô số đường đi hữu hạn đi theo các mũi tên, bắt đầu từ điểm tầng một. Chúng ta phải chứng minh rằng có một con đường vô hạn. Chúng tôi sẽ giải thích cách tìm thấy nó. Điểm đầu tiên trong đó sẽ là điểm tầng một. Vì có vô số lối đi dẫn từ một điểm ở tầng một nên có một điểm ở tầng hai có vô số lối đi qua. Điểm này sẽ là điểm thứ hai trên hành trình của chúng tôi. Hãy xem xét tất cả các đường đi qua hai điểm đã chọn - có vô số đường đi, có nghĩa là trên tầng thứ ba có một điểm mà vô số đường đi qua. Hãy chọn cô ấy thứ ba. Mỗi lần chúng ta sẽ có thể hoàn thành con đường của mình, tăng độ dài của nó và cuối cùng chúng ta sẽ có được một con đường vô tận.

4. Có một ngôn ngữ có bảng chữ cái hữu hạn. Một từ trong ngôn ngữ này là bất kỳ chuỗi chữ cái nào (hữu hạn hoặc vô hạn) trong bảng chữ cái của ngôn ngữ này. Một số từ (có độ dài hữu hạn) trong ngôn ngữ là tục tĩu. Hãy gọi một từ là hoàn toàn tử tế nếu nó không chứa những từ phụ không đứng đắn. Được biết, có những từ hoàn toàn đàng hoàng ở bất kỳ độ dài nào. Chứng minh rằng có một từ hoàn toàn đúng và dài vô hạn.

Truy đuổi trên máy bay 5. Trò chơi diễn ra trên máy bay. Hai người chơi: người đầu tiên di chuyển một chip sói, người thứ hai di chuyển 99 chip cừu. Sau bước đi của sói, một trong những con cừu đi bộ, rồi sau bước đi tiếp theo của sói, một trong những con cừu lại bước đi, v.v. Cả sói và cừu đều di chuyển không quá một mét theo bất kỳ hướng nào trong một nước đi. Có đúng là ở bất kỳ vị trí ban đầu nào, con sói sẽ bắt được ít nhất một con cừu (sẽ kết thúc ở cùng điểm với nó)?

Đáp số: không đúng. Hãy vẽ 100 đường thẳng song song trên mặt phẳng sao cho khoảng cách giữa các đường thẳng liền kề là 3 mét. Hãy đặt những con cừu trên những đường thẳng khác nhau, sau đó mỗi con sẽ chỉ di chuyển dọc theo đường thẳng của riêng mình. Hãy đặt con sói trên đường thẳng thứ một trăm. Chúng ta hãy trình bày một thuật toán về hành vi của đàn cừu, trong đó khoảng cách từ con sói đến con cừu bất kỳ trước khi con sói di chuyển sẽ luôn lớn hơn một mét. Nếu khoảng cách từ con sói đến mỗi con cừu lớn hơn một mét, hãy di chuyển bất kỳ con cừu nào (dọc theo đường thẳng của nó) để nó di chuyển ra xa con sói. Ngay khi con sói tiếp cận một trong những con cừu ở khoảng cách 1 mét hoặc gần hơn (có thể có chính xác một con cừu như vậy), chúng ta di chuyển con cừu dọc theo đường thẳng của nó sang một bên 1 mét để khoảng cách giữa nó và con sói trở nên hơn một mét.

6. Thành phố là một mặt phẳng ca rô vô tận (đường kẻ là đường phố, hình vuông là khối nhà). Trên một trong những con phố, cứ 100 dãy nhà lại có một cảnh sát ở các giao lộ. Có một tên cướp ở đâu đó trong thành phố (không rõ vị trí của hắn, nhưng hắn chỉ di chuyển dọc các con phố). Mục tiêu của cảnh sát là nhìn thấy tên cướp. Cảnh sát có thuật toán nào để chắc chắn đạt được mục tiêu của họ không? Tốc độ tối đa của cảnh sát và tên cướp là một số giá trị hữu hạn nhưng chúng tôi chưa biết (tốc độ của tên cướp có thể lớn hơn tốc độ của cảnh sát). Cảnh sát có thể quan sát dọc theo đường phố ở mọi hướng trong khoảng cách vô tận.

Hãy chọn hệ tọa độ sao cho CSGT đứng trên đường y = 0 tại các điểm (0; 0), (100; 0), (–100; 0), (200;0), (–200;0), v.v. Để CSGT đứng tại các điểm có dạng (200k; 0), trong đó $k = 0, \pm 1, \pm 2, K$, giữ nguyên tại chỗ. Khi đó tên cướp sẽ ở bên trong một dải nhất định giữa các đường x = 200m và x = 200(m + 1); anh ta sẽ có thể di chuyển bên trong dải này, nhưng sẽ không thể thoát ra khỏi nó. Cho những cảnh sát còn lại (hãy gọi họ là lính tuần tra) di chuyển dọc theo đường y = 0 theo hướng điểm (0; 0) đến giao lộ gần nó nhất mà chưa có người tuần tra nào đến được. Khi đến giao lộ (n; 0), người tuần tra rẽ vào đường vuông góc và di chuyển dọc theo điểm (n; n) và dừng lại ở đó. Kết quả là lực lượng tuần tra sẽ chiếm dần tất cả các giao lộ trên đường thẳng y = x. Chứng minh rằng bằng cách làm như vậy, sau một thời gian cảnh sát sẽ có thể nhìn thấy tên cướp.

7*. Trong thành phố từ bài toán trước, ba cảnh sát bắt được một tên trộm (không rõ địa điểm của tên trộm mà hắn chỉ di chuyển dọc các con phố). Tốc độ tối đa của cảnh sát và tên trộm là như nhau. Một tên trộm được coi là bị bắt nếu anh ta tình cờ ở cùng đường với cảnh sát. Làm thế nào cảnh sát có thể bắt được một tên trộm?

Số thập phân vô hạn

8. Chứng minh rằng mọi số thực dương đều có thể biểu diễn dưới dạng tổng của chín số, mỗi số chỉ gồm các chữ số 0 và 8 ở dạng thập phân.

Thật dễ dàng để biểu diễn bất kỳ số dương nào dưới dạng tổng của chín số, ký hiệu của số này chỉ bao gồm số 0 và số 1 (kiểm tra). Bây giờ hãy giải bài toán ban đầu. Ta cần biểu diễn số a. Trước tiên, hãy tưởng tượng số a/8 là tổng của chín số, các phần tử của chúng chỉ bao gồm các số 0 và số một, sau đó nhân mỗi số này với 8 - chúng ta được 9 số cần thiết, tổng của chúng bằng a.

9. Chứng minh rằng trong bất kỳ phân số thập phân vô hạn nào, bạn có thể sắp xếp lại các chữ số sao cho phân số thu được trở thành phân số tuần hoàn (có thể có dấu chấm trước).

Nếu có những số trong ký hiệu của một phân số xuất hiện trong ký hiệu này với số lần hữu hạn, thì chúng ta chuyển tất cả chúng về đầu (chúng ta viết chúng thành một hàng ngay sau dấu thập phân). Các số còn lại xuất hiện vô số lần. Ví dụ: đặt các số này là các số 2, 5, 7 và 8. Sau đó, bạn có thể di chuyển chúng tuần tự về đầu sao cho chúng đi theo thứ tự 257825782578… Kết quả là một phân số tuần hoàn.

Robot máy bay ca-rô Robot là một cỗ máy có bộ nhớ hữu hạn có khả năng thực hiện một chương trình có độ dài hữu hạn. Robot có một số lá cờ. Robot có thể thực hiện các hành động sau: – khi vào ô, kiểm tra xem có cờ ở đó hay không; – di chuyển đến một trong các ô lân cận (trên mặt phẳng - trái, phải, lên, xuống); – chọn hoặc bỏ chọn hộp nơi đặt robot. 10. Một robot có hai lá cờ đứng trên một trong các ô của dải ca rô vô hạn rộng một ô. Anh ta nên tiến hành bỏ qua toàn bộ dải như thế nào, tức là truy cập từng ô của nó ít nhất một lần?

Chúng ta đặt một lá cờ vào ô, di chuyển sang trái và đặt lá cờ thứ hai vào ô. Tiếp theo, chúng ta thực hiện theo một thuật toán rất đơn giản: di chuyển sang phải cho đến khi đến cờ, xóa cờ, di chuyển một ô khác sang phải, đặt cờ và di chuyển sang trái đến cờ, di chuyển một ô sang trái và quay lại đầu thuật toán (di chuyển sang phải cờ, v.v.).

11. Làm thế nào một robot có bốn lá cờ có thể đi vòng quanh một chiếc máy bay ca rô? Có thể thực hiện được bằng ba hộp kiểm không?

Thuật toán “đi vòng quanh mặt phẳng theo hình xoắn ốc”, luân phiên di chuyển sang trái, lên, phải và xuống, định kỳ tăng độ dài di chuyển thêm 1 ô, là không phù hợp: robot sẽ phải ghi nhớ các số ngày càng lớn và bộ nhớ của nó là hữu hạn. Hãy đặt bốn lá cờ vào các ô của hình vuông 2 ѣ 2. Tiếp theo chúng ta sẽ “mở rộng” hình vuông, ví dụ như thế này. Chúng ta di chuyển cờ phía trên bên trái sang trái trở lên, đi từ ô này sang phải, kiểm tra xem có cờ phía dưới chúng ta không. Nếu có, chúng ta di chuyển nó sang phải và lên trên, sau đó từ ô này chúng ta đi xuống, kiểm tra xem có lá cờ nào ở bên trái của chúng ta không, v.v. Kết quả là chúng ta sẽ đi vòng quanh máy bay, di chuyển “theo hình xoắn ốc”. Hóa ra chỉ cần ba lá cờ là đủ (gợi ý hiển thị ở hình).

12. Robot có thể điều hướng trong không gian ca rô 3D chỉ bằng ba lá cờ không? 13. Làm thế nào một robot có thể vượt qua nửa mặt phẳng ca-rô chỉ với một lá cờ? Ranh giới của nửa mặt phẳng là một bức tường. Ban đầu robot đứng dựa vào tường. Robot nhìn thấy bức tường khi nó đến gần nó. 14. Hai con robot hoàn toàn giống hệt nhau đã hạ cánh trên một chiếc máy bay. Mỗi cái có một số hộp kiểm. Robot phân biệt cờ của mình với cờ khác. Làm sao họ có thể gặp nhau? Chương trình của họ phải giống nhau.

Nếu các robot có thể có các chương trình khác nhau thì việc tổ chức một cuộc họp sẽ dễ dàng: một robot đứng yên và robot còn lại đi vòng quanh máy bay bằng ba lá cờ. Nhưng các robot được sản xuất trên cùng một dây chuyền lắp ráp và chương trình hành vi của chúng cũng giống nhau. Cố gắng nghĩ ra một chương trình cho phép robot gặp nhau bằng cách sử dụng càng ít cờ càng tốt.

Tài liệu được chuẩn bị bởi S. Dorichenko, A. Nikolaev