Chủ đề này có 28 trả lời

[go out]

Một vườn chuối nằm cạnh một sa mạc. Vườn có 3000 chuối. Chủ rừng muốn vận chuyển chuối đến chợ bằng lạc đà, trên một đoạn km 1000 của sa mạc. Chủ nhà chỉ có một con lạc đà, có thể mang theo tối đa là 1000 chuối ở bất kỳ lần vận chuyển nào và ăn một quả chuối mỗi km nó đi. Số lượng lớn nhất của chuối có thể được giao tại chợ là bao nhiêu?

Mình nghĩ vầy:
Gọi O là điểm xuất phát
Chia đoạn đường làm các điểm dừng chân A,B và C là điểm kết thúc (chợ)
Gọi OA = x và OB = y (y>x)
Đầu tiên mang 1000 quả đến A, đặt 1000 - 2x quả rồi trở về O
Sau đó mang 1000 quả đến B và đặt 1000 - 2y quả rồi trở về
Tiếp tục mang 1000 quả đến A rồi từ A đến B
Đến đây ta thấy số quả chuối từ A đến B cộng với số quả chuối ổ B phải bằng 1000 ( để được lợi nhất, hehe)
Tổng số quả chuối ở A là: 1000 - 2x + 1000 - x= 2000-3x
Số chuối khi lạc đà di chuyển từ A - B: 2000 - 3x -y + x = 2000 - 2x - y
Tổng quả chuối ở B (sau khi Lạc đà đi từ A đến B) là: 2000-2x -y + 1000 - 2y= 3000 - 2x - 3y tiến dần về 1000
kết hợp với tại mỗi vị trí, số Chuối ko wa' 1000 quả tình ra dc số chuối max là 439 quả>
Mình làm dc đến đên thôi Galois làm sao, chỉ với !!!

Bài viết đã được chỉnh sửa nội dung bởi go out: 03-05-2011 - 19:39

[E. Galois]

Gọi A là điểm xuất phát.
Bước 1: Lạc đà mang theo 1000 quả chuối đi từ A đến điểm B sao cho AB = 200km. Nó ăn hết 200 quả cho lượt đi. Đến B, còn 1000 - 200 = 800 quả. Còn phải quay về A nên cần mang về 200 quả (ăn dọc đường). Để lại B: 800 - 200 = 600 quả.

Bước 2: Lặp lại bước 1, ở B bây giờ có 600 + 600 = 1200 quả.

Bước 3: Lạc đà mang theo 1000 quả chuối cuối cùng đi từ A đến điểm B. Nó ăn hết 200 quả trên đường đi. Đến B, còn 1000 - 200 = 800. Vậy số quả ở tại B bây giờ là 1200 + 800 = 2000.

Bước 4: Lạc đà mang theo 1000 quả từ B đi 333,333km đến địa điểm C. Nó ăn hết 333,3 quả chuối dọc đường (333 quả và 1/3 quả chuối), cần mang theo 333 quả (và 2/3 quả chuối ăn dở)dọc đường từ C về B (không thì chết đói). Vậy để lại C: 1000 - 333 - 334 = 333 quả.

Bước 5: Lạc đà lại mang theo 1000 quả từ B đi 333,333km đến địa điểm C. Nó ăn hết 333,3 quả chuối dọc đường (đã ăn hết quả chuối ăn dở)
Còn 1000 - 333 = 667 quả. Vậy bây giờ ở C có: 667 + 333 = 1000 quả.

Bước 6: Từ C đến chợ còn 1000 - 333,333 - 200 = 466,667km. Lạc đà mang nốt 1000 quả còn lại. Ăn mất 467 quả. Còn 1000 - 467 = 533 quả.
(thật ra là còn 533 quả 1/3 nữa)

[go out]

Gọi A là điểm xuất phát.
Bước 1: Lạc đà mang theo 1000 quả chuối đi từ A đến điểm B sao cho AB = 200km. Nó ăn hết 200 quả cho lượt đi. Đến B, còn 1000 - 200 = 800 quả. Còn phải quay về A nên cần mang về 200 quả (ăn dọc đường). Để lại B: 800 - 200 = 600 quả.

