בבחינה של 2013 סמססטר א מועד א הייתה את השאלה הבאה: https://drive.google.com/open?id=0B-bVRl5hSfgOY18zWGVmbVd0Mms

ניסיתי להוכיח לעצמי למה תמיד עבור כל s וf אני אמצא את המעגל ולא הצלחתי. אני מניח שזה קשור לחוקי מודולו (כשהמספר הוא אורך המעגל).

בקיצור למה זה נכון ואיזה הסבר פורמלי צריך לתת בבחינה אם יש כזאת שאלה?

your question is not very readable. please use "Writing in Hebrew" hints.

השאלה היא איך באלגוריתם של השאלה (של הצב והארנב עם f ו-s במקום 2 ו1 באלגוריתם המקורי) מוכיחים שעבור כל f ו-s שאני אבחר (כשf>s) תמיד אני אאתר את המעגל ברשימה המקושרת.

The key here is the gcd of f and s. If the gcd is greater than 1, you can construct cases of a cycle where the hare and tortoise will never meet. For example, a length 4 cycle where the hare is one step ahead of the tortoise when

the later first enters the cycle, and f=4, s=2. In such case the hare will stay put, while the tortoise will alternate between one step before and one step after the hare. This example can be generalized to any f,s with gcd greater than 1.

Benny,

If I understood your answer, that means that that we can build a scenario in which the loop will never stop.

That means, that the answer to the question in the test was suppose to be (c), while it was (d) (according to the solution published in the site).

What am I missing?

It turns out my answer was incorrect, because there is no scenario where the tortoise will enter a 4 length cycle and the hare will be just one step ahead. I apologize (probably answering at 00:47 after consuming half a litter of beer was not a good idea :-)

Suppose there is a linear path of length t ("tail") leading to a cycle of length c.

Take a positive integer i such that after i iterations, the tortoise is in the cycle. This means that the product $i\cdot s$ is greater than or equal t. Under this condition, the tortoise will be in location $(i\cdot s-t) \bmod c$ in the cycle, and the hare will be in location $(i\cdot f-t) \bmod c$ on the cycle (location 0 is the point of entry to the cycle). In order to have the two meet, we should have $(i\cdot s-t) \bmod c = (i\cdot f-t) \bmod c$, plus the condition $i\cdot s \geq t$. This reduces to $i\cdot (f-s) = 0 \bmod c$. Taking i to be any large enough multiple of c will guarantee this equality.

Note: $\bmod \ c$ here is just Python's remainder, % c.

**mod** is used in the literature both as an operation, e.g. $15 \bmod 4$, which equals 3, and in a relation, e.g. $15 \equiv 3 \pmod 4$. What I wrote did not completely adhere to these notations. In any case, recalling we are in a Pythonian context, the expression in the "This reduces to …" sentence is

(i * (f-s)) % c == 0.