Kate está buscando ordenó triples $(a,b,c)$ de los distintos números enteros tales que a$-47 \leq \; a,b,c \; \leq 47$$a+b+c>0$. ¿Cuántos de esos ordenó triples pueden Kate encontrar?
Mi primer paso fue dejar $a_1=a+47, \; b_1=b+47$$c_1=c+47$, de modo que $a_1+b_1+c_1>141$$0 \leq \; a,b,c \; \leq 94$. Puedo simplemente tienen que resolver para todos los $a_1+b_1+c_1=142, \; 143, \cdots, 282$ y la suma de estos resultados. O hay una mejor manera?
Usted puede resolver el anterior sub problemas utilizando una de las estrellas y las barras de método http://en.wikipedia.org/wiki/Stars_and_bars_(combinatoria)
Respuestas
¿Demasiados anuncios?
CodingBytes
Puntos
102
Discutimos sobre el conjunto de $A_n$ admisible entramado de puntos en el "cubo" $[-n,n]^3\cap{\mathbb Z}^3$. Tenga en cuenta que$A_1=\emptyset$$A_{n-1}\subset A_n$$n\geq2$. Indicar el número de puntos en $A_n$$f(n)$.
Comenzamos con $f(2)$. El conjunto $\{-2,-1,0,1,2\}$ contiene cuatro triples de números diferentes con una suma positiva, es decir,$\{2,1,0\}$, $\{2,1,-1\}$, $\{2,1,-2\}$, $\{2,0,-1\}$. De ello se desprende que $f(2)=24$.
Ahora nos cuente el número de puntos en el conjunto de $\Delta_n:=A_n\setminus A_{n-1}$. Dibujar un cubo, y verás que $\Delta_n$ se compone de tres "cuadrática placas" a partir de la cual un triángulo ha sido quitada, y tres pequeños triángulos de exactamente el mismo tamaño. Haciendo un cuidadoso recuento con la placa de $c=n$, y el pequeño triángulo en la cara $c=-n$ se obtiene $$\#\Delta_n=\cases{3(4n^2-5n+2)\quad &($$ n) \cr 3(4n^2-5n+1)&($n$ impar)\cr}\ .\la etiqueta{1}$$ La distinción entre pares e impares $n$ proviene de la diagonal $a=b$ que tiene que ser eliminado: Si $n$ es incluso hay un punto con $a+b=-n$ en esta diagonal, y cuando se $n$ es impar, no hay tal punto.
Fórmula $(1)$ puede escribirse como $$\#\Delta_n=12n^2 -15n +{9\over2}+{3\over2}(-1)^n\qquad(n\geq3)\ .$$ De ello se sigue que $$f(n)=24+\sum_{k=3}^n\left(12n^2-15n+{9\over2}+{3\over2}(-1)^n\right)\ ,$$ y esto se evalúa a $$f(n)={1\over4}\bigl(16 n^3-6n^2-4n-3+3(-1)^n\bigr)\qquad(n\geq2)\ .\tag{2}$$ Tenga en cuenta que incluso nos $f(1)=0$, aunque en este caso el recuento podría ser considerado como algo sospechoso. (Tengo que admitir que yo también lo hizo la fuerza bruta contar con Mathematica y hasta el $n=47$ obtenido los números producidos por $(2)$.)
En particular,$f(47)=411930$, de acuerdo con @André Nicolás resultado (cuando se desempaquetan) para este caso.
Llanura de Estrellas y Barras no funciona aquí. Los enteros se supone que ser distinta, y la llanura de las Estrellas y las Barras no presta atención a eso. (Se puede ajustar).
Pero no vamos a utilizar. Contamos con las triples $(a,b,c)$ tal que $a\lt b\lt c$, luego se multiplica por $3!$.
La adición de $47$ suena como una buena idea; pero resulta que la simetría de $\pm 47$ es muy útil.
Hay $95$ números en nuestra lista. Supongamos que elegimos $3$ de ellos. Algunas opciones de agregar a a $0$. Algunas opciones tienen de suma positiva. Algunos han de suma negativa. Por simetría, al igual que muchos tienen de suma positiva como negativa en suma.
Así que si queremos encontrar el número de $z$ de opciones con suma $0$, vamos a ser terminado. Para dejar $p$ ser el número con suma positiva. Tenemos $z+2p=\binom{95}{3}$. Podemos resolver para $p$, y encontrar que nuestra respuesta es $$3!\frac{\binom{95}{3}-z}{2}.$$
Ahora sólo queremos encontrar $z$, el número de desordenada triples, o, equivalentemente, triples, con $a\lt b\lt c$, de tal manera que $a$, $b$, y $c$ satisfacer las restricciones de tamaño, y $a+b+c =0$. Mucho más simple!
Temporalmente, se lo dejo a usted para buscar $z$. Que es muy factible.
Búsqueda de $z$: Nos concentramos en el medio plazo. Si esto es$0$, $47$ formas de completar el triple. Ahora mira a medio plazo $1,2,3, \dots$. (Hay muchos con el centro términos de $-1, -2,-3,\dots$.)
Si el término medio es $1$, el grande plazo puede ser cualquiera de $2$$46$, lo $45$ posibilidades, y ahora la pequeña plazo es determinado. Si el término medio es$2$, $43$ posibilidades, y así sucesivamente hasta cuando en el medio plazo es $23$, no sólo es $1$ posibilidad para el gran término, es decir,$24$. Así que el total de positivos a medio plazo es$1+3+5+\cdots +45$,$23^2$. De ello se sigue que $$z=47+(2)(23^2),$$ y hemos terminado.
Comentario: Precisamente el mismo razonamiento funciona si vamos a reemplazar el enlazado $\pm 47$$\pm B$. También se puede tratar con intervalos que son menos abiertamente simétrica. Pero la simetría o cerca de simetría de la condición de $a+b+c$ es crucial para un argumento del tipo anterior.
DiGi
Puntos
1925
Joe Gauterin
Puntos
9526
Deje $N = 47$$X = \{-N,\ldots,N\}$. Tenemos $|X^3| = |X|^3 = (2N+1)^3$.
Deje $\mathscr{N}_{???}$ el número de soluciones de cualquier ecuación ??? implican $(a,b,c) \in X^3$.
Debido a la simetría,
$$\mathscr{N}_{a+b+c>0} = \mathscr{N}_{a+b+c<0} \implies \mathscr{N}_{a+b+c>0} = \frac12 \left((2N+1)^3 - \mathscr{N}_{a+b+c=0} \right)$$
Para cualquier fija $c$, el número de soluciones para$a + b + c = 0$$(2N+1) - |c|$, tenemos:
$$\mathscr{N}_{a+b+c=0} = \sum_{c = -N}^{N} \left( (2N+1) - |c|\,\right) = (2N+1)^2 -2\frac{N(N+1)}{2} = 3N^2+3N+1$$
y por lo tanto
$$\mathscr{N}_{a+b+c>0} = \frac12\left((2N+1)^3 - (3N^2+3N+1)\right) = \frac12 N (8N^2 + 9N + 3) = 425303$$
Método 2
Otra forma de obtener la misma respuesta se tratan de atacar a una pregunta más general:
Dado $n \in \mathbb{Z}$$d, L \in \mathbb{Z}_{+}$, ¿cuál es la número entero de soluciones para $a_1 + a_2 + \cdots + a_d = n$ donde todos los $ 0 \le a_i < L$.
Deje $\varphi_{d}(n)$ $\varphi_{d}(n;L)$ ser la número de número entero no negativo soluciones donde $\sum_{i=1}^{d} a_i = n$ y aquellos con restricción mayor que $a_1,\ldots,a_d < L$. es decir,
$$\begin{align} \varphi_{d}(n) &= \left|\,\{ (a_i) \in \mathbb{N}^{d} : \sum_{i=1}^{d} a_i = n \}\,\right|\\ \varphi_{d}(n;L) &= \left|\,\{ (a_i) \in \mathbb{N}^{d} : \sum_{i=1}^{d} a_i = n \wedge a_1, \ldots a_d < L \}\,\right| \end{align}$$
Por inducción, no es difícil mostrar que:
$$\varphi_{d}(n) = \begin{cases}\binom{n+d-1}{d} = \frac{n(n+1)\cdots(n+d-1)}{d!},& n \ge 0\\ \\0, & n < 0\end{cases}$$
Para calcular los $\varphi_{d}(n;L)$, podemos comenzar con el conjunto de soluciones para $\varphi_{d}(n)$ y, a continuación, se procederá a eliminar esas soluciones con al menos un $x_i \ge L$. Para una primera aproximación, se obtiene:
$$\begin{align}\varphi_{d}(n;L) &= \varphi_{d}(n) - \sum_{j=1}^{d} \left|\{ (a_i) \in \mathbb{Z}^d : \sum_{i=1}^{d} a_i = n \wedge a_j \ge L \}\right| + \cdots\\ &= \varphi_{d}(n) - d \varphi_{d}(n-L) + \cdots\\ \end{align}$$
Sin embargo, para las soluciones con al menos dos $a_i \ge L$, este procedimiento eliminado más de una vez. Necesitamos volver a agregar su contribución. Para la segunda aproximación, se obtiene:
$$\begin{align}\varphi_{d}(n;L) &= \varphi_{d}(n) - d \varphi_{d}(n-L) + \sum_{1 \le j < k \le d} \left|\{(a_i) \in \mathbb{Z}^d : \sum_{i=1}^{d} a_i = n \wedge a_j, a_k \ge L \}\right| + \cdots\\ &= \varphi_{d}(n) - d \varphi_{d}(n-L) + \binom{d}{2} \varphi_{d}(n-2L) + \cdots \end{align}$$
Para las soluciones con al menos tres $a_i \ge L$, esto, de nuevo, volver a agregar demasiado. Podemos utilizar Inclusión-Exclusión para organizar este lío. Al final, tendremos:
$$\varphi_{d}(n;L) = \sum_{k=0}^{d} (-1)^k \binom{d}{k} \varphi_{d}(n - kL) = \sum_{k=0}^{\min(d,\lfloor\frac{n}{L}\rfloor)}(-1)^k \binom{d}{k} \varphi_{d}(n-kL) $$
De vuelta a nuestro problema original, es claro que el número de soluciones para $$a + b + c < 0,\quad|a|, |b|, |c| \le N$$ es igual al número de soluciones para $$x + y + z = 3N,\quad 0 \le x, y, z < 2N+1$$ Desde $\lfloor\frac{3N}{2N+1}\rfloor = 1$, obtenemos:
$$\begin{align}\mathscr{N}_{a+b+c>0} &= \mathscr{N}_{a+b+c<0}\\ &= \varphi_3(3N;2N+1)\\ &= \varphi_3(3N) - \binom{3}{1}\varphi_3(3N-(2N+1))\\ &= \varphi_3(3N) - 3\varphi_3(N-1)\\ &= \frac12 N(3N+1)(3N+2)) - \frac12 (N-1)N(N+1)\\ &= \frac12 N(8N^2+9N+3)\\ &= 425303 \end{align}$$
ACTUALIZACIÓN
Uy, olvidar el requisito de que $a, b, c$ son distintos. Necesitamos contar el casos donde $a, b, c$ falla al ser distintos. Hay dos posibles casos:
- Caso 1, dos de $a, b, c$ es el mismo. Hay 3 posibles subcases. Para el subcase donde$a = b \ne c$, $2N(2N+1)$ combinación. $2 \lfloor\frac{N}{2}\rfloor$ suma $0$. Los otros 2 subcases dar la misma cantidad de contar.
- Caso 2. $a = b = c$. Hay $2N+1$ combinación, sólo 1 de ellos sumas a $0$.
A partir de esto, el número de soluciones para $a + b + c > 0$ $a \ne b \ne c$ está dada por:
$$\begin{align} \mathscr{N}^{distinct}_{a+b+c>0} &= \mathscr{N}_{a+b+c>0} - \frac12\left( (6N+1)(2N+1) - 6\lfloor\frac{N}{2}\rfloor - 1\right)\\ &= \frac12 (N-1)N(8N+5) + 3\lfloor\frac{N}{2}\rfloor\\ &= 411930 \end{align}$$
