Câu hỏi 55
Cho $N$, $k$ là số nguyên dương với $k \le N$. Một trò chơi nhỏ $(N, k)$-Mountain Tetris được chơi trên lưới $N \times N$. Đường viền * tăng dần * là bất kỳ đường dẫn nào trên lưới được làm bằng các đoạn ngang và dọc, bắt đầu từ $(0, 0)$ và đạt đến $(N, N)$ mà không bao giờ đi xuống hoặc quay lại. Mỗi trò chơi nhỏ $(N, k)$-Mountain Tetris đều bắt đầu với một ngọn núi có đường viền * tăng dần ban đầu * bắt đầu từ $(0, 0)$ theo chiều ngang và có chính xác $k$ nằm ngang và $k$ các đoạn dọc. Một tảng đá $1 \times 1$-square rơi thẳng đứng từ một khe ngẫu nhiên trên trần lưới. A * di chuyển * bao gồm việc dịch chuyển đơn vị ROCK 1 sang phải. Trò chơi sẽ thắng nếu người chơi thực hiện số lần di chuyển tối thiểu cần thiết để khi đá lắng xuống núi, hình dạng kết quả vẫn là một đường viền * tăng dần *. Trò chơi sau đó được đặt lại và bắt đầu với một đường viền đường dẫn tăng dần ban đầu mới. Chứng minh rằng số lần di chuyển trung bình được chơi trên tất cả các trò chơi nhỏ $(N, k)$-Mountain Tetris tương đương với $$
\frac{N-k}{k+1}.
$$ Đây là một ví dụ về một trò chơi nhỏ $(6, 4)$ Mountain Tetris với một mini-game ban đầu Đường viền đường đi tăng dần. Người chơi cần một động thái để giành chiến thắng.
\frac{N-k}{k+1}.
$$ Đây là một ví dụ về một trò chơi nhỏ $(6, 4)$ Mountain Tetris với một mini-game ban đầu Đường viền đường đi tăng dần. Người chơi cần một động thái để giành chiến thắng.