Question

50 БАЛЛОВ ЗА ЛУЧШИЙ!!! На столе лежат книги, которые нужно упаковать. Если их связать по 4, по 5, или по 6 в пачку, то каждый раз останется 1 книга, а если связывать по 7 книг в пачку, то лишних книг не останется. Сколько книг могло быть на столе, если известно, что их число не превосходит 2000. PASCAL

Answer 1

Будем перебирать i от 1 до [2000/7] = 285. Для каждого такого i узнаем, правда ли, что 7i дает остатки 1 при делении на 4, 5 и 6; если это так, то выводим 7i на печать.

Free Pascal Compiler version 3.0.2

var i, n: integer;

begin

   for i := 1 to 285 do

   begin

       n := 7 * i;

       if (n mod 4 = 1) and (n mod 5 = 1) and (n mod 6 = 1) then

           writeln(n);

   end;

end.

Вывод программы:

301

721

1141

1561

1981

Answer 2

Данная задача связана с китайской теоремой об остатках. Для ее решения можно использовать метод последовательного перебора всех возможных значений числа книг на столе.

Для начала заметим, что число книг на столе должно иметь остаток 1 при делении на 4, 5 и 6. Также оно должно иметь остаток 0 при делении на 7. Минимальное такое число можно найти с помощью китайской теоремы об остатках. Для этого нужно решить следующую систему уравнений:

luaCopy code
x ≡ 1 (mod 4)
x ≡ 1 (mod 5)
x ≡ 1 (mod 6)
x ≡ 0 (mod 7)

Первые три уравнения говорят о том, что число x имеет остаток 1 при делении на 4, 5 и 6. Это эквивалентно тому, что x = 4a + 1, x = 5b + 1 и x = 6c + 1 для некоторых целых a, b и c. Подставляя эти выражения в четвертое уравнение, получаем:

luaCopy code
4a + 1 ≡ 0 (mod 7)
5b + 1 ≡ 0 (mod 7)
6c + 1 ≡ 0 (mod 7)

Откуда следует, что 4a ≡ 6, 5b ≡ 6 и 6c ≡ 6 по модулю 7. Это можно переписать в виде:

luaCopy code
a ≡ 4 (mod 7)
b ≡ 5 (mod 7)
c ≡ 6 (mod 7)

Таким образом, мы получили следующие выражения для x:

makefileCopy code
x = 4a + 1 = 4(7k + 4) + 1 = 28k + 17
x = 5b + 1 = 5(7k + 5) + 1 = 35k + 26
x = 6c + 1 = 6(7k + 6) + 1 = 42k + 37

где k - произвольное целое число.

Теперь мы можем перебрать значения k от 0 до 2000 и проверить, какие из полученных выражений удовлетворяют условию x ≤ 2000. Вот соответствующий код на Pascal:

arduinoCopy code
program Books;

var
  x, k: integer;

begin
  for k := 0 to 2000 do
  begin
    x := 28*k + 17;
    if x <= 2000 then
      if (x mod 5 = 1) and (x mod 6 = 1) then
      begin
        writeln(x);
        break;
      end;
    x := 35*k + 26;
    if x <= 2000 then