Hãy xem xét tất cả các tùy chọn

Kvant 1988, số 1 tr. 42-46 Thẻ UFKD

Bản dịch tự động sơ bộ, chất lượng thấp: có thể còn lỗi và câu chữ chưa tự nhiên. Bản này sẽ được thay bằng bản dịch tốt hơn. Bản gốc →

S. M. LVOVOVSKY,
Ứng viên Khoa học Vật lý và Toán học
A. L. TOOM

Phương pháp ở đây gần giống như khi tìm kiếm một hạt đậu trong túi đậu: trước tiên bạn cần có sự kiên nhẫn, chàng trai trẻ.
K. Chapek. “Phiếu giảm giá”

Khi ở các lớp tiểu học, học sinh lần đầu tiên bắt đầu giải bài toán trong toán học, các em được chọn đặc biệt như bài toán, được giải bằng các phương pháp đã khắc phục trước đó và các em nhận được một đáp số cụ thể. Để tối ưu hóa, họ chọn bài toán, có lời giải bất ngờ nhưng đơn giản và đẹp mắt.

Nhưng Thiên nhiên không tính đến sở thích của chúng ta. Do đó, một chuyên gia giải quyết bài toán, phát sinh trong quá trình phát triển bệnh lậu tự nhiên, thường xuyên phải đối mặt với những vấn đề không có lời giải, sau đó có nhiều lời giải, hoặc yêu cầu các phương pháp “xấu xí” không có đặc quyền và đôi khi cồng kềnh, “xấu xí” lời giải.

Học sinh tiểu học thường coi phương pháp dùng vũ lực là một phương pháp “xấu xí”. Một số người thậm chí còn cho rằng phương pháp vũ phu là phương pháp “sai” và họ được cho là không thể giải được bài toán. Trên thực tế, bài toán có thể được giải bằng bất kỳ cách nào, chỉ để có được đáp số đúng và hợp lý. Tìm tất cả đáp số và chứng minh rằng không có các số khác—điều này có nghĩa là giải bài toán. Và có thể có bất kỳ số nào trong số đáp số này: một, một số, không có hoặc một số vô hạn.

Tất nhiên, phương pháp tuyển dụng nhân viên được đề cập trong bài viết này phải được sử dụng một cách khôn ngoan và không bừa bãi. Trước hết, chúng ta hãy lưu ý rằng bất kỳ sự vượt quá nào mà một người hoặc toàn thể nhân loại từng

bất kỳ ai cũng có thể thực hiện nó - đây là một tìm kiếm hữu hạn và không có công nghệ máy tính nào có thể thay đổi được điều này. Nhưng ngay cả việc tìm kiếm hữu hạn cũng chỉ khả thi trong giới hạn giới hạn. Trên thực tế, với lời giải bài toán “thủ công”, sử dụng bút và giấy, bạn có thể xem qua mười, à, hàng trăm lựa chọn. Máy tính được thông báo về con số này lên tới hàng nghìn, à - hàng triệu. Tuy nhiên, bài toán, lời giải xuất hiện rất thường xuyên, phương pháp dùng vũ lực dẫn đến số lượng tùy chọn lớn hơn nhiều. Những trò chơi board đơn giản như cờ vua đã cung cấp một số thế cờ mà không máy nào có thể xử lý được. Vì vậy, nghệ thuật lập trình, giống như nghệ thuật giải toán bài toán, bao gồm khả năng giảm thiểu phép liệt kê xuống một thang đo khả thi.

Việc tìm kiếm đầy đủ tất cả các tùy chọn chỉ khả thi trong những trường hợp đơn giản nhất. Vì. Swift đã khéo léo đề cập đến nó trong cuốn sách Những chuyến du hành của Gulliver. Trong chương thứ năm của phần thứ ba, ông mô tả một cỗ máy thực hiện việc liệt kê mọi thứ và có thể tạo thành một cái nhìn tổng quan hoàn chỉnh về tất cả các ngành nghệ thuật và khoa học. Sự châm biếm của Swift nhắm đến một mục tiêu rất thực tế: tạo ra những cỗ máy “tư duy” gắn liền với ý tưởng về vũ lực. Trở lại thế kỷ 12, tu sĩ hiệp sĩ Raymudus Lull đã thiết kế một cỗ máy để chứng minh cơ học tất cả các điều khoản của Cơ đốc giáo và mang nó đến người Moor, tin tưởng rằng “khoa học” này sẽ chuyển đổi họ sang đức tin thực sự. Ý tưởng của Lullai được Giordano Bruno và Leibniz quan tâm, những người mơ ước về sự tiến bộ trong khoa học cho phép người ta không tranh luận mà có thể tính toán.