Bước 2: Lặp lại bước 1, ở B bây giờ có 600 + 600 = 1200 quả.

Bước 3: Lạc đà mang theo 1000 quả chuối cuối cùng đi từ A đến điểm B. Nó ăn hết 200 quả trên đường đi. Đến B, còn 1000 - 200 = 800. Vậy số quả ở tại B bây giờ là 1200 + 800 = 2000.

Bước 4: Lạc đà mang theo 1000 quả từ B đi 333,333km đến địa điểm C. Nó ăn hết 333,3 quả chuối dọc đường (333 quả và 1/3 quả chuối), cần mang theo 333 quả (và 2/3 quả chuối ăn dở)dọc đường từ C về B (không thì chết đói). Vậy để lại C: 1000 - 333 - 334 = 333 quả.

Bước 5: Lạc đà lại mang theo 1000 quả từ B đi 333,333km đến địa điểm C. Nó ăn hết 333,3 quả chuối dọc đường (đã ăn hết quả chuối ăn dở)
Còn 1000 - 333 = 667 quả. Vậy bây giờ ở C có: 667 + 333 = 1000 quả.

Bước 6: Từ C đến chợ còn 1000 - 333,333 - 200 = 466,667km. Lạc đà mang nốt 1000 quả còn lại. Ăn mất 467 quả. Còn 1000 - 467 = 533 quả.
(thật ra là còn 533 quả 1/3 nữa)

Uh, mình cũng nghĩ tại C phải còn 1000 quả nhưng ko tính đến nước này, hì. BDT mình còn kém wa ^^!

Bài viết đã được chỉnh sửa nội dung bởi go out: 03-05-2011 - 23:52

[hxthanh]

Cách của thầy Galois đúng rùi!

- Em hiểu như thế này:
Với số lượng ban đầu là 3000 quả chuối - thì cần 3 lần vận chuyển đi từ A,
như vậy đến B (cách A x km)
thì còn lại 3000-5x quả chuối. (3 lần đi + 2 lần quay lại mà )
- Ta phải tính toán điểm B này sao cho hợp lý!

• Nếu đến B mà chỉ cần thêm 1 lần chở nữa là chở hết chuối đến chợ, thì khi đến chợ số chuối là:

$3000-5x-(1000-x)=2000-4x$ với điều kiện là $3000-5x \le 1000 \Rightarrow x\ge 400$

$\Rightarrow 2000-4x\le 400$ quả
Để xem phương án này có tối ưu hay không ta xét trường hợp.

• Đến B vẫn cần thêm 2 lần chở mới chở hết chuối!

Lần này từ B chở đến C (cách B y km; C cũng có thể là chợ!)

Do phải đi 3 lần đoạn BC (2 lần đi +1 lần quay lại) mà số chuối ở C chỉ còn
$3000-5x-3y$ quả với điều kiện là $3000-5x \le 2000 \Rightarrow x \ge 200$
Mà rõ ràng là đi đoạn AB tốn chuối nhất (5x)/km trong khi đoạn BC là (3y)/km. Do vậy phải chọn $min(x)=200km$
Khi đó B cách chợ đến 800km vậy C không thể là chợ được vì số chuối ở B chỉ còn $3000-5x-3y=2000-3y$ (Nếu y mà bằng 800km thì... )

Cần một lần vận chuyển nữa từ C đến chợ!. Đến B ta còn $2000-3y$ quả chuối và còn $(800-y)$ km
Như vậy số chuối khi ra đến chợ sẽ là $2000-3y-(800-y)=1200-2y$ quả với điều kiện $2000-3y\le 1000\Rightarrow y\ge \dfrac{1000}{3}\Rightarrow 1200-2y\le \dfrac{1600}{3}$

Như vậy tối đa lạc đà mang ra chợ được $\dfrac{1600}{3}=533,33$ quả chuối!

Bài viết đã được chỉnh sửa nội dung bởi UEVOLI: 10-11-2011 - 21:20

[E. Galois]

Em à, cách của anh mang tới chợ được hơn 533 quả cơ

[khanh3570883]

Em à, cách của anh mang tới chợ được hơn 533 quả cơ

