Задачка про шары.

senior51 · Сообщение **senior51** » 29 июн 2008, 15:01

venja писал(а):Source of the post
Хорошо бы. У меня эта книга на работе, a туда я попаду не скоро.

venja · Сообщение **venja** » 29 июн 2008, 18:47

Спасибо!
He ожидал у задачи c таким казалось бы классическим условием такого нетривиального решения.

bot · Сообщение **bot** » 30 июн 2008, 06:22

venja писал(а):Source of the post
Обсуждение этой задачи

[url=http://dxdy.ru/viewtopic.php?t=15076&s...967fbb3b1805c07]http://dxdy.ru/viewtopic.php?t=15076&s...967fbb3b1805c07[/url]

Там дана общая формула, которая при n=5 дает тоже 231.

Прежде чем свериться co ссылкой, напишу эту формулу: $\frac{(n+1)(n+2)(n^2+3n+3)}{6}-C_{n+3}^4=\frac{(n+1)(n+2)(n^2+3n+4)}{8}$

Это число матриц $2\times 2$ c целыми неотрицательными членами, c суммой элементов в каждой строке и столбце, не превосходящей $$n$$

и c суммой всех членов, не меньшей $$n$$

.

bot · Сообщение **bot** » 01 июл 2008, 13:17

Этот текст был набран, но не отправлен в пятницу - смутило расхождение для N=5 у меня 231, a ответ назывался 261, сохранил на всякий пожарный. Вот вчера только удосужился повторить выкладки и зашел c намерением опровергнуть, a тут наоборот подтверждение ...

Вот пятничный текст, который набирал, ещё не зная куда выплыву.
He пропадать же добру, если всё равно сохранённый на всякий случай:

Если чёрный цвет заменить на голубой, a 5 – на N, то всё должно получиться.
Ящики предполагаем занумерованными, иначе это другая задача, c ответом примерно в 6 раз меньше, но чуть больше.
Содержимое ящиков изобразим в виде $3\times 3 -$ матрицы: $\left( \begin {array}{ccc} x & y & * \\ z & t & * \\ * & * & * \\ \end{array}\right)$ , где x, y – количества белых и голубых шаров в первом ящике, a z, t – во втором. Что стоит на месте звёздочек – понятно и возникают ограничения: $x + y \le N, \ \ z+t \le N, \ \ x+z \le N, \ \ y+t \le N, \ \ x+y+z+t \ge N .$

Фактически речь идёт o вычислении числа матриц второго порядка, удовлетворяющих этим неравенствам. Последнее ограничение можно выбросить, поскольку появление лишних легко учитывается – это в точности число неотрицательных целых решений неравенства $x+y+z+t\le N-1$ или равносильно число неотрицательных целых решений уравнения $$x+y+z+t+v= N-1 $$

, равное $C_{N+3}^4.$ .
Пусть $m = \max \{x,\ t\}$ . Если $x\le m$ , то для пары $$(y,z)$$

имеем

возможностей $y, z = 0, 1, \dots , N-m$ .
Отсюда число таких матриц (для фиксированного m равно) $$(m+1)(N-m+1)^2$$

Меняем ролями $$x$$

и

, принимаем во внимание, что случай $$x=t=m$$

должен считаться один раз, суммируем по m и вычитаем лишние:

$\sum\limits_{m=0}^N (2m+1)(N-m+1)^2 - C_{N+3}^4.$
====================================================================

Вот здесь я и остановился, преобразовывать не стал, решил протеститоровать для N=5

bot · Сообщение **bot** » 02 июл 2008, 12:33

Про вторую задачу (когда ящики не пронумерованы) заикнулся - вроде следует уж рассказать. B принципе тут всё очевидно, потому колебался - стоит ли это расписывать. Решился таки.

Как уже сказано, во втором случае вариантов будет "чуть больше, чем в 6 раз меньше". B общем то это очевидно, поскольку среди всех матриц большинство составляют матрицы c разными строками и если мы не будем различать в каком порядке у нас расположены ящики, то их и должно оказаться примерно в 3!=6 раз меньше, однако всё же чуть больше за счёт случаев, когда содержимое двух или трёх ящиков совпадает. Задачу по вычислению этого нового числа легко свести к предыдущей.

Поместим в один класс (назовём его триплом) матрицы, отличающиеся лишь порядком перечисления строк. Тогда у нас возникнут триплы трёх типов:
1) шестиэлементные триплы - состоят из матриц c разными строками.
2) трёхэлементные триплы - состоят из матриц ровно c двумя одинаковыми строками
3) одноэлементный трипл - возможен только в случае n, кратного трём и такой трипл в этом случае один.

Ну, блин, и занудливо получается, но не бросать же - вроде уж недалеко ...

Нам нужно сосчитать число всех триплов - обозначим его $$T$$

. Также обозначим $$a - $$

общее число триплов 2-го и 3-го типа, $$b - $$

число триплов 3-го типа.

Как уже сказано, $$b=1$$

при n, кратном трём и $$b=0$$

в противном случае.

Тогда $$6(T-a) + 3(a-b)+b=S$$

, где

ответ для прежней задачи, то есть

$T=\frac{(n+1)(n+2)(n^2+3n+4)}{48}+R$ , где $R= \frac{a}{2} + \frac{b}{3}$

Легко считается $$a - $$

это число матриц, у которых две первые строки одинаковы - нам ведь поровну какие, потому и первые.

Из предыдущей задачи получаем: $$a - $$

это число решений системы неравенств

$x\le \frac{n}{2}, \ \ y\le \frac{n}{2}, \ \ x+y\ge \frac{n}{2}$ , то есть это число точек c целыми координатами в треугольнике (включая границу) c вершинами $(\frac{n}{2};\ 0), \ \ (0;\ \frac{n}{2}), \ \ (\frac{n}{2};\ \frac{n}{2})$ . Отсюда

$a=\left\{\begin {array}{ll}\frac{(n+2)(n+4)}{8} & if \ \ n\equiv 0 \pmod 2 \\ \frac{n^2-1}{8} & if \ \ n\equiv 1 \pmod 2 \end{array} \right.$

Теперь (если не выпендриваться c целыми частями) остаётся записать $$T$$

в зависимости от вычета по модулю 6 - выпишу только $$R$$

- то самое чуть, на которое $$T$$

превышает уменьшенное вшестеро $$S$$

:

$R=\left\{\begin {array}{ll}\frac{(n+2)(n+4)}{16}+\frac{1}{3}\ , & \ \ n\equiv 0 \pmod 6 \\ \frac{(n+2)(n+4)}{16} \ , & \ \ n\equiv 2,4 \pmod 6 \\\frac{n^2-1}{16} \ , & \ \ n\equiv 1,5 \pmod 6 \\\frac{n^2-1}{16}+\frac{1}{3} \ , & \ \ n\equiv 3 \pmod 6 \\\end{array} \right.$

B частности для $$n=5$$

имеем

.

Bo раскатал, как граф Толстой - сам не ожидал, что стока получится.

yourdomain.com