Задачка

[Debugger]

В одной плоскости вокруг неподвижной центральной звезды в одном направлении движутся 5 планет. Каждой из них надо 27, 54, 72, 99 и 180 земных лет соответственно для полного оборота вокруг звезды. Назовем парадом планет такое положение, при котором все планеты выстраиваются на одной прямой по одну сторону от звезды. Сколько лет проходит между двумя ближайшими по времени парадами планет?

Я предположил, что надо просто найти наименьшее общее кратное. Нашел я его криво (11880).

Правильный ответ - 1320.

Но сдается мне, что он неправильный. Последняя планета пройдет 7 1/3 полных оборотов, а первая - 48 8/9. То есть, первая планета будет на 8/9 оборота, а последняя - на 1/3. Ну и какой же это парад?

Где ошибка в моей логике или все же "правильный ответ" неверен?

[Хакер]

Ужас.

найти наименьший общий делитель

Есть наибольший делитель и наименьшее кратное. Наименьший делитель для любого набора чисел — это всегда единица.

Можно конечно находить НОК, но это не ответ на вопрос задачи. Это будет ответ на вопрос «через сколько лет произойдёт парад ровно в той же фазе», а не «через сколко лет произойдёт парад (вообще)». Чтобы ответить на актуальный (то есть второй) вопрос, нужно решить уравнение.

[Debugger]

Можно конечно находить НОК, но это не ответ на вопрос задачи. Это будет ответ на вопрос «через сколько лет произойдёт парад ровно в той же фазе», а не «через сколко лет произойдёт парад (вообще)». Чтобы ответить на актуальный (то есть второй) вопрос, нужно решить уравнение.

Точно, спасибо.

Есть наибольший делитель и наименьшее кратное. Наименьший делитель для любого набора чисел — это всегда единица.

Оговорился.

Все же парада через 1320 не будет:

первая планета будет на 8/9 полного оборота, а последняя - на 1/3.

Или я что-то не понял?

[Хакер]

Все же парада через 1320 не будет:

Через 1320 лет после расмотренного тобою. Твоя ошибка в том, что ты считаешь, что период парадов постоянен. Это не доказано.

[Debugger]

Период парадов постоянен. Планеты движутся по окружностям, в одну сторону и равномерно. В честь чего парад должен происходить через разные промежутки времени?

[Хакер]

Период парадов постоянен.

Это «впечатление» или математически доказано? Я не задумывался глубоко на тему. Для двух планет период постоянен точно. Постоянен ли для 5?

[iGrok]

В целом, если я ничего не попутал, связь положения планеты (угла) и времени будет такой:

T - это период обращения.

Соответственно, нас интересуют все t, при которых для всех пяти планет (т.е. для всех пяти T) получаются равные углы.

А дальше меня сбивает с толку модульная арифметика, про которую я всё уже давно забыл.

З.Ы. Хакер, всё-таки если задуматься, период действительно постоянен. Берём начальную точку, все планеты на "нуле" градусов.
Проходит какое-то время, и все планеты встречаются уже в другой точке, предположим, это будет 238 градусов. "Доворачиваем" круг, чтобы они оказались снова на нуле, и.. Следующая встреча будет в той же точке (238 градусов) через то же время. Скорость-то постоянная.

[Debugger]

Программа, помогающая решить задачу (выводит в Debug время парадов).

Код: Выделить всё

Option Explicit

'27, 54, 72, 99 и 180
Const P1 = 27
Const P2 = 54
Const P3 = 72
Const P4 = 99
Const P5 = 180

Function Func(a As Single) As Single
    Func = a - Round(a) + 1
    If Func < 0 Then Func = Func + 1
End Function
Private Sub Form_Load()
    Dim c As Long, w1 As Single, w2 As Single, w3 As Single, w4 As Single, w5 As Single
    For c = 0 To 99999
        w1 = c / P1
        w2 = c / P2
        w3 = c / P3
        w4 = c / P4
        w5 = c / P5
        If (Func(w1)) = (Func(w2)) And _
           (Func(w1)) = (Func(w3)) And _
           (Func(w1)) = (Func(w4)) And _
           (Func(w1)) = (Func(w5)) Then
            Debug.Print c
        End If
    Next
End Sub


Выводит числа с промежутком 11880.
Выходит, в задаче неправильный ответ? Весь мозг уже себе сломал, но 1320 никак не получить (можно поделить НОД на НОК, но смысла в этом действии нет).

[Alec]

Может где ошибка в исходных данных? Ведь ответ 1320 для любой планеты дает нецелое количество оборотов. Но по условию периоды у первой и второй планеты относятся как 1:2, т.е. даже на пальцах можно представить, что встречаться они будут каждые два полных оборота на начальной линии.
Кстати, через каждые 1320 лет парад наступает для 3, 4 и 5 планеты (18 1/3, 13 1/3 и 7 1/3 оборота). А если, например, опечатка у периода второй (не 54, а 45), то и она попадает на этот парад (29 1/3).

