Республиканская юниорская олимпиада по математике. Заключительный этап. 2017-2018 учебный год

$17*04*20*18*$ cаны 45-ке бөлінетіндей әр жұлдызшаны кез келген цифрға ауыстыру керек. Бұны қанша әртүрлі тәсілмен жасауға болады?

Комментарий/решение

Ответ: 990

свойства деления на 5, то что число оканчивается 0 или 5

свойства деления на 9, то что сумма цифр числа делится на 9( спасибо, кэп)

1+7+4+2+1+8=23

Если последняя цифра 0 $\Rightarrow$ конечная сумма цифр(после вписывание цифр в число) = x, 23<x<50 (23+3*9 т.к 3 пустых мест (1)) $\Rightarrow$ x = {27, 36, 45}

Если последняя цифра 5 $\Rightarrow$ конечная сумма цифр(после вписывание цифр в число) = x, 28<x<55 (1) $\Rightarrow$ x = {36, 45, 54}

Представим, что значение всех трех пробелов = 0, тогда будем добавлять единицы до того момента пока сумма цифр не будет равна нужному х.

тогда всего будет добавлено х-23=n единиц. Необходимо посчитать все варианты их расположения, причем каждая единица равносильна другой.

Дальше можно пойти методом перебора, но это капец как долго и скучно поэтому я вывела формулу

Выведем формулу:

Поставим в первый пробел все n единиц, это первый вариант.

Теперь остальные единицы будут сдвигаться вправо на один пробел таким образом:

единица совершает 2 хода, затем возвращается на второй пробел(это за ход не считается) затем следующая единица идет на 2 хода, а прошла только на 1(т.к идет со второго пробела), затем они обе возвращаются на второй пробел, 2 раза ходит следующая и они по очереди сдвигаются на 1 пробел вправо и.т.д. пока все единицы не окажутся в третьем пробеле. 1 ход равносилен одному варианту(объяснение чуть ниже)

Получаем такую формулу(работает только когда пробелов 3)

1(первая позиция)+2+(2 + 1)+(2+2)+...+(2+(n-1)) = 1 + 2*n + $\dfrac{(n-1)n}{2}$

Объяснение формулы: на каждое кол-во единиц в первом пробеле мы находим все возможные варианты расположение единиц во втором и третьем путем их перекладывания, получается что то вроде 5+0, 4+1, 3+2, ..., 0+5.

2) находим кол-во вариантов

1 + (1 + 2*4 + 3*4/2) + (1 + 2*(36-23) + 12*13/2) + (1 + 2*(45-23) + 21*22/2) + (1 + 2*(36-28) + 7*8/2) + (1 + 2*(45-28) + 16*17/2) + (1 + 2*(54-28) + 25*26/2) = 990