قورباغه ها را بگیر

یک قورباغه روی خط شماره می پرد و شما سعی می کنید آن را بگیرید. پرش و گرفتن همیشه متناوب است. قورباغه از موقعیت \(s \in \mathbb{Z}\) و با هر حرکت آن فاصله \(z \in \mathbb{Z}\) را می پرد (اگر \(z>0\) ، می پرد به راست ، در غیر این صورت اگر به سمت چپ باشد). \(z\) برای هر پرش یکسان است. Snapping شامل تعیین موقعیت عدد صحیح است. هیچ کس نمی داند \(z\) و نه \(s\) . ما نشان می دهیم که راهی برای گرفتن همیشه قورباغه وجود دارد.


اول از همه ، \(a_1 = s\) و \(a_{n+1} = a_n + z = s + n \cdot z\) با \(s,z \in \mathbb{Z}\) .

ما الان انتخاب می کنیم 

$$h:\mathbb{N} \to \mathbb{Z}^2: h(2^k r) = \left ( (-1)^{k+1} \left \lfloor \frac{k+1}{2} \right \rfloor, (-1)^{\frac{r+1}{2}} \left \lfloor \frac{r+1}{4} \right \rfloor \right ) $$

به عنوان تابعی که (دقیقاً) یک تعداد عددی از کل اعداد را به هر تعداد طبیعی اختصاص می دهد. انتخاب این تابع از طریق توابع \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) ، \(\mathbb{N}\) در \(\mathbb{Z}\) و \(g(2^kr) = (k+1, \frac{r+1}{2})\) ، که \(\mathbb{N}\) در \(\mathbb{N}^2\) نقشه به صورت ذهنی ، با انگیزه.

اکنون نشان می دهیم که میزان خاصیت \(h\) ( \(h\) نیز م injثر است ، اما نیازی به این ویژگی نداریم).

اجازه دهید \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . اما بعد

$$h \left ( 2^{2 \cdot 2^{k_1} r_1 - 1} \cdot (4 \cdot 2^{k_2} r_2 - 1) \right ) = (2^{k_1} r_1, 2^{k_2} r_2) = (x,y).$$

از این رو: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) با \(h(m) = (x_m,y_m) = (s, z)\) .

به عنوان مثال ، اگر نوبت ما باشد که در \(n = 88\) کنیم ، \(h(88)=(2,3)\) را محاسبه کرده و \(2 + 88 \cdot 3 = 266\) به عنوان موقعیت انتخاب می کنیم.

سپس دقیقاً پس از حرکت \(m\) با \(x_m + m \cdot y_m = s + m \cdot z = a_m\) انتخاب بر روی قورباغه قرار می گیرد.

علاوه بر \(h\) ، بسیاری از عملکردهای دیگر مانند عملکرد جفت سازی کانتور یا مارپیچ ذهنی امکان پذیر است.

در اینجا یک پیاده سازی ساده در JavaScript وجود دارد:

See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.

بازگشت