Đáp án vấn đề 'vịt và rùa' khám xét bạn có thông minh sáng dạ hơn học sinh lớp 3

Đề bài: 

Oliver sắp đặt các chú vịt và rùa đồ chơi của em thành một hàng như hình sau đây.

Oliver muốn xếp đặt tất cả vịt sang bên trái và rùa sang bên phải, tuy thế em chỉ được phép đổi chỗ hai đồ chơi liền kề trong mỗi lần di chuyển. Oliver phải di chuyển đồ chơi nhỏ nhất bao nhiêu lần để xếp được hàng như mong được?

Đáp án: 17 lần.

Có hai cách sắp đặt tối ưu nhất dành tặng Oliver là di chuyển hết số vịt sang trái hoặc di chuyển hết số rùa sang phải.

- Cách 1: Di chuyển hết vịt sang trái.

Từ trái qua phải, nhiều chú vịt lần lượt ở vị trí địa lý 1, 3, 5, 8, 10 và 11. 

Để toàn bộ vịt bên cạnh trái, Oliver cần rung chuyển nhiều chú vịt về địa điểm 1, 2, 3, 4, 5 và 6. 

Mỗi lần di chuyển, vịt sẽ rung chuyển sang trái những nhất một vị trí. Số lần Oliver phải chuyển dịch đồ chơi bằng tổng số lần đổi thay vị trí của mỗi chú vịt.

Vậy số lần chí ít Oliver phải di chuyển để xếp được hàng như mong muốn được là
 (1-1) + (3-2) + (5-3) + (8-4) + (10-5) + (11-6) = 17 lần.

- Cách 2: Di chuyển hết rùa sang phải.

Từ phải qua trái. các chú rùa lần lượt ở địa điểm 2, 4, 6, 7 và 9.

Oliver cần dịch chuyển những chú rùa về địa điểm 7, 8, 9, 10 và 11.

Vậy số lần ít ra Oliver phải di chuyển để xếp được hàng như mong muốn là
 (7-2) + (8-4) + (9-6) + (10-7) + (11-9) = 17 lần.

>>Xem lời giải gốc

Thanh Tâm