Nhà khoa học vĩ đại người Đức Leibnitz (1646-1716), người cùng thời với Swift (1667-1745), trong cuộc đời ông đã phát triển ý tưởng về một “đặc điểm phổ quát”, tức là một mô tả có độ chính xác tương đương với toán học về mọi quá trình tư duy của con người.

Ý tưởng này vẫn chưa được thực hiện đầy đủ và có lẽ sẽ không bao giờ thành hiện thực. Nhưng việc toán học hóa nhiều khía cạnh hoạt động của con người chắc chắn sẽ xảy ra. Đồng thời, các ý tưởng toán học cơ bản, trong đó có ý tưởng liệt kê các phương án, ngày càng được sử dụng rộng rãi.

Bài toán 1. Trong kho có 5 máy có trọng lượng tương ứng là 1500 kg, 1020 kg, 800 kg, 750 kg và 600 kg. Cần phải tăng một số lượng trên máy có sức nâng 3 tấn, tải tối đa nhưng không để quá tải. Những máy nào cần được cắt thành ô tô?

Lời giải. Giả sử rằng chúng ta quyết định không trở thành chiếc máy nặng nhất. Khi đó khối lượng của các máy còn lại là 1020+800+750+600=3170 kg, tức là hơn ba tấn. Điều này có nghĩa là chúng ta sẽ phải bỏ lại một chiếc máy khác. Chúng tôi sẽ thu được trọng lượng nặng nhất nếu để lại chiếc máy nhẹ nhất - 600 kg. Tất nhiên, chúng ta vẫn cần

kiểm tra xem ba mã lực có nâng được các máy còn lại không: 1020 + 800 + 750 = 2570 kg <3 tấn. Vì vậy: nếu chúng ta không lấy chiếc máy nặng nhất thì chúng ta sẽ tăng tối đa là 2570 kg. Bây giờ chúng ta tải một máy 1500 kg lên máy; thì trong xe vẫn còn 1500 kg chỗ trống. Chúng ta có thể đáp ứng 1500 kg này bằng cách chỉ lấy một máy, máy này sẽ cung cấp cho chúng ta tối đa 1020 kg (và tổng cộng sẽ có 2520 kg trong xe tải) hoặc bằng cách lấy hai máy, sẽ cung cấp cho chúng ta nhiều nhất là 800 + 600 = 1400 kg, và tổng cộng sẽ có 2900 kg trên xe tải.

So sánh tất cả các tùy chọn, chúng tôi thấy rằng tùy chọn cuối cùng là nhiều nhất. Vì vậy, bạn cần tải các loại máy có trọng lượng 1500 kg, 800 kg và 600 kg.

Việc tìm kiếm trực tiếp như vậy không phải lúc nào cũng có thể thực hiện được. Thường xuyên hơn cần phải sử dụng nó kết hợp với các phương pháp khác. Đây là một ví dụ.

Bài toán 2.*) Tìm tất cả các số tự nhiên có ba chữ số, mỗi số có hai tính chất sau:

chữ số đầu tiên nhỏ hơn chữ số cuối cùng của nó 3 lần;
tổng của chính số đó với số thu được từ nó bằng cách sắp xếp lại chữ số thứ hai và thứ ba của nó thì chia hết cho 8 mà không có số dư.

Ở đây, phương pháp liệt kê trực tiếp có nghĩa là xem xét tất cả các số có ba chữ số và chọn những số thỏa mãn điều kiện. Làm thủ công cũng giống như tìm kim trong đống cỏ khô hoặc tìm đúng hạt đậu trong túi đậu. Đúng, sẽ không mất nhiều thời gian để sắp xếp tất cả các số có ba chữ số bằng máy tính, nhưng sẽ “thể thao hơn” khi giải các số bài toán đơn giản bằng các phương tiện đơn giản: điều này sẽ buộc chúng ta phải phát triển các kỹ thuật để giảm bớt tìm kiếm; Nhân tiện, những kỹ thuật này sẽ tăng cường đáng kể khả năng của chúng ta khi chúng ta có máy tính.

