Câu hỏi 178
Mùa xuân cuối cùng cũng đã đến ở Cambridge và đã đến lúc chúng ta phải cắt cỏ. Với mục đích giải quyết những vấn đề này, bãi cỏ của chúng tôi bao gồm các cụm cỏ nhỏ được sắp xếp theo lưới hình chữ nhật $m \times n$, nghĩa là với các hàng $m$ chạy theo hướng đông tây và các cột $n$ chạy theo hướng bắc-nam. Để rõ ràng hơn nữa, chúng ta có thể nói rằng các khối của chúng ta nằm ở các điểm mạng
$$
\left\{(x, y) \in \mathbb{Z}^2 \mid 0 \leq x \lt n \text{và} 0 \leq y \lt m \right\}.
$$
Máy móc của chúng tôi bao gồm một đội mowbots giống hệt nhau (hay gọi tắt là "mobots"). Mobot là máy cắt cỏ. Để cắt cỏ, chúng tôi bắt đầu bằng cách chọn đội hình: chúng tôi đặt số lượng mobot tùy thích tại các đám cỏ khác nhau và định hướng đầu của mỗi mobobot theo một hướng nhất định, bắc hoặc đông (không phải nam hoặc tây). Khi có tiếng còi, mỗi mob bắt đầu di chuyển theo hướng chúng ta đã chọn, cắt từng bụi cỏ trên đường đi của nó (bao gồm cả bụi mà nó bắt đầu) cho đến khi rời khỏi bãi cỏ.
Bởi vì mùa xuân còn quá non nên bãi cỏ của chúng tôi khá mỏng manh. Do đó, chúng tôi muốn đảm bảo rằng mỗi đám cỏ đều được cắt một lần và chỉ một lần. Chúng tôi sẽ không xem xét các đội hình không đáp ứng tiêu chí này.
Một điều nữa: hai đội hình được coi là "khác nhau" nếu tồn tại một cụm cỏ mà (1) đối với chính xác một trong các đội hình, mob bắt đầu trên cụm đó hoặc (2) có mob bắt đầu trên cụm cỏ này cho cả hai đội hình, nhưng chúng được định hướng theo các hướng khác nhau.
Chứng minh rằng số lượng mob tối đa bạn cần để cắt cỏ là $m+n-1$.
$$
\left\{(x, y) \in \mathbb{Z}^2 \mid 0 \leq x \lt n \text{và} 0 \leq y \lt m \right\}.
$$
Máy móc của chúng tôi bao gồm một đội mowbots giống hệt nhau (hay gọi tắt là "mobots"). Mobot là máy cắt cỏ. Để cắt cỏ, chúng tôi bắt đầu bằng cách chọn đội hình: chúng tôi đặt số lượng mobot tùy thích tại các đám cỏ khác nhau và định hướng đầu của mỗi mobobot theo một hướng nhất định, bắc hoặc đông (không phải nam hoặc tây). Khi có tiếng còi, mỗi mob bắt đầu di chuyển theo hướng chúng ta đã chọn, cắt từng bụi cỏ trên đường đi của nó (bao gồm cả bụi mà nó bắt đầu) cho đến khi rời khỏi bãi cỏ.
Bởi vì mùa xuân còn quá non nên bãi cỏ của chúng tôi khá mỏng manh. Do đó, chúng tôi muốn đảm bảo rằng mỗi đám cỏ đều được cắt một lần và chỉ một lần. Chúng tôi sẽ không xem xét các đội hình không đáp ứng tiêu chí này.
Một điều nữa: hai đội hình được coi là "khác nhau" nếu tồn tại một cụm cỏ mà (1) đối với chính xác một trong các đội hình, mob bắt đầu trên cụm đó hoặc (2) có mob bắt đầu trên cụm cỏ này cho cả hai đội hình, nhưng chúng được định hướng theo các hướng khác nhau.
Chứng minh rằng số lượng mob tối đa bạn cần để cắt cỏ là $m+n-1$.