Matemática discreta, probabilidade e métodos numéricos
Introduzido| English | Significado |
|---|---|
| recurrence/rɪˈkʌrəns/ | relação de recorrência |
| complement/ˈkɒmplɪmənt/ | complementar |
| bisection/baɪˈsekʃn/ | bissecção |
Um comitê ou três papéis diferentes?
- Escolher 3 de 10 estudantes para um comitê resulta em $\binom{10}{3}=120$ grupos. Escolher presidente, secretário e tesoureiro resulta em $10\cdot9\cdot8=720$ atribuições: os papéis distinguem os resultados.
- Antes de calcular, decida o que um resultado registra e se repetições são permitidas. Esta lição conecta contagem e probabilidade com recorrências, raciocínio gráfico e aproximações numéricas.
Conte resultados com as regras declaradas
- De $n$ objetos distintos, selecionar $r$ sem repetição resulta em $n(n-1)\cdots(n-r+1)$ listas ordenadas ou $\binom nr$ subconjuntos desordenados, para $0\le r\le n$. Com repetição permitida, uma lista ordenada tem $n^r$ possibilidades.
- Por exemplo, um código de três letras usando cinco letras disponíveis tem $5^3=125$ resultados se as letras puderem repetir, mas $5\cdot4\cdot3=60$ se não puderem. Uma probabilidade é resultados favoráveis divididos por todos os resultados apenas quando esses resultados são igualmente prováveis.
A three-letter code uses A, B, C, D or E in each position. Repetition is allowed. How many codes are possible?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
There are five choices independently for each of three positions: 5³ = 125. Dividing by 3! would incorrectly merge different ordered codes.
Grafos e retas precisam de suas próprias suposições
- Em um grafo simples não direcionado, arestas conectam vértices distintos, sem arestas repetidas. O grafo completo $K_n$ tem uma aresta por par de vértices não ordenado, logo $\binom n2$ arestas. Uma árvore é conexa e não possui ciclos; com $n\ge1$ vértices, ela tem $n-1$ arestas.
- Para $n$ retas distintas no plano, posição geral significa nenhum par paralelo e nenhuma três passando por um ponto. A $k$-ésima reta encontra as retas anteriores em $k-1$ pontos distintos, adicionando $k$ regiões. Começando com uma região, obtém-se $1+n(n+1)/2$ regiões.
Ordenado ou desordenado?
Decida se posições ou papéis distinguem resultados; verifique repetição separadamente.
How many edges does the complete graph $K_7$ have?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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.
Use o complemento para um valor repetido
- O complemento é o evento em que o evento dado não ocorre. Logo $P(A^c)=1-P(A)$. Para $r$ escolhas independentes uniformes de $n$ valores, o espaço amostral ordenado tem $n^r$ resultados igualmente prováveis.
- Para $r\le n$, os resultados todos distintos totalizam $n(n-1)\cdots(n-r+1)$. Com 3 escolhas de 10 valores, sua probabilidade é $720/1000=0.72$, logo pelo menos uma repetição tem probabilidade $0.28$. Se $r>n$, uma repetição é certa.
Three values are picked independently and uniformly from ten possible values, with replacement. What is the probability of at least one repeated value?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
The all-distinct probability is (10·9·8)/10³ = 0.72. Its complement, at least one repeat, has probability 1 − 0.72 = 0.28.
Independente não significa disjunto
- Independência significa $P(A\cap B)=P(A)P(B)$. Quando $P(B)>0$, a probabilidade condicional é $P(A\mid B)=P(A\cap B)/P(B)$; a independência diz que aprender $B$ não altera a probabilidade de $A$.
- Eventos mutuamente exclusivos têm interseção vazia, logo $P(A\cap B)=0$. Se ambas as probabilidades são positivas, seu produto é positivo e elas não podem ser independentes. Em um único lançamento de dado justo, "par" e "maior que 4" são independentes: sua interseção é $\{6\}$, com probabilidade $1/6=(1/2)(1/3)$.
Two mutually exclusive events with positive probabilities cannot be independent.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
Verifique o modelo binomial antes de sua fórmula
- $X\sim\operatorname{Binomial}(N,p)$ conta sucessos em um número fixo $N$ de ensaios independentes, cada um com dois resultados e a mesma probabilidade de sucesso $p$. Sua média é $Np$ e variância é $Np(1-p)$; para $N=10$, $p=0.3$, estas são 3 e 2.1.
- Neste modelo, zero sucessos tem probabilidade $(1-p)^N$, logo pelo menos um tem probabilidade $1-(1-p)^N$. A amostragem sem reposição geralmente altera a próxima probabilidade de sucesso; uma contagem de ensaios fixa e uma taxa inicial de sucesso sozinhos não estabelecem um modelo binomial.
A binomial variable has $N = 10$, $p = 0.3$. Its variance is
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
$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?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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.
Os dois sorteios são dependentes: após um vermelho, a probabilidade do próximo vermelho é $3/9$, não $4/10$. Assim o modelo binomial declarado não é exato. A probabilidade de dois vermelhos é $(4/10)(3/9)=2/15$, enquanto o modelo binomial daria $0.4^2=0.16$. Equivalentemente, há $\binom42=6$ pares favoráveis não ordenados entre $\binom{10}2=45$ pares igualmente prováveis.
Uma recorrência também precisa de valores iniciais
- Uma recorrência é uma regra que expressa termos de uma sequência usando termos anteriores. Para $a_n=2a_{n-1}$, $n\ge1$, o valor inicial $a_0=3$ fornece $3,6,12,\ldots$ e a forma fechada $a_n=3\cdot2^n$.
- Uma regra de segunda ordem pode exigir dois valores iniciais. Para $a_n=a_{n-1}+a_{n-2}$, $n\ge2$, especificar apenas $a_0$ deixa $a_1$ livre. Defina tanto o domínio da recorrência quanto dados iniciais suficientes para determinar todos os termos.
Verifique uma fórmula, não apenas alguns termos
- Para $b_n=2b_{n-1}+1$, $n\ge1$, com $b_0=0$, tente $b_n=2^n-1$. Ela tem o valor inicial correto, e a substituição resulta em $2(2^{n-1}-1)+1=2^n-1$. A recorrência então determina a mesma sequência por indução.
- Correspondência com finitamente muitos termos não prova uma fórmula para todo $n$. Uma resposta proposta deve satisfazer todos os valores iniciais e a recorrência em toda a faixa declarada; alterar um valor inicial pode mudar toda a sequência.
$b_0=0$ e $b_n=2b_{n-1}+1$ for $n\ge1$. Find $b_5$.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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$ e $a_1=1$, prove $a_n=2^n-1$. Explain why only specifying $a_0=0$ would not determine this sequence.
A fórmula fornece $a_0=0$ e $a_1=1$. A substituição resulta em $3(2^{n-1}-1)-2(2^{n-2}-1)=2^n-1$, logo a indução prova a fórmula para todo $n\ge0$. Se apenas $a_0=0$ fosse dado, a sequência de todos os zeros também satisfaria a recorrência e esse valor inicial, mas teria um $a_1$ diferente. Ambos os valores iniciais são necessários.
O método de Newton usa uma tangente
- Para aproximar uma raiz de uma função diferenciável $f$, use $x_{k+1}=x_k-f(x_k)/f'(x_k)$ sempre que $f'(x_k)\ne0$. O próximo valor é onde a tangente em $x_k$ cruza o eixo horizontal.
- Para $f(x)=x^2-2$, começando em $x_0=1$, obtém-se $x_1=3/2$ e $x_2=17/12\approx1.4167$, próximo de $\sqrt2\approx1.4142$. Começar em 0 torna a fórmula indefinida porque $f'(0)=0$.

