Có hai đống đá, một đống có n hòn và đống kia có k hòn. Cứ mỗi phút một máy tự động lại chọn một đống có số hòn đá là chẵn và chuyển một nửa số hòn đá của đống đá được chọn sang đống kia (nếu cả hai đống đều có số hòn đá là chẵn thì máy sẽ chọn ngẫu nhiên một đống). Nếu trong hai đống số hòn đá đều là lẻ thì máy sẽ ngừng làm việc. Hỏi tồn tại bao nhiêu cặp thứ tự (n, k), với n và k là các số tự nhiên không vượt quá 1000, để máy tự động sau khoảng thời gian hữu hạn sẽ dừng

Giải thích

Giả sử n = 2 a u và k = 2 b v , với u và v là các số lẻ. Chúng ta sẽ chứng minh rằng máy tự động nhất thiết sẽ dừng đối với các cặp và chỉ các cặp số (n, k) với a = b. Nếu a = b thì từ cặp (n, k) máy tự động có thể nhận được cặp hoặc . Vì các số (2u + v) và (2v + u) lại là lẻ, nên máy tự động đã làm giảm số mũ của 2 xuống 1 đơn vị. Qua a bước thì số mũ này trở nên bằng 0, và máy tự động sẽ dừng lại. Bây giờ giả sử a < b(trường hợp a > b xét tương tự). Nếu a ⩽ b − 2 , thì từ cặp (n, k) máy tự động có thể nhận được cặp với các số mũ trong lũy thừ của 2 khác nhau. Nếu a = b − 1, thì từ cặp (n, k) máy tự động có thể nhận được cặp lại với các số mũ trong lũy thừa của 2 khác nhau. Dễ dàng thấy rằng trong trường hợp này máy tự động sẽ làm việc mãi mãi không dừng. Chỉ còn việc đếm các cặp số khả dĩ. Có 500 số lẻ không vượt quá 1000, bởi vậy số cặp (n, k) = (2au, 2 b v) với a = b = 0 bằng 5002 ; có 250 số không vượt quá 1000 chia hết cho 2 và không chia hết cho 4, bởi vậy số lượng cặp với a = b = 1 bằng 250 2 . Cứ tiếp tục như vậy, ta nhận được đáp số của bài toán: 50 0 2 + 25 0 2 + 12 5 2 + 6 3 2 + 3 1 2 + 1 6 2 + 8 2 + 4 2 + 2 2 + 1 2 = 333396