[Debugger]

Всё, разобрались. Написал жюри апелляцию, правильный ответ исправили на 11880.

Может где ошибка в исходных данных? Ведь ответ 1320 для любой планеты дает нецелое количество оборотов. Но по условию периоды у первой и второй планеты относятся как 1:2, т.е. даже на пальцах можно представить, что встречаться они будут каждые два полных оборота на начальной линии.

Да. Скорее всего, так и было. Косяк в исходных данных.

[Александр Дмитриев]

А как правильно решать задачку, разобрался? В частности, Хакер прав, что твоя изначальная логика с НОК неверна, хотя и даёт в этом конкретном случае правильный ответ.

[Debugger]

Программка, которая для 101 случайного набора 5 чисел проверяет, постоянен ли период и равен ли он НОК этих чисел.

Код: Выделить всё

Option Explicit

Dim p1 As Long, p2 As Long, p3 As Long, p4 As Long, p5 As Long

Function LCM(ByVal a As Long, ByVal b As Long) As Long
    Dim x As Long, y As Long
    x = a
    y = b
    Do Until x = y
        If x < y Then
            y = y - x
        Else
            x = x - y
        End If
    Loop
    LCM = a * b / x
End Function

Function Func(a As Single) As Single
    Func = a - Round(a)
    If Func < 0 Then Func = Func + 1
End Function

Private Sub Form_Load()
    Randomize
    Dim c As Long, w1 As Single, w2 As Single, w3 As Single, w4 As Single, w5 As Single
    Dim i As Long, LastW As Long
    For i = 0 To 100
        p1 = Rnd * 7 + 7
        p2 = Rnd * 7 + 7
        p3 = Rnd * 7 + 7
        p4 = Rnd * 7 + 7
        p5 = Rnd * 7 + 7
        Debug.Print p1, p2, p3, p4, p5
        LastW = -1
        For c = 1 To 9999999
            w1 = c / p1
            w2 = c / p2
            w3 = c / p3
            w4 = c / p4
            w5 = c / p5
            If (Func(w1)) = (Func(w2)) And _
               (Func(w1)) = (Func(w3)) And _
               (Func(w1)) = (Func(w4)) And _
               (Func(w1)) = (Func(w5)) Then
                If LastW = -1 Then
                    LastW = LCM(LCM(LCM(LCM(p1, p2), p3), p4), p5)
                    If LastW <> c Then
                        Stop
                    Else
                        Debug.Print "1: ", LastW
                    End If
                Else
                    If c = LastW * 2 Then
                        Debug.Print "2: ", c
                        Exit For
                    Else
                        Debug.Print c, LastW * 2, LastW
                        Stop
                    End If
                End If
            End If
        Next
    Next
End Sub


Похоже, эта задача решается именно нахождением НОК. Слишком банально для олимпиадной задачи, даже не верится.

[Александр Дмитриев]

Подсказка: рассмотри случай двух планет с периодами 3 и 5.

[Хакер]

Похоже, эта задача решается именно нахождением НОК

Возьми две планеты с периодами 60 и 1. НОК(60, 1) = 60. Ответ не будет равен 60.

[Александр Дмитриев]

Короче, смотри, сейчас я тебе быстро объясню решение этой задачи. Сначала периоды планет нужно перевести в частоты (измеряющиеся в оборотах в год) (формула ). Потом нужно принять за начало отсчёта углов текущее угловое положение самой медленно двигающейся планеты (совершающей меньше всего оборотов в год). Начало отсчёта будет двигаться вместе с этой планетой. Далее перевести частоты всех остальных планет в полученную систему отсчёта. Для этого вычесть из их частот частоту самой медленной планеты. Далее обратно перевести получившиеся частоты в периоды. Уже для этих периодов (которых будет на единицу меньше, чем планет) найти НОК, которое и будет ответом. Если какие-то из периодов получились дробные, то для нахождения НОК нужно их привести к общему знаменателю, для числителей найти НОК, и итоговое НОК будет равно дроби с числителем, равным получившемуся НОК, и знаменателем, равным общему знаменателю. Если получившуюся дробь можно сократить, то ответ будет целым, если нет - то дробным. Таким образом, даже для миллиона планет даже с дробными периодами парады планет будут существовать и происходить с постоянным периодом.

[Хакер]

Александр Дмитриев, твоё решение основано на итеративном выбросе планет?

[Александр Дмитриев]

Нет, то есть итерация одна. После неё отпадает проблема с тем, что совпадение положения планет может произойти не в начале отсчёта. Если совпадение оставшихся планет произошло не в начале отсчёта, то общего парада планет не будет. Для парада место совпадения должно будет ещё совпадать с началом отсчёта.

[Debugger]

Похоже на правду. Сейчас проверим.