Интересные задачи

[Gnida]

Задачи взяты из учебника по инфарматики для 8 класса.
---
Доказать что любое целое число больше 7 можно представить в виде суммы произвидений троек и пяторок, тоесть N=3x+5y , N>7
Найти все возможные значения х и у при произвольном N
---
Дробь вида p/q представить в виде суммы дробей 1/n , например 3/7=1/3+1/11+1/231

[myst]

Задача №1

Доказывал, что называется, "в лоб", потому что лень думать.

Математическая индукция:

1. Для N = 7. N = 3*1 + 5*1. Выполняется.
2. Допустим, что для N = 3x + 5y выполняется, тогда для N+1 = 3x + 5y + 1:
   1. при x ≥ 3:
      N+1 = 3(x-3) + 5y + 3*3 + 1 =
      = 3(x-3) + 5y + 10 =
      = 3(x-3) + 5y + 5*2 =
      = 3(x-3) + 5(y+2).
      Выполняется.
   2. при x < 3 и y ≥ 1:
      N+1 = 3x + 5y + 1 =
      = 3x + 5(y-1) + 5 + 1 =
      = 3x + 5(y-1) + 6 =
      = 3x + 3*2 + 5(y-1) =
      = 3(x+2) + 5(y-1).
      Выполняется.
   3. при x < 3 и y < 1:
      (N = 3x + 5y) < 7.

Собственно больше чем на 8-ой класс не тянет.

[Gnida]

Мист , засуньте это ваше теперь в програму и пасчитайте все возможные х и у при N=8432648123482854759275437534 например

[myst]

Опять же, прога тупая как валенок. Только для примера. Естественно, что на ооочень больших числах будет работать медленно.

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

def factor(n):
    for y in range(int((n + 1) / 5)):
        if (n – 5*y) % 3 == 0:
            x = (n – 5*y) / 3
            print n, " = 3*", x, " + 5*", y

З.Ы. переписал на Python, чтобы было понятнее
З.З.Ы. Надеюсь то, что для каждого y существует один и только один х такой, что N = 3x + 5y, доказывать не надо?

[myst]

Задача №2

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

def factor(n):
    print n, " = ",
    while p != 1:
        x = int(q / p) + 1
        print "1/", x, " + ",
        p = p*x - q
        q = q*x
    print "1/", q

Тут гораздо более интересно доказательство того, что такое разложение существует и конечно. Но это надо думать, а мне лень.

Пофикшен баг: не печаталася последняя дробь ряда.

[Gnida]

для первой задачи логическое доказательство основываеца на свойствах остатка после деления любого числа на 5 , а возможные х и у находяца уже из хатябы одной пары изестных х и у , например 5*10+3*20=5(10-3)+3(20+5) так можно сильно сакратить количество циклов паходу.
Втарая задача ришение правильное , а насчет даказательства я даже и не падумал падумать Вобщем мист маладец

[Gnida]

А верную пару х и у в первой задачи можно легко найти проанализировав астатак ат деления на 5 , в общем можно ооочень бысро решать эту задачу для оооооочень больших чисел

[myst]

вариант, но это уже не 8-ой класс

[Gnida]

К сожалению эта только васьмой
Если тебе мист интересно , я сейчас читаю пару книжек , могу интересные задачи которые там будут сюда кидать

[myst]

Кидай-кидай. Тока пусть модеры это в программинг снесут.

[michael]

Вы помедленнее, а то не успеваешь задачу прочитать, myst ответ пишет

[myst]

Ннууу... и где продолжение?!

[Gnida]

Предположим , что у нас есть весы с двумя чашами и по одной штуке гирь массой 1,3,9,3^k граммов , уравновесить груз массой М граммов на весах. Гири конечно можно засовывать и на правую и на левую чашу , как угодно

[michael]

M представляем в троичной системе счисления, далее процедура элементарна. Массы гирь сразу наталкивают на ответ.

[hlamer]

... я сейчас читаю пару книжек , могу интересные задачи которые там будут сюда кидать

Что за книжки из которых задачки, если не секрет ?