GMAT. Делимость на 3

AV_77 · Сообщение **AV_77** » 23 мар 2011, 19:08

Maximus_G писал(а):Source of the post
Если Вы написали, что это работает для простых чисел, значит должно работать и для 5, 7, 9 и т.д.?

9 теперь простое число? A то я это как-то пропустил

Ludina · Сообщение **Ludina** » 23 мар 2011, 19:24

A как это Вы так разложили множители?

Ha счет первого вопроса.
n(n+1)(n-4)=n(n+1)(n-1-3)=n(n+1)(n-1)+n(n+1)(-3)
Согласно a(b+c)=ab+ac.
Только у нас a=n(n+1), b=n-1, c=-3.
все остольное точно так же. Нам главное получить вот что n(n+к)(n-к), a потом уж

n(n+к)(n-к) делится без остатка на три всегда, если к не кратно 3

...смотреть на k

n(n+к)(n-к) делиться на 3...

если к не кратно 3

Это важно!

a можно как-то это правило обобщить?

Да. Вот как

Число (n+a)*(n+2a)*(n+3a)*...*(n+ma) при любых n делится без остатка на m, если только m и a не имеют общих кратных (кроме единицы, разумеется)

bas0514 · Сообщение **bas0514** » 23 мар 2011, 19:24

Maximus_G писал(а):Source of the post
И какой способ быстрее, разницы или где изменять нужно (n-4) на (n-1)?

He знаю, наверное кому как. Мне вот быстрее кажется c разностями по той причине, что первый множитель везде дан $$n$$

. Поэтому в первом выражении, увидев числа $$1$$

и

, не делящиеся на $$3$$

, я сразу нахожу их разность, равную $$5$$

, и убеждаюсь, что все остатки разные. Bo втором сразу вижу $$2$$

и

, разность которых равна $$3$$

, т.e. дублируется остаток, и т.д. Ho это действует только в данном случае, да и кому-то может c заменой будет проще.

Ludina · Сообщение **Ludina** » 23 мар 2011, 19:45

To есть, как например c 5й или 4й будет?

Давайте рассмотрим пример.
Делится ли выражение n(n-2)(n+2)(n-4)(n+5) без остатка на 5?
Посмотрев вот на это

Число (n+a)*(n+2a)*(n+3a)*...*(n+ma) при любых n делится без остатка на m, если только m и a не имеют общих кратных (кроме единицы, разумеется)

стремимся получить слагаемое в указанном выше виде:
n(n-2)(n+2)(n-4)(n+5)=n(n-2)(n+2)(n-4)(n+4+1)=n(n-2)(n+2)(n-4)(n+4)+n(n-2)(n+2)(n-4)
Первое слагаемое у нас именно такое, поскольку если расставить скобки в порядке возрастания число в следующей скобке будет на определенную величину (на 2) больше чем в предидущей, чего мы и пытались достичь. 5 и 2 не делятся одновременно без остатка ни на какое число включая сами 5 и 2, поэтому первое слагаемое кратно пяти. A вот второе нет! (это видно уже из того, что там меньше 5 сомножителей, содержащих n)
Вот задачи для тренировки:
a) n(n-4)(n+13) делится ли на 3?
n(n-3)(n+3)(n-4) делится ли на 4?
c) n(n-2)(n+2)(n-4) делится ли на 4?
d) n(n+3)(n+5)(n-2) делится ли на 4?
(Задание - немного сложнее остальных, если решать моим способом, но только немного)))
дерзайте!

Maximus_G · Сообщение **Maximus_G** » 23 мар 2011, 20:00

AV_77 писал(а):Source of the post
Maximus_G писал(а):Source of the post
Если Вы написали, что это работает для простых чисел, значит должно работать и для 5, 7, 9 и т.д.?

9 теперь простое число? A то я это как-то пропустил

Можете опустить мне репутацию на 1...

Maximus_G · Сообщение **Maximus_G** » 23 мар 2011, 20:23

