|
Задача про кучки монет и неведомую сумму |
☑ |
0
Ненавижу 1С
гуру
27.01.14
✎
14:55
|
25 монет раскладывают по кучкам следующим образом. Сначала их произвольно разбивают на две кучки. Затем любую из имеющихся кучек снова разбивают на две кучки, и так далее до тех пор, пока каждая кучка не будет состоять из одной монеты. При каждом разбиении какой-либо кучки на две записывается произведение количеств монет в двух получившихся кучках.
Чему равна сумма всех записанных чисел?
|
|
1
Avganec
27.01.14
✎
15:01
|
(0) 300?
|
|
2
Ненавижу 1С
гуру
27.01.14
✎
15:04
|
(1) да
быстро гуглите ))
|
|
3
Avganec
27.01.14
✎
15:07
|
(2) зачем сразу так? просто математика... если предположить разбие всегда на 1 и n, то получается арифметическая прогрессия, а ее сумма легко считается по формуле...
|
|
4
Ненавижу 1С
гуру
27.01.14
✎
15:10
|
(3) шучу ))
а вдруг при других разбиениях получится другая сумма?
|
|
5
SeraFim
27.01.14
✎
15:10
|
Блин... Интеллектуальная шуточка про тракториста =D
|
|
6
Avganec
27.01.14
✎
15:10
|
(4) поэтому я и поставил знак вопроса, что не уверен про другие варианты, но если подумать, то найдется доказательво и на это
|
|
7
Avganec
27.01.14
✎
15:13
|
(4) если не секрет, откуда эти задачи? особенно про решение уравнения в рациональных числах
|
|
8
Ненавижу 1С
гуру
27.01.14
✎
15:15
|
(7) из интернета все
брожу периодически на разных математических сайтах
|
|
9
Avganec
27.01.14
✎
15:17
|
(8) можете списком поделиться?
|
|
10
Ненавижу 1С
гуру
27.01.14
✎
15:20
|
(9)
dxdy.ru
problems.ru
zaba.ru
|
|
11
Avganec
27.01.14
✎
15:26
|
(10) спасибо
|
|
12
sda553
27.01.14
✎
15:36
|
При разбиении всегда на 1 и n действительно получается
24+23+22+...+1=24*25/2=300
Докажем общую формулу, что при любом разбиении N монет всегда получается N(N-1)/2 методом индукции.
Для 2 и даже 3 монет данное утверждение очевидно.
Пусть оно выполняется для любого количества монет вплоть до n монет. И любое разбиение n монет дает при этих операциях n(n-1)/2
Теперь у нас есть (n+1) монета.
Разделяем это количество на любые две непустые кучки k и m монет k+m=n+1
При этом разбиении мы получаем первое произведение k*m
в дальнейшем мы по отдельности разбиваем кучку k которая дает нам k(k-1)/2 (по утверждению индукции)
и кучку m, которая дает нам m(m-1)/2
Тогда мы получим в итоге
k*m+k(k-1)/2+m(m-1)/2=(2k*m+k^2-k+m^2-m)/2=[(k+m)^2-(k+m)]/2=[(n+1)^2-(n+1)]/2
Утверждение доказано
|
|
13
Ненавижу 1С
гуру
27.01.14
✎
15:58
|
(12) отлично и оригинально
|
|
14
Ненавижу 1С
гуру
28.01.14
✎
11:12
|
другое решение, "на пальцах"
обозначим монеты вершинами, а если они в одной кучке, то соединим их ребром, получаем вначале полный граф из 300 ребер
каждые разбиением мы стираем число ребер произведения кучек, в конце получаем 0
значит всего стерли 300 ребер
|
|
Требовать и эффективности, и гибкости от одной и той же программы — все равно, что искать очаровательную и скромную жену... по-видимому, нам следует остановиться на чем-то одном из двух. Фредерик Брукс-младший