Chúng ta sẽ bắt đầu giải bài toán này bằng đại số và sẽ chỉ sử dụng phép liệt kê khi chúng ta có thể giải được nó trong một số trường hợp.

Lời giải. Gọi $x$ là chữ số hàng trăm, $y$ là chữ số hàng chục của số mong muốn. Khi đó chữ số hàng đơn vị của nó là 3x. Hiển nhiên là 3x<9, do đó $x\leq 3$ . Chữ số đầu tiên của một số không thể bằng 0. Điều này có nghĩa là $x$ không thể bằng một số khác ngoài 1, 2 và 3. Chúng ta sẽ xem xét ba khả năng này một cách riêng biệt, nhưng trước tiên chúng ta viết ra điều kiện thứ hai, biểu thị thời gian bằng dấu chấm (:) biểu thức “chia cho”:

$((100x+10y+3z)+(100x+30x+y))\div 8,$

tức là

$(200x+33x+11y)\div 8.$

Chúng tôi cố tình để lại 200x và 33x dưới dạng các thuật ngữ riêng biệt. Điều này giúp dễ dàng nhận thấy rằng 200x có thể bị loại bỏ (kể từ 200 : 8) và viết điều kiện này như sau:

$((33x+11y)\div 8,$

hoặc

$11(3x+y)\div 8.$

Để làm được điều này, điều cần thiết và đủ là 3x+y chia hết cho 8. Bây giờ chúng ta hãy xem xét việc tìm kiếm, điều này khá khả thi vì nó chỉ bao gồm ba trường hợp.

$x=1$ . Sau đó $3+y$ : 8. Đây sẽ là $y=5$ .
$x=2$ . Sau đó $6+y$ : 8. Đây sẽ là $y=2$ .
$x=3$ . Sau đó $9+y$ : 8. Đây sẽ là $y=7$ .

Vậy bài toán có ba đáp số: 153, 226, 379.

Bài toán 3. Giải phương trình trong số tự nhiên

$\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1.$

Hãy nhớ rằng số nguyên dương được gọi là số tự nhiên. Giải một phương trình bằng số tự nhiên có nghĩa là tìm tất cả lời giải của nó trong đó các ẩn số lấy giá trị tự nhiên. Bằng cách tìm kiếm toàn diện, xem xét tất cả các bộ ba số tự nhiên một cách riêng biệt, hãy giải quyết tính tổng quát bài toán này: có vô số ba số tự nhiên như vậy. Vì vậy, trước sự bạo lực, cần phải bằng cách nào đó giảm thiểu một số trường hợp hữu hạn. Sẽ thuận tiện hơn cho chúng ta khi thực hiện lại

cạnh nếu chúng ta thay đổi một chút các điều kiện bài toán.
Bài toán 3’. Giải hệ bằng số tự nhiên

$\begin{cases} \frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1, \\ x \leqslant y \leqslant z. \end{cases}$

Lời giải bài toán 3’. Rõ ràng,

$\frac{1}{x} \geqslant \frac{1}{y} \geqslant \frac{1}{z}.$

Trước tiên chúng ta hãy giả sử rằng $x > 3$ . Sau đó

$\frac{1}{3} > \frac{1}{x} \geqslant \frac{1}{y} \geqslant \frac{1}{z},$

Ở đâu

$\frac{1}{x} + \frac{1}{y} + \frac{1}{z} < \frac{1}{3} + \frac{1}{3} + \frac{1}{3},$

đó là trái với điều kiện. Vì vậy, $x$ không thể bằng bất kỳ giá trị nào khác ngoài 1, 2 và 3. (Hãy xem chúng tôi đã giảm tìm kiếm đáng kể như thế nào!)

$x = 1$ . Sau đó

$\frac{1}{y} + \frac{1}{z} = 0,$

chero không thể được.
2) $x = 2$ . Sau đó