Vậy trên đường về nó chết đói à anh?

[E. Galois]

Đề bài chỉ đặt ra mục tiêu đến được chợ thôi mà, Đến chợ rồi có thể mua thức ăn khác cho nó hoặc là bán nó luôn, mua xe oto

[hxthanh]

Bài này quả thực rất hay!

Thầy Galois có thể khái quát và chọn số liệu sao cho chẵn hơn thì còn hay hơn nữa. Mấu chốt của bài này không phải chỉ là việc chia nhỏ quãng đường đi sao cho hợp lý mà là tìm Min (Max) dựa vào các điều kiện của đề bài.

Cụ thể vấn đề ở đây (giống như cách hiểu của nhóc UEVOLI) là:
Nếu phải cần ít nhất $k$ lần để chở hết được số vật cần di chuyển một quãng đường $x$ thì số quãng đường thực tế phải di chuyển gấp $(2k-1)$ lần quãng đường $x$ (với $k$ lần đi và $k-1$ lần quay lại)
Trong khi đó $(2k-1)x$ cũng là lượng "hao phí" vật trên đoạn đường đó. Rõ ràng $k$ càng nhỏ thì "hao phí" càng thấp. Vậy giải pháp tối ưu của ta là chọn đoạn đường $x$ nhỏ nhất "vừa đủ" để giảm $k$ xuống 1 đơn vị. Lặp lại "chiến thuật" vận chuyển đó đến khi tới đích thì thội!

Thay đổi một vài số liệu đề bài để có một "bài toán đẹp"
Ví dụ như thay 1000km bằng 900km; thay 3000 quả chuối bằng 2700 quả. Thay tối đa một lần chở 1000 quả chuối bằng 900 quả chuối.
Thì kết quả bài toán sẽ là tròn 480 quả chuối được mang ra chợ!

[Minato4]

Cách của thầy Galois đúng rùi!

- Em hiểu như thế này:
Với số lượng ban đầu là 3000 quả chuối - thì cần 3 lần vận chuyển đi từ A,
như vậy đến B (cách A x km)
thì còn lại 3000-5x quả chuối. (3 lần đi + 2 lần quay lại mà )
- Ta phải tính toán điểm B này sao cho hợp lý!

• Nếu đến B mà chỉ cần thêm 1 lần chở nữa là chở hết chuối đến chợ, thì khi đến chợ số chuối là:

$3000-5x-(1000-x)=2000-4x$ với điều kiện là $3000-5x \le 1000 \Rightarrow x\ge 400$

$\Rightarrow 2000-4x\le 400$ quả
Để xem phương án này có tối ưu hay không ta xét trường hợp.

• Đến B vẫn cần thêm 2 lần chở mới chở hết chuối!

Lần này từ B chở đến C (cách B y km; C cũng có thể là chợ!)

Do phải đi 3 lần đoạn BC (2 lần đi +1 lần quay lại) mà số chuối ở C chỉ còn
$3000-5x-3y$ quả với điều kiện là $3000-5x \le 2000 \Rightarrow x \ge 200$
Mà rõ ràng là đi đoạn AB tốn chuối nhất (5x)/km trong khi đoạn BC là (3y)/km. Do vậy phải chọn $min(x)=200km$
Khi đó B cách chợ đến 800km vậy C không thể là chợ được vì số chuối ở B chỉ còn $3000-5x-3y=2000-3y$ (Nếu y mà bằng 800km thì... )

Cần một lần vận chuyển nữa từ C đến chợ!. Đến B ta còn $2000-3y$ quả chuối và còn $(800-y)$ km
Như vậy số chuối khi ra đến chợ sẽ là $2000-3y-(800-y)=1200-2y$ quả với điều kiện $2000-3y\le 1000\Rightarrow y\ge \dfrac{1000}{3}\Rightarrow 1200-2y\le \dfrac{1600}{3}$

Như vậy tối đa lạc đà mang ra chợ được $\dfrac{1600}{3}=533,33$ quả chuối!

 

Mình vẫn chưa hiểu tạii sao bạn lập được điều kiện 3000−5x≤1000 ở trường hợp 1 và điều kiện 3000−5x≤2000 ở trường hợp 2