Có hai chiếc đồng hồ cát: một chiếc chạy hết trong \(4\) phút, chiếc kia chạy hết \(7\) phút. Làm thế nào để bạn đo chính xác \(9\) phút khi phép đo phải bắt đầu vào lần đầu tiên đồng hồ được khởi động? Đồng hồ khác, đếm giây và đoán không được phép. Tất cả những gì bạn phải làm là lật ngược chiếc đồng hồ cát và quan sát khi ngăn trên trống rỗng. Việc quay lại không mất nhiều thời gian. Những gì chúng tôi đang tìm kiếm là một quá trình trong đó sự kết thúc của khoảng thời gian mong muốn chỉ có thể được nhận ra bằng đồng hồ cát.
Chúng tôi gọi đồng hồ có \(4\) phút \(A\) và đồng hồ có \(7\) phút \(B\) . Ban đầu tất cả cát đều ở phía dưới. Chúng tôi khởi động cả hai đồng hồ cùng lúc bằng cách lật chúng lại; Từ thời điểm này trở đi, số phút tìm kiếm \(9\) được tính. Sau đó, bạn luôn có thể giao dịch khi đồng hồ ở trên cùng trống. Bạn không được lật một, một hoặc cả hai đồng hồ, kể cả một đồng hồ vẫn đang chạy. Bạn đợi đến lần sau nó hết. Không được phép dừng lại và đánh dấu; một chiếc đồng hồ trống có thể vẫn đứng. Giải pháp trông như thế này:
- Tại phút \(0\) \(A\) và \(B\) được bắt đầu.
- Tại phút \(4\) \(A\) trống và bị lật. \(B\) tiếp tục chạy không thay đổi.
- Tại phút \(7\) \(B\) trống và bị lật. Vẫn còn \(1\) phút nữa \(A\) .
- Tại phút \(8\) \(A\) trống. Trong \(B\) cát chảy xuống đúng \(1\) phút; do đó \(B\) ngay lập tức được lật lại.
- Tại phút \(9\) \(B\) trống. Đã đến thời điểm bạn tìm kiếm.
Vào phút \(8\) chúng ta lật đồng hồ \(B\) đồng hồ vẫn đang chạy. Vì chúng khởi động lại ở phút \(7\) nên lượng cát đã chảy xuống chính xác sẽ vừa với nút cổ chai trong \(1\) phút. Sau khi lật thì chỉ có lượng nhỏ này ở trên. Bây giờ phải mất \(1\) phút để nhỏ giọt trở lại. Do đó, đồng hồ sẽ trống vào phút \(9\) , không phải sau một lần chạy hoàn chỉnh khác. Vì vậy, chúng tôi đo phút cuối cùng bằng cát đã đi qua. Hình ảnh động cho thấy động thái này:
Lật đồng hồ cát đang chạy cũng hữu ích cho giải pháp chung. Khi nói thời gian còn lại, chúng tôi muốn nói đến thời gian mà cát vẫn cần chảy qua khoang trên. Nếu đồng hồ đầy đủ có thời gian chạy \(c\) và thời gian chạy còn lại của nó là \(r\) , thì lượng cát ở phía dưới tương ứng với thời lượng \(cr\) . Khi bạn lật nó lại, số tiền chính xác này sẽ lên trên cùng. Nếu khoang trên đầy trước thì trống sau và ngược lại. Đối với đồng hồ chạy một phần, thời gian chạy còn lại mới là \(r'\):
$$r'=c-r.$$
Trước đây, phép đo bắt đầu từ lượt đầu tiên. Điều này có nghĩa là “không có thời gian chuẩn bị”: mỗi phút kể từ khi bắt đầu đều được tính. Mặt khác, “có trước” có nghĩa là bạn có thể chuẩn bị đồng hồ trước và khoảng thời gian mong muốn sẽ bắt đầu sau. Ví dụ: chúng tôi khởi động cả hai đồng hồ và quay \(A\) vào phút \(4\) . Nếu \(B\) trở nên trống vào phút \(7\) , phép đo của chúng tôi bắt đầu. Nếu \(A\) trở nên trống vào phút \(8\) , nó sẽ kết thúc. Chúng tôi đo được \(1\) phút; phút \(7\) trước đó không được tính.
Bây giờ chúng tôi xem xét đồng hồ cát tùy ý với thời gian chạy số nguyên dương \(a\) và \(b\) . Chúng tôi gọi thời lượng mong muốn \(T\) . Thời gian nào có thể được đo bằng điều này nếu việc chuẩn bị được cho phép? Ở đây cũng vậy, phần đầu và phần cuối phải được nhận biết bằng một khoảng trống. Vì vậy, bạn không nên bắt đầu đo lường vào một thời điểm nào đó dựa trên cảm giác của mình. Tay cầm vẫn giống như trong câu đố thực tế. Đầu tiên chúng tôi chỉ ra thời gian nào bị loại trừ; thì chúng tôi sẽ chỉ cho bạn cách thực sự đo lường tất cả những phần còn lại.
Trước tiên, hãy lấy đồng hồ có phút \(6\) và \(10\) phút. Cả hai thời gian chạy đều chia hết cho \(2\) . Do đó, cát có thể được chia thành nhiều phần, mỗi phần mất \(2\) phút để đi hết. Khi bạn lật nó lại hoặc đợi đến lần tiếp theo nó trống, chỉ toàn bộ phần được tạo lại. Do đó, tất cả thời gian trống có thể quan sát được đều cách nhau một số phút chẵn. Bạn không thể đo khoảng thời gian \(3\) phút với nó, ngay cả khi bạn chuẩn bị trước đồng hồ bao lâu tùy thích.
Nói chung, hãy để \(g=\gcd(a,b)\) là ước số chung lớn nhất của thời gian chạy. Ban đầu cả hai số hạng còn lại đều là bội số của \(g\) . Khi được xoay \(r\) trở thành \(ar\) hoặc \(br\) ; cả hai vẫn chia hết cho \(g\) . Khi chờ đợi, thời gian dương nhỏ nhất còn lại trôi qua, cũng là bội số của \(g\) . Điều này có nghĩa là tất cả thời gian trống và khoảng cách của chúng vẫn là bội số của \(g\) . Do đó, khoảng thời gian có thể đo được phải thỏa mãn \(g\mid T\) : \(T\) phải chia hết cho \(g\) . Liệu điều đó có đủ hay không vẫn còn phải xem.
Để làm điều này, chúng tôi cho cả hai đồng hồ chạy đi chạy lại hoàn toàn và lật từng chiếc ngay khi nó trống. Cái đầu tiên sẽ trống sau \(a,2a,3a,\ldots\) đơn vị thời gian, cái thứ hai sau \(b,2b,3b,\ldots\) . Chúng ta đang tìm thời gian \(mb\) của đồng hồ thứ hai và thời gian sau đó \(na\) của đồng hồ thứ nhất, giữa đó chính xác là \(T\) . Bổ đề Bézout đảm bảo các số nguyên khớp \(n,m\) nếu \(T\) là bội số dương của \(g\) . Mối quan hệ bạn đang tìm kiếm là::
$$na-mb=T.$$
Các số \(n,m\) do Bézout cung cấp ban đầu có thể âm. Chạy tiêu cực không thể được thực hiện. Tuy nhiên, người ta có thể tăng cả hai số mà không thay đổi khoảng thời gian: chúng ta thay thế chúng bằng \(n+kb/g\) và \(m+ka/g\) , trong đó \(k\) là số nguyên dương đủ lớn. Do đó, cả hai thời gian đều được dịch chuyển một lượng như nhau \(kab/g\) ; sự khác biệt của họ vẫn là \(T\) . Vì vậy, cả hai số đều dương và thời gian cần thiết thực sự là sau khi đồng hồ bắt đầu.
Bây giờ bạn đếm các chu kỳ hoàn chỉnh của mỗi đồng hồ. Khi đồng hồ \(m\) trống, quá trình đo bắt đầu; nó kết thúc khi đồng hồ đầu tiên trống ở lần thứ \(n\) . Có chính xác \(T\) đơn vị thời gian ở giữa. Việc chuẩn bị có thể mất nhiều thời gian. Bằng chứng không hứa hẹn một quá trình đặc biệt ngắn. Với \(T=0\) phần đầu và phần cuối trùng nhau. Điều này chứng minh cho tất cả các mục tiêu số nguyên không âm: Với sự chuẩn bị, khoảng thời gian có thể được đo khi và chỉ khi ước số chung lớn nhất chia hết cho nó:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Quy tắc này không nhất thiết phải áp dụng cho việc bắt đầu đo ngay khi bắt đầu lần đầu tiên. Ví dụ: với \(4\) và \(7\) phút \(g=1\) , nhưng sau \(1\) phút không có đồng hồ nào trống. Vì vậy, bạn không thể nhìn thấy sự kết thúc của phút này. Phép đo từ phút \(7\) đến \(8\) được mô tả ở trên chỉ hoạt động vì việc chuẩn bị không được tính. Bằng chứng do đó trả lời câu hỏi điều gì có thể xảy ra sau khi chuẩn bị. Nếu bạn đang tìm kiếm một quy trình được phép có hoặc không có sự chuẩn bị, việc tìm kiếm có hệ thống sau đây sẽ hữu ích.
Tập lệnh PHP ghi nhớ cả thời gian chạy còn lại và thời gian đã trôi qua kể từ khi bắt đầu đo. Đối với mọi điều kiện như vậy, hãy thử tất cả \(4\) Các khả năng: không có đồng hồ, chỉ có đồng hồ thứ nhất, chỉ có đồng hồ thứ hai hoặc lật cả hai. Sau đó nó đợi cho đến lần tiếp theo nó trống rỗng. giá trị \(-1\) biểu thị sự chuẩn bị; mục nhập start đặt thời gian đo \(0\). Các điều kiện đã biết sẽ không được điều tra lại. Trình tự tìm thấy có được thông qua những người tiền nhiệm của nó. wait chỉ đề cập đến khoảng cách đến lần đổ tiếp theo, không phải là phép đo thời gian bổ sung:
<?php
declare(strict_types=1);
function hourglass(int $a, int $b, int $target, bool $prepare = false): ?array
{
if ($a <= 0 || $b <= 0 || $target < 0) {
throw new InvalidArgumentException('Positive capacities, nonnegative target required.');
}
$root = [0, 0, $prepare ? -1 : 0];
$key = static fn(array $s): string => implode(',', $s);
$queue = new SplQueue();
$queue->enqueue($root);
$previous = [$key($root) => null];
$enqueue = static function (array $next, array $from, array $action)
use ($queue, &$previous, $key): void {
$k = $key($next);
if (!array_key_exists($k, $previous)) {
$previous[$k] = [$key($from), $action];
$queue->enqueue($next);
}
};
while (!$queue->isEmpty()) {
$state = $queue->dequeue();
[$x, $y, $elapsed] = $state;
if ($elapsed === $target) {
$path = [];
for ($k = $key($state); $previous[$k] !== null;) {
[$k, $action] = $previous[$k];
$path[] = $action;
}
return array_reverse($path);
}
if ($elapsed === -1) {
$enqueue([$x, $y, 0], $state, ['start' => true]);
}
for ($mask = 0; $mask < 4; ++$mask) {
$u = ($mask & 1) ? $a - $x : $x;
$v = ($mask & 2) ? $b - $y : $y;
if ($u === 0 && $v === 0) {
continue;
}
$wait = $u === 0 ? $v : ($v === 0 ? $u : min($u, $v));
$nextTime = $elapsed < 0 ? -1 : $elapsed + $wait;
if ($nextTime > $target) {
continue;
}
$enqueue(
[max(0, $u - $wait), max(0, $v - $wait), $nextTime],
$state,
['flip' => $mask, 'wait' => $wait]
);
}
}
return null;
}
foreach ([[4, 7, 9, false], [4, 7, 1, false], [4, 7, 1, true],
[6, 10, 3, true], [5, 5, 10, false], [4, 7, 0, false]] as $case) {
echo json_encode($case), ': ', json_encode(hourglass(...$case)), PHP_EOL;
}
Việc tìm kiếm tìm thấy hoặc trả về một quy trình được phép null, nếu không tồn tại. Nó bao gồm tất cả các phần tiếp theo được phép và yêu cầu chuẩn bị tối đa \((a+1)(b+1)(T+2)\) Hoa Kỳ. Do đó, đầu vào lớn đòi hỏi nhiều bộ nhớ. Số lần chuyển tiếp tìm kiếm được giảm thiểu chứ không phải thời gian chuẩn bị. Thời gian chạy hợp lý và thời gian mục tiêu được chuyển đổi thành số nguyên bằng mẫu số chung. Ví dụ: đối với thời gian chạy không có đơn vị thời gian chung \(1\) và \(\sqrt{2}\), tìm kiếm số nguyên hữu hạn này không phù hợp.