$\frac{1}{y} + \frac{1}{z} = \frac{1}{2}.$

Nếu $y > 4$ thì

$\frac{1}{4} > \frac{1}{y} \geqslant \frac{1}{z},$

Ở đâu

$\frac{1}{y} + \frac{1}{z} < \frac{1}{4} + \frac{1}{4},$

chero không thể được. Vì vậy, $y$ không thể bằng bất kỳ giá trị nào khác ngoài 2, 3 và 4. Thay thế từng giá trị này, chúng tôi tin rằng $y = 2$ không phù hợp và hai giá trị còn lại cho hai đáp số: (2, 3, 6) và (2, 4, 4).
3) $x = 3$ . Sau đó

$\frac{1}{y} + \frac{1}{z} = \frac{2}{3}.$

Nếu $y > 3$ thì

$\frac{1}{3} > \frac{1}{y} \geqslant \frac{1}{z},$

Ở đâu

$\frac{1}{y} + \frac{1}{z} < \frac{1}{3} + \frac{1}{3},$

chero không thể được. Vì vậy, trong trường hợp này, chúng ta chỉ cần xem xét một giá trị 3 cho $y$ , giá trị này mang lại một giá trị khác đáp số: (3, 3, 3).

Tất cả các trường hợp đã được giải quyết. Bài toán 3’ lời giải. Nó có ba đáp số: (2, 3, 6), (2, 4, 4), (3, 3, 3).

Ngược lại, bài toán 3 có một danh sách khác đáp số là kết quả của tất cả các hoán vị có thể có này. Đây là đáp số bài toán 3:

(2, 3, 6), (2, 6, 3), (3, 2, 6),
(3, 6, 2), (6, 2, 3), (6, 3, 2),
(2, 4, 4), (4, 2, 4), (4, 4, 2), (3, 3, 3).

(Trong mỗi đáp số này, số đầu tiên là giá trị $x$ , số thứ hai là giá trị $y$ , số thứ ba là giá trị $z$ .)

Trong các bài toán chúng ta đã giải cho đến nay, cần phải tìm tất cả đáp số thỏa mãn một điều kiện nhất định. Để chứng minh rằng một đối tượng như vậy không tồn tại, cần phải tách tất cả các trường hợp hoặc tiến hành suy luận tổng quát. Để chứng minh rằng một vật thể như vậy tồn tại, chỉ cần đưa ra một ví dụ là đủ. Đây là hai bài toán thuộc loại này.

Bài toán 4. Biết rằng đối với hai tam giác $ABC$ và $A'B'C'$ thì thỏa mãn ba điều kiện sau:

$\angle A = \angle A', AB = A'B', BC = B'C'.$

Các tam giác $ABC$ và $A'B'C'$ có thể bằng nhau không?

Đáp số: họ có thể.

Bằng chứng. Chúng ta hãy dựng hai tam giác không bằng nhau mà các đẳng thức trong điều kiện là đúng. Hãy lấy một góc nhọn $A$ và đặt đoạn $AB$ (hình 2) ở một bên của nó. Hãy vẽ một đường tròn có tâm $B$ và bán kính nhỏ hơn $AB$ nhưng lớn hơn khoảng cách từ điểm $B$ đến phía bên kia của góc. Đường tròn này sẽ cắt cạnh kia của góc tại hai điểm mà chúng ta gọi là $C$ và $C'$ . Các tam giác $ABC$ và $ABC'$ không bằng nhau, mặc dù ba điều kiện trên đều được thỏa mãn.

Bài toán 5. Có thể tính $k$ các số khác nhau trong một vòng tròn sao cho từ hai số liền kề có thể tạo thành một số chia hết cho 7 không? Đây $k$ toàn bộ, $3 \le k \le 10$ .

Trên thực tế, tám bài toán khác nhau được giả định ở đây cho tám giá trị khác nhau của $k$ . Nhưng thật thuận tiện khi giải quyết tất cả chúng cùng nhau bằng kỹ thuật sau.

Hãy viết tất cả các số có hai chữ số chia hết cho 7 (hình 3). Sau đó, chúng ta vẽ tất cả mười số trên giấy và nối những đường thẳng tạo nên bất kỳ số có hướng nào (hình 4). Việc sắp xếp các số $k$ theo cách yêu cầu cũng giống như tổng số $k$ của các vòng tròn khác nhau và quay về đầu đường dẫn.

