Вот тут жена притащила кучу олимпиадных задач, одна из этой кучи показалась забавной:
Напишите на листе с строку числа от 1 до 10, каждое из чисел сложите с номером позиции на которой оно записано. Доказать, что при любой расстановке найдутся две суммы с одинаковой цифрой на конце.
Решение я нашел, интересно, может кто чего другого предложит? (перебор естественно не катит
Здравствуйте, Alglib, Вы писали:
A>Напишите на листе с строку числа от 1 до 10, каждое из чисел сложите с номером позиции на которой оно записано. Доказать, что при любой расстановке найдутся две суммы с одинаковой цифрой на конце.
Пусть перетасованный набор — это числа a[0]..a[9].
Тогда последние цифры — c[i] = i + a[i] (mod 10).
Допустим, что получились 10 разных цифр. То есть, попросту, от 0 до 9.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Alglib, Вы писали:
A>>Напишите на листе с строку числа от 1 до 10, каждое из чисел сложите с номером позиции на которой оно записано. Доказать, что при любой расстановке найдутся две суммы с одинаковой цифрой на конце.
К>Пусть перетасованный набор — это числа a[0]..a[9]. К>Тогда последние цифры — c[i] = i + a[i] (mod 10).
К>Допустим, что получились 10 разных цифр. То есть, попросту, от 0 до 9.
К>Посчитаем: К>sum{i} c[i] = sum{i} i = 45 = 5 (mod 10)
К>С другой стороны, К>sum{i} c[i] = sum{i}(i + a[i]) = sum{i} i + sum{i} a[i] = 45+45 = 0 (mod 10).
К>Неувязочка
Катит, у меня мудренее получилось, одно успокаивает, я решал во втором часу ночи
тока пара занудств (которые на решение не влияют )
1. позиции нумеруются от 1 до 10 (это по математике задача, а не по программированию все-таки )
соответственно, sum{i} i = 55,
2. ну и понятно дело sum{i} a[i] = 55
вот.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Alglib, Вы писали:
A>>Напишите на листе с строку числа от 1 до 10, каждое из чисел сложите с номером позиции на которой оно записано. Доказать, что при любой расстановке найдутся две суммы с одинаковой цифрой на конце.
К>Неувязочка
Попроще:
В каждой из суммируемых строк количество суммируемых нечетных нечетно (и равно пяти). Следовательно, в строке сумм количество нечетных четно. А чтобы все компоненты были различны нужно ровно пять.
Здравствуйте, Les, Вы писали:
Les>Здравствуйте, Кодт, Вы писали:
К>>Здравствуйте, Alglib, Вы писали:
A>>>Напишите на листе с строку числа от 1 до 10, каждое из чисел сложите с номером позиции на которой оно записано. Доказать, что при любой расстановке найдутся две суммы с одинаковой цифрой на конце.
К>>Неувязочка
Les>Попроще: Les>В каждой из суммируемых строк количество суммируемых нечетных нечетно (и равно пяти). Следовательно, в строке сумм количество нечетных четно. А чтобы все компоненты были различны нужно ровно пять.
угу, вот у меня примерно так же получилось, что конечно с одной стороны куль, поскольку, что есть mod в школе не проходят (а задачка школьная), с другой стороны, у Кодта формально строгое док-во
Здравствуйте, Les, Вы писали:
Les>Попроще: Les>В каждой из суммируемых строк количество суммируемых нечетных нечетно (и равно пяти). Следовательно, в строке сумм количество нечетных четно. А чтобы все компоненты были различны нужно ровно пять.
Насчет попроще...
В задаче используются вычисления по модулю 10. Это очевидное и естественное основание.
Действительно, по модулю 2 тоже будет разница.
Давай исследуем этот вопрос.
Для N-ричной системы счисления
S = sum[i=1..N-1] i == N(N-1)/2
Сумма последних цифр сумм номера и перестановки — равна 2S mod N.
Сумма всех цифр подряд — равна S mod N.
проверка S mod N mod 2 != 2S mod N mod 2 (== 0)
в тех случаях, когда S нечетно и не кратно N. Это достигается, если N mod 4 == 2.
проверка S mod N != 2S mod N
в тех случаях, когда S не кратно N. То есть когда N четно.
Для нечетных N существуют перестановки, дающие в сумме со своими номерами уникальные цифры.
Пример — тождественные перестановки:
N=5
0+0=0, 1+1=2, 2+2=4, 3+3=1, 4+4=2
(несложно показать, что для любого нечетного N тождественная перестановка даст уникальные цифры).
показалась забавной:
Перекуём баги на фичи!