Apply one Newton step to $f(x) = x^2 - 3$ from $x_0 = 2$.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
x₁ = x₀ − f(x₀)/f′(x₀) = 2 − (4 − 3)/(2 · 2) = 2 − 1/4 = 1.75, already close to √3 ≈ 1.732.
Um passo definido de Newton nem sempre converge
- Derivadas não nulas nos iterados tornam as atualizações possíveis; elas não garantem convergência. O valor inicial e o comportamento da função importam. Uma iteração pode se afastar de uma raiz ou entrar em um ciclo.
- Para $f(x)=x^3-2x+2$, comece em 0. Então $f(0)=2$, $f'(0)=-2$, logo o próximo valor é 1. Em 1, $f(1)=1$, $f'(1)=1$, logo o próximo valor é 0. A sequência oscila $0,1,0,1,\ldots$ mesmo que ambas as derivadas sejam não nulas.
A favor $f(x)=x^3-2x+2$, Newton iteration starts at 0. It alternates between 0 and 1. What does this show?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
A bisseção mantém uma caixote certificado
- A bisseção é um método de busca de raízes que repete metade de um intervalo mantendo uma raiz. Exija $f$ contínua em $[a,b]$ e $f(a)f(b)<0$; o teorema do valor intermediário garante pelo menos uma raiz. Se uma extremidade já for uma raiz, retorne-a.
- Teste $c=(a+b)/2$. Se $f(c)=0$, pare; caso contrário, mantenha a metade com sinais opostos nas extremidades. A continuidade importa: $1/x$ tem sinais opostos em $-1$ e 1, mas é indefinido em 0 e não possui raiz.
Transforme a largura do intervalo de virada em um limite de erro
- Se o intervalo inicial tiver comprimento $L$, após $k$ halving retidos sua largura será $L/2^k$. O ponto médio desse intervalo atual está dentro de $L/2^{k+1}$ de uma raiz retida. Esse ponto médio pode não ser o último ponto já testado.
- Para $x^2-2$ em $[1,2]$, os primeiros intervalos retidos são $[1,1.5]$ e $[1.25,1.5]$. Após dois halving, o ponto médio atual é $1.375$ com erro de no máximo $0.125$. Após quatro halving, o limite de erro do ponto médio é $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?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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]$.
O polinômio é contínuo, com $f(1)=-1$ e $f(2)=5$. Em $1.5$, $f(1.5)=0.875>0$, portanto mantenha $[1,1.5]$. O comprimento original é 1, e após k halving retidos, o erro atual do ponto médio é no máximo $1/2^{k+1}$. Cinco halving resultam em $1/64>0.01$; seis resultam em $1/128<0.01$, logo seis bastam e são o menor número certificado por este limite. A função $1/x$ não é contínua em $[-1,1]$ e não possui raiz; sinais opostos isoladamente não atendem às hipóteses do teorema.
Não invierta um teorema sem verificar
- Uma árvore tem $n-1$ arestas, mas apenas essa contagem de arestas não torna um grafo uma árvore. Um triângulo mais um vértice isolado tem 4 vértices e 3 arestas, porém é desconexo e possui um ciclo. Para um grafo simples não direcionado, a conectividade junto com $n-1$ arestas implica sim uma árvore.
- Uma mudança de sinal através de uma função contínua garante uma raiz; uma raiz não precisa dar lugar a uma mudança de sinal. A função $x^2$ tem uma raiz em 0, mas valores positivos em ambas as extremidades de $[-1,1]$. A falha no teste de mudança de sinal não é prova de que nenhuma raiz existe.
O que o teste declarado estabelece?
Distinguir uma raiz da bisseção, um passo de Newton definido e uma condição de método ausente.
Mantenha o modelo e a garantia separados
- Enuncie ordens, repetição e suposições de igual probabilidade antes de contar probabilidades. Verifique independência e probabilidade constante de sucesso antes de usar um modelo binomial. Verifique fórmulas de recorrência contra tanto a regra quanto seus valores iniciais.
- Uma atualização de Newton exige uma derivada não nula, mas ainda pode ciclar. A bisseção exige um intervalo de mudança de sinal contínuo; sua largura retida fornece um limite rigoroso de erro do ponto médio. Distinga condições suficientes das necessárias.
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) Um triângulo mais um vértice isolado é um grafo simples com 4 vértices e 3 arestas. É desconexo e contém um ciclo, logo não é uma árvore. A conectividade é uma condição adicional suficiente com essa contagem de arestas. (ii) A função contínua $f(x)=x^2$ em $[-1,1]$ tem raiz 0, mas ambos os valores das extremidades são iguais a 1. Uma mudança de sinal é suficiente para que uma função contínua tenha uma raiz, mas não é necessária.