Như bạn có thể thấy, tất cả các con số đều nằm rải rác ở ba “hòn đảo”. Hiện tại rõ ràng là không thể sắp xếp nhiều hơn năm chữ số theo cách yêu cầu. Và bạn có thể sắp xếp ba, bốn hoặc năm số. Hãy tự mình viết ra những sắp xếp cần thiết.

Nhiệm vụ 1. Bốn phát biểu được đưa ra về tam giác $ABC$ :
a) tam giác $ABC$ đều;
b) tam giác $ABC$ là góc vuông;
c) $AB=BC$ ;
d) $AB=2AC$ .

Chúng ta biết rằng hai trong số những tuyên bố này là đúng và hai tuyên bố còn lại là sai. Chu vi của tam giác $ABC$ có thể bằng bao nhiêu nếu cạnh ngắn nhất của nó bằng 1?

Tìm hai số có bình phương lớn hơn số kia một đơn vị.
Chu vi của tam giác $ABC$ có thể bằng bao nhiêu nếu biết rằng $\angle A=60^\circ$ , $AB=8$ , $BC=7$ ?
Giải phương trình cho số dương

$x^2+y^2+z^2+xyz=20.$

Con ốc sên bò được một đoạn dài thì dừng lại. Sau đó cô rẽ sang $90^\circ$ , bò thêm một đoạn dài một mét nữa rồi dừng lại. Cô ấy đã làm điều này 6 lần liên tiếp: bò 6 đoạn thẳng dài hàng mét, xoay từng đoạn $90^\circ$ sang phải hoặc trái. Khoảng cách giữa điểm bắt đầu và điểm kết thúc cuộc hành trình của cô ấy là bao nhiêu?
Tìm tất cả các số có ba chữ số mà tổng các chữ số của chúng gấp 19 lần.
Trong khoảng trống đầy nắng có hình tam giác gồm rắn, chim sẻ, chuột, bọ cánh cứng và máy cày. Tất cả cùng nhau họ có bốn chân nhiều hơn đầu. Nếu rắn bò đi thì số chân sẽ nhiều hơn đầu bốn chân. Chuột và bọ cánh cứng có bốn chân nhiều hơn đầu. Con bọ và cái cày cùng nhau có hàng trăm chiếc đinh. Có bao nhiêu con vật ở khu đất trống? (Chúng tôi hy vọng rằng mọi người đều biết ai đó không có bao nhiêu: đã - 0, uvorov - 2, chuột - 4, bọ cánh cứng - 6, pashka - 8.)
Khoảng cách $AB$ là 225 km. Vào lúc 12 giờ trưa, một xe buýt xuất phát từ $A$ đến $B$ và cùng lúc đó một xe buýt xuất phát từ $B$ đến $A$ . Xe buýt đến $B$ lúc 6 giờ chiều cùng ngày và dừng 4 điểm trên đường với khoảng thời gian đều đặn mỗi lần 15 phút. Xe buýt đi hết chặng đường không dừng lại và gặp xe buýt ở khoảng cách 90 km tính từ $A$ . Tốc độ của xe buýt có thể là bao nhiêu?
Có thể sắp xếp các số 1, 2, 3, 4, 5, 6, 7, 8, 9 thành một vòng tròn sao cho từ hai chữ số liền kề tạo thành một số đơn giản có hai chữ số? (Chúng tôi xin nhắc bạn rằng một số tự nhiên được gọi là số nguyên tố nếu nó có hai ước số bằng nhau: chính nó và một.)
Tìm ba số có bình phương lớn hơn tổng của hai số còn lại là 3.
Tất cả các đỉnh của một tứ giác nhất định đều nằm trong một hình vuông có cạnh bằng 1.

a) Chu vi của tứ giác này có thể lớn hơn 5 không?

b) Chu vi của tứ giác này có thể lớn hơn 6 không?

Một người đi bộ đi bộ từ điểm $A$ đến điểm $B$ . Một lúc sau, người đi bộ đi theo từ điểm $A$ vào Volospedic. Sau khi lái xe được một giờ,