Câu đố và đồ thị

59

Câu đố và đồ thị

MP Barbolin

Mọi người đều biết bài toán để đổ, vượt; sự phân chia. Họ đã có nền tảng vững chắc trong việc thực hành các vòng tròn toán học, Câu đố, buổi tối toán học, v.v. Thông thường, những bài toán như vậy được giải “trong tâm trí” và đòi hỏi sự thông minh và khéo léo đáng kể. Việc tìm kiếm lời giải như vậy bài toán theo bất kỳ cách nào đều không khó. Việc chỉ ra con đường ngắn nhất hoặc tất cả các cách có thể lời giải sẽ khó hơn nhiều.

Đáp số Những câu hỏi này có thể được trả lời dễ dàng bằng sơ đồ đồ họa bao gồm các dấu chấm được nối với nhau bằng mũi tên. Các sơ đồ như vậy được gọi là đồ thị.

Bài toán 1. Có hai mục tiêu: một bình sữa đầy 8 lít và hai bình rỗng 5 và 3 lít. Làm thế nào họ có thể chia sữa đều nhau?

Đối với lời giải bài toán chúng tôi sẽ sử dụng biểu đồ. Chúng ta hãy gán một số cho mỗi bình: bình 8 lít là số 1, bình 5 lít là số 2, bình 3 lít là số 3. Chúng ta hãy xem xét các phương án khả thi để đổ đầy bình sau một lần truyền máu.

Lúc đầu bình số 1 đầy, bình số 2 và bình số 3 rỗng.

Chúng ta hãy biểu thị trạng thái này bằng dấu chấm (8.0.0.) (Hình 1). Bây giờ từ bình số 1, bạn có thể đổ năm lít vào bình số 2 hoặc ba lít vào bình số 3. Kết quả là có hai tùy chọn mới để đổ đầy bình (3.5.0.) và (5.0.3.). Chúng tôi cũng sẽ mô tả chúng bằng các dấu chấm và bằng các mũi tên, chúng tôi sẽ chỉ ra rằng chúng được lấy từ phiên bản gốc (8.0.0.) (Hình 2). Không thể có được các lựa chọn khác chỉ bằng một lần truyền máu.

Chúng tôi thực hiện lần truyền máu thứ hai. Để chắc chắn rằng bạn không bỏ lỡ bất kỳ cơ hội nào, chúng ta hãy nhìn vào những người ném bóng theo thứ tự số. Chúng tôi chọn tùy chọn (3.5.0.) (trong bình số 1 - 3 lít, trong bình số 2 - 5 lít, bình số 3 - rỗng). Từ bình số 1, bạn chỉ có thể đổ sữa vào bình số 3, dẫn đến tùy chọn rót mới: (0.5.3.). Trên đồ thị, từ điểm (3.5.0.) ta vẽ một mũi tên đến điểm (0.5.3.) (Hình 3). Từ bình số 2, bạn có thể đổ sữa vào bình số 1 hoặc số 3 (chuyển vào hai bình được coi là hai lần truyền liên tiếp!), nhưng việc đổ vào bình số 1 không đưa ra lựa chọn mới (các phương án kết quả (8.0.0.) đã được xem xét), vì vậy không nên truyền máu. Chuyển sữa từ số 2 sang số 3, chúng ta có một phương án mới (3.2.3.), chúng ta thể hiện điều này trên biểu đồ bằng dấu chấm (3.2.3.) (Hình 3). Cái bình số ba rỗng nên có thể bỏ qua.

Tiếp theo chúng ta chuyển sang tùy chọn (5.0.3.). Lập luận tương tự như trên, ta có một phương án khác

60

(5.3.0.) và theo đó, có thể truy cập được biểu đồ.

Bây giờ rõ ràng là quá trình lời giải có xu hướng “phát triển” một cây biểu đồ. Tiếp tục lý luận, tiến tới biểu đồ trong Hình 4.

Nó hiển thị hai chuỗi đến từ điểm (8.0.0.) và kết thúc bằng tùy chọn mong muốn (4.4.0.). Chúng tương ứng với hai cách khác nhau

Cơm. 1
(8.0.0.)
(3.5.0.) (5.0.3.)

Cơm. 2.
(8.0.0.)
(3.5.0.) (5.0.3.)
(0.5.3.) (3.2.3.) (5.3.0.)

Cơm. 3.
(8.0.0.)
(3.5.0.) (5.0.3.)
(0.5.3.) (3.2.3.) (5.3.0.)
(6.2.0.) (2.3.3.)
(6.0.2.) (2.5.1.)
(1.5.2.) (7.0.1.)
(1.4.3.) (7.1.0.)
(4.4.0.) (4.1.3.)

Cơm. 4.
(4.4.0.)

tràn mong muốn:
Phương pháp I: (8.0.0.) → (3.5.0.) → (3.2.3.) → (6.2.0.)→ (6.0.2.)→ (1.5.2.)→ (1.4.3.)→ (4.4.0.).
Phương pháp II: (8.0.0.) → (5.0.3.) → (5.3.0.)→ (2.3.3.)→ (2.5.1.)→ (7.0.1.)→ (7.1.0.)→ (4.1.3.)→ (4.4.0.)

Bài toán 2. Người vận chuyển (P) cần vận chuyển một con sói (B), một con dê (K) và một bao bắp cải (M) qua sông. Chiếc thuyền nhỏ đến mức ngoài người vận chuyển, chỉ có thể mang theo một đồ vật. Ngoài ra, bắp cải không thể để cho dê, và dê không thể để cho sói. Làm thế nào để thực hiện việc vượt biển?

Với mục đích định nghĩa, hãy để mọi người ở bờ trái tại thời điểm ban đầu (L.B.). Hãy mô tả tình huống ban đầu dưới dạng một điểm và biểu thị nó như sau: (V.K.M.P. || -) (Hình 5). Trong chuyến bay đầu tiên, người vận chuyển chỉ được phép mang theo một con dê (vì nó không thể để lại với sói hoặc bắp cải). Kết quả là chúng ta thu được một tình huống mới: (V.M. || K.P.). (sói và cái túi ở bờ trái, con dê và người vận chuyển ở bên phải). Hãy mô tả nó như một điểm và vẽ một mũi tên tới nó -

Cơm. 5.