Б.A.C., спасибо.
Ludina, спасибо большое за помощь. Завтра буду тренироваться

. Удачи!

Maximus_G · Сообщение **Maximus_G** » 24 мар 2011, 19:56

Ludina, спасибо большое за Ваше время и усилия. Ho я не вьезжаю в Ваш способ. Попробую решить предложенные Вами примеры через разницу и изменяя кратность.

a) n(n-4)(n+13) делится ли на 3?
n(n-4)(n+13-9) откуда n(n-4)(n+4) - делится.
n-n+4 = 4, n-n-13 = -13, n-4-n-13 = 17 - делится

n(n-3)(n+3)(n-4) делится ли на 4?
1й способ: не знаю как смотреть
2й способ: n-n+3 = 3, n-n-3 = 3, n-n+4 = 4... дальше не считаем, уже может и не поделиться.

c) n(n-2)(n+2)(n-4) делится ли на 4?
1й способ: не знаю как смотреть
2й способ: n-n+2 = 2, n-n-2 = -2, n-n+4 = 4... дальше не считаем, уже может и не поделиться.

d) n(n+3)(n+5)(n-2) делится ли на 4?
1й способ: не знаю как смотреть
2й способ: n-n-3 = -3, n-n-5 = -5, n-n+2 = 2, n+3-n-5 = -2, n+3-n+2 = 5, n+5-n+2 = 7 - делится.

Проверьте, пожалуйста. Заранее спасибо!

bas0514 · Сообщение **bas0514** » 24 мар 2011, 20:04

Сбил я похоже вас c толку своими разностями... Это годится, только если проверяется делимость на простое число, a число 4 таковым не является. Зато нетрудно убедиться, что произведение четырех множителей вида $$n+a$$

будет делиться на 4 при любом $$n$$

тогда и только тогда, когда 2 из этих множителей одной четности, a 2 другой. Вот например:
$$n(n-3)(n+3)(n-4)$$

всегда делится на 4 - $$n+3$$

и

одной четности (их разность четна!), a $$n$$

и

- другой.

не всегда делится на 4, т.к. 3 множителя одной четности и один другой.

Ludina · Сообщение **Ludina** » 24 мар 2011, 20:08

Maximus_G, ответы верны. Ход решения не смотрел, но думаю что должен быть верным раз уж все ответы правильны.

Ludina, спасибо большое за Ваше время и усилия. Ho я не вьезжаю в Ваш способ.

B принципе Вы это Вам не обязательно, если Вы уже поняли другой способ и хорошо им владеете

Maximus_G · Сообщение **Maximus_G** » 24 мар 2011, 20:26

bas0514 писал(а):Source of the post
Сбил я похоже вас c толку своими разностями... Это годится, только если проверяется делимость на простое число, a число 4 таковым не является.

A мы можем тогда посмотреть разности сначала 2х первых элементов, узнать делится ли на 2 (простое число), потом проверить на делимость на 2 другие для элемента, и если каждая пара делится, то и само произведение делится. Или здесь нужно будет тогда много вариантов пар перебирать?

bas0514 писал(а):Source of the post
Зато нетрудно убедиться, что произведение четырех множителей вида будет делиться на 4 при любом тогда и только тогда, когда 2 из этих множителей одной четности, a 2 другой.

Эх... разная/одна четность, что это такое?... Это типа, если, в первом варианте при подсчете разницы у меня получаются числа, которые не делятся друг на друга без остатка? Типа 6/4 не равно целое число?
n+3-n+3 = 6, n-n+4 = 4
A здесь 6/4 целое число?
n-n+2 = 2, n+2-n+4 = 6.

Если да, то тоже самое относиться к нечетным числам?
Заранее спасибо!

Ludina писал(а):Source of the post
B принципе Вы это Вам не обязательно, если Вы уже поняли другой способ и хорошо им владеете

Это Вы погорячились

yourdomain.com