Matemáticas discretas, probabilidad y métodos numéricos
Introducido| English | Significado |
|---|---|
| recurrence/rɪˈkʌrəns/ | relación de recurrencia |
| complement/ˈkɒmplɪmənt/ | complemento |
| bisection/baɪˈsekʃn/ | bisección |
¿Un comité o tres roles diferentes?
- Elegir 3 de 10 estudiantes para un comité da $\binom{10}{3}=120$ grupos. Elegir presidente, secretario y tesorero da $10\cdot9\cdot8=720$ asignaciones: los roles distinguen resultados.
- Antes de calcular, decide qué registra un resultado y si se permite repetición. Esta lección conecta conteo y probabilidad con recurrencias, razonamiento gráfico y aproximación numérica.
Cuenta resultados con las reglas establecidas
- De $n$ objetos distintos, seleccionar $r$ sin repetición da $n(n-1)\cdots(n-r+1)$ listas ordenadas o $\binom nr$ subconjuntos no ordenados, para $0\le r\le n$. Con repetición permitida, una lista ordenada tiene $n^r$ posibilidades.
- Por ejemplo, un código de tres letras usando cinco letras disponibles tiene $5^3=125$ resultados si las letras pueden repetirse, pero $5\cdot4\cdot3=60$ si no pueden. Una probabilidad es resultados favorables divididos por todos los resultados solo cuando esos resultados son igualmente probables.
A three-letter code uses A, B, C, D or E in each position. Repetition is allowed. How many codes are possible?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
There are five choices independently for each of three positions: 5³ = 125. Dividing by 3! would incorrectly merge different ordered codes.
Los grafos y las rectas necesitan sus propias suposiciones
- En un grafo simple no dirigido, las aristas unen vértices distintos, sin aristas repetidas. El grafo completo $K_n$ tiene una arista por par no ordenado de vértices, luego $\binom n2$ aristas. Un árbol es conexo y no tiene ciclos; con $n\ge1$ vértices, tiene $n-1$ aristas.
- Para $n$ rectas distintas en el plano, posición general significa ningún par paralelo y ninguna triple concurrente. La $k$ª recta entonces cruza las rectas anteriores en $k-1$ puntos distintos, añadiendo $k$ regiones. Empezando con una región se obtienen $1+n(n+1)/2$ regiones.
¿Ordenados o desordenados?
Decida si posiciones o roles distinguen resultados; verifique la repetición por separado.
How many edges does the complete graph $K_7$ have?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Each edge joins a pair of distinct vertices, and K₇ joins every pair: C(7, 2) = 7 · 6 / 2 = 21.
Into how many regions do 5 lines in general position divide the plane?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
The n-th line in general position crosses the earlier n − 1 lines and so adds n regions. Starting from 1 region: 1 + (1 + 2 + 3 + 4 + 5) = 1 + 15 = 16.
Usa el complemento para un valor repetido
- El complemento es el evento que el evento dado no ocurre. Así $P(A^c)=1-P(A)$. Para $r$ selecciones independientes uniformes de $n$ valores, el espacio muestral ordenado tiene $n^r$ resultados igualmente probables.
- Para $r\le n$, los resultados todos distintos numeran $n(n-1)\cdots(n-r+1)$. Con 3 selecciones de 10 valores, su probabilidad es $720/1000=0.72$, así que al menos una repetición tiene probabilidad $0.28$. Si $r>n$, una repetición es segura.
Three values are picked independently and uniformly from ten possible values, with replacement. What is the probability of at least one repeated value?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
The all-distinct probability is (10·9·8)/10³ = 0.72. Its complement, at least one repeat, has probability 1 − 0.72 = 0.28.
Independiente no significa disjunto
- Independencia significa $P(A\cap B)=P(A)P(B)$. Cuando $P(B)>0$, la probabilidad condicional es $P(A\mid B)=P(A\cap B)/P(B)$; la independencia entonces dice que aprender $B$ no cambia la probabilidad de $A$.
- Eventos mutuamente excluyentes tienen intersección vacía, así que $P(A\cap B)=0$. Si ambas probabilidades son positivas, su producto es positivo y no pueden ser independientes. En un lanzamiento de dado justo, "par" y "mayor que 4" son independientes: su intersección es $\{6\}$, con probabilidad $1/6=(1/2)(1/3)$.
Two mutually exclusive events with positive probabilities cannot be independent.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
True. Exclusive means $P(A \cap B) = 0$, but independence needs $P(A \cap B) = P(A)P(B) > 0$.
On one fair six-sided die roll, let A be “even” and B be “greater than 4”. These events are
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
P(A) = 1/2, P(B) = 1/3 and P(A ∩ B) = P({6}) = 1/6. The product test holds, but the intersection is not empty.
Verifica el modelo binomial antes de su fórmula
- $X\sim\operatorname{Binomial}(N,p)$ cuenta éxitos en un número fijo $N$ de ensayos independientes, cada uno con dos resultados y la misma probabilidad de éxito $p$. Su media es $Np$ y varianza es $Np(1-p)$; para $N=10$, $p=0.3$, estas son 3 y 2.1.
- En este modelo, cero éxitos tiene probabilidad $(1-p)^N$, así que al menos uno tiene probabilidad $1-(1-p)^N$. Muestrear objetos sin reemplazo generalmente cambia la siguiente probabilidad de éxito; un conteo de ensayos fijo y una tasa inicial de éxito sola no establecen un modelo binomial.
A binomial variable has $N = 10$, $p = 0.3$. Its variance is
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
$10 \times 0.3 \times 0.7$.
Four independent trials each succeed with probability 0.5. What is the probability of at least one success?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
The complement is four failures, with probability (0.5)⁴ = 1/16. Hence at least one success has probability 15/16 = 0.9375.
A bag contains 4 red and 6 blue counters. Draw two uniformly at random without replacement. A student models the red count as Binomial(2, 0.4). Assess the model and find the probability of two reds.
Los dos sorteos son dependientes: tras un rojo, la probabilidad siguiente de rojo es $3/9$, no $4/10$. Por tanto, el modelo binomial enunciado no es exacto. La probabilidad de dos rojos es $(4/10)(3/9)=2/15$, mientras que el modelo binomial daría $0.4^2=0.16$. Equivalentemente, hay $\binom42=6$ pares favorables sin orden entre $\binom{10}2=45$ pares igualmente probables.
Una recurrencia también necesita valores iniciales
- Una recurrencia es una regla que expresa los términos de una secuencia mediante términos anteriores. Para $a_n=2a_{n-1}$, $n\ge1$, el valor inicial $a_0=3$ determina $3,6,12,\ldots$ y la forma cerrada $a_n=3\cdot2^n$.
- Una regla de segundo orden puede requerir dos valores iniciales. Para $a_n=a_{n-1}+a_{n-2}$, $n\ge2$, especificar solo $a_0$ deja libre $a_1$. Indique tanto el rango de la recurrencia como suficientes datos iniciales para determinar cada término.
Verifique una fórmula, no solo algunos términos
- Para $b_n=2b_{n-1}+1$, $n\ge1$, con $b_0=0$, pruebe $b_n=2^n-1$. Tiene el valor inicial correcto y la sustitución produce $2(2^{n-1}-1)+1=2^n-1$. La recurrencia determina luego la misma secuencia por inducción.
- Coincidir con unos pocos términos finitos no prueba una fórmula para cada $n$. Una propuesta de respuesta debe satisfacer todos los valores iniciales y la recurrencia en todo su rango declarado; cambiar un valor inicial puede alterar toda la secuencia.
$b_0=0$ y $b_n=2b_{n-1}+1$ for $n\ge1$. Find $b_5$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
The verified closed form is bₙ = 2ⁿ − 1. Thus b₅ = 32 − 1 = 31. Direct iteration gives 0, 1, 3, 7, 15, 31.
A favor $a_n=3a_{n-1}-2a_{n-2}$, $n\ge2$, with $a_0=0$ y $a_1=1$, prove $a_n=2^n-1$. Explain why only specifying $a_0=0$ would not determine this sequence.
La fórmula da $a_0=0$ y $a_1=1$. La sustitución produce $3(2^{n-1}-1)-2(2^{n-2}-1)=2^n-1$, por lo que la inducción demuestra la fórmula para todo $n\ge0$. Si solo se diera $a_0=0$, la secuencia de ceros también satisfaría la recurrencia y ese valor inicial, pero tiene una $a_1$ diferente. Ambos valores iniciales son necesarios.
El método de Newton usa una tangente
- Para aproximar una raíz de una función diferenciable $f$, utilice $x_{k+1}=x_k-f(x_k)/f'(x_k)$ siempre que $f'(x_k)\ne0$. El siguiente valor es donde la tangente en $x_k$ intersecta el eje horizontal.
- Para $f(x)=x^2-2$, comenzando en $x_0=1$ se obtienen $x_1=3/2$ y $x_2=17/12\approx1.4167$, cercanos a $\sqrt2\approx1.4142$. Comenzar en 0 en cambio hace que la fórmula sea indefinida porque $f'(0)=0$.

Apply one Newton step to $f(x) = x^2 - 3$ from $x_0 = 2$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
x₁ = x₀ − f(x₀)/f′(x₀) = 2 − (4 − 3)/(2 · 2) = 2 − 1/4 = 1.75, already close to √3 ≈ 1.732.
Un paso definido de Newton no necesariamente converge
- Las derivadas no nulas en las iteraciones permiten las actualizaciones; no garantizan convergencia. El valor inicial y el comportamiento de la función son relevantes. Una iteración puede alejarse de una raíz o entrar en un ciclo.
- Para $f(x)=x^3-2x+2$, comience en 0. Entonces $f(0)=2$, $f'(0)=-2$, por lo que el siguiente valor es 1. En 1, $f(1)=1$, $f'(1)=1$, por lo que el siguiente valor es 0. La secuencia cicla $0,1,0,1,\ldots$ aunque ambas derivadas sean no nulas.
A favor $f(x)=x^3-2x+2$, Newton iteration starts at 0. It alternates between 0 and 1. What does this show?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
The derivatives are −2 at 0 and 1 at 1, so both updates are defined. Neither point is a root, and the two-cycle does not converge.
Bisección mantiene un intervalo acotado certificado
- La bisección es un método de búsqueda de raíces que divide repetidamente un intervalo conservando una raíz. Exija que $f$ sea continua en $[a,b]$ y $f(a)f(b)<0$; el teorema del valor intermedio garantiza al menos una raíz. Si un extremo es ya una raíz, indivértala.
- Pruebe $c=(a+b)/2$. Si $f(c)=0$, deténgase; de lo contrario conserve la mitad con signos opuestos en sus extremos. La continuidad importa: $1/x$ tiene signos opuestos en $-1$ y 1, pero es indefinida en 0 y no tiene raíz.
Convierta el ancho del intervalo en una cota de error
- If the initial bracket has length $L$, after $k$ retained halvings its width is $L/2^k$. The midpoint of that current bracket is within $L/2^{k+1}$ of a retained root. This midpoint need not be the last point already tested.
- For $x^2-2$ on $[1,2]$, the first retained brackets are $[1,1.5]$ and $[1.25,1.5]$. After two halvings, the current midpoint is $1.375$ with error at most $0.125$. After four halvings, the midpoint error bound is $1/32=0.03125$.
An initial continuous sign-change bracket has length 1. After four retained bisection halvings, what is the guaranteed absolute error bound for the midpoint of the current bracket?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
The current width is 1/2⁴ = 1/16. Its midpoint is at most half that width from a retained root: 1/32 = 0.03125. The question asks about the current midpoint, not the last tested midpoint.
A favor $f(x)=x^3-x-1$, justify bisection on $[1,2]$, find the first retained half, and find the least number of retained halvings needed to bound the current midpoint error by 0.01. Explain why the same sign argument cannot be used for $1/x$ on $[-1,1]$.
El polinomio es continuo, con $f(1)=-1$ y $f(2)=5$. En $1.5$, $f(1.5)=0.875>0$, por lo que se retiene $[1,1.5]$. La longitud original es 1, y después de k mitades retenidas, el error actual del punto medio es como máximo $1/2^{k+1}$. Cinco mitades dan $1/64>0.01$; seis dan $1/128<0.01$, así que seis son suficientes y son el número menor certificado por esta cota. La función $1/x$ no es continua en $[-1,1]$ y no tiene raíz; los signos opuestos solos no cumplen las hipótesis del teorema.
No invierta un teorema sin verificar
- Un árbol tiene $n-1$ aristas, pero ese conteo de aristas por sí solo no convierte a un grafo en un árbol. Un triángulo más un vértice aislado tiene 4 vértices y 3 aristas, sin embargo está desconectado y posee un ciclo. Para un grafo simple no dirigido, la conectividad junto con $n-1$ aristas sí implica que sea un árbol.
- Un cambio de signo a través de una función continua garantiza una raíz; una raíz no necesariamente da lugar a un cambio de signo. La función $x^2$ tiene una raíz en 0 pero valores positivos en ambos extremos de $[-1,1]$. El fracaso de la prueba del cambio de signo no es prueba de que no exista ninguna raíz.
¿Qué establece la prueba enunciada?
Distinguir una raíz de biseción, un paso definido de Newton y una condición de método faltante.
Mantenga el modelo y la garantía separados
- Establezca los supuestos de orden, repetición e igual probabilidad antes de contar una probabilidad. Verifique la independencia y la probabilidad constante de éxito antes de usar un modelo binomial. Verifique las fórmulas de recurrencia tanto contra la regla como contra sus valores iniciales.
- Una actualización de Newton necesita una derivada no nula pero aún puede ciclar. Bisección necesita un intervalo de cambio de signo continuo; su ancho retenido proporciona una cota rigurosa del error del punto medio. Distinga las condiciones suficientes de las necesarias.
Assess these claims with counterexamples: (i) Every simple undirected graph with n vertices and n − 1 edges is a tree. (ii) If a continuous function has a root in an interval, its endpoint values have opposite signs.
(i) Un triángulo más un vértice aislado es un grafo simple con 4 vértices y 3 aristas. Es desconectado y contiene un ciclo, por lo que no es un árbol. La conectividad es una condición adicional suficiente con esa cantidad de aristas. (ii) La función continua $f(x)=x^2$ en $[-1,1]$ tiene raíz 0 pero ambos valores en los extremos son iguales a 1. El cambio de signo es suficiente para que una función continua tenga una raíz, pero no es necesario.