Exercício de probabilidade

O problema

Sejam \(a,b\in]0,1[\) dois números reais entre zero e um. Queremos construir uma moeda que dê cara com probabilidade \(p\) proporcional a \(a\) e coroa com probabilidade proporcional a \(b\). Quanto vale \(p\)?

Solução

Queremos \(p=ac_1\) e \(1-p=bc_2\), onde \(c_1\) e \(c_2\) são constantes positivas que usamos para definir a “proporção”. Dividindo as expressões, obtemos \[\frac{p}{1-p} = \frac{ac_1}{bc_2}\implies p =\frac{ac_1}{ac_1+bc_2}.\]

Grafos sem \(C_4\)

Quantas arestas pode ter um grafo sem que ele contenha um circuito com quatro vértices (\(C_4\))?

Spoiler alert! Vale a pena pensar neste problema antes de ler a discussão abaixo.

Um \(C_4\) é o grafo conexo com 4 vértices, cada um com dois vizinhos. Num grafo sem \(C_4\), cada par de vértices tem no máximo um vizinho comum. Considere o grafo formado por \(k\) cópias de \(K_2\) (grafo completo com dois vértices), em que acrescentamos um vértice novo \(v\) e arestas ligando cada um dos demais vértices a \(v\). Esse grafo é tal que qualquer par de vértices possui um vizinho em comum, e possui \(3k\) arestas.

Outro comentário: num grafo em que cada par de vértices possui um vizinho comum, qualquer nova aresta gera um \(C_4\). (e, se há ao menos 5 vértices, um \(C_5\) também).

Pergunta: o número de arestas de um grafo \(G\) com \(n\) vértices e tal que todo par de vértices possui exatamente um vizinho em comum é único para cada \(n\) fixo?

Para pensar: seja \(G\) um grafo livre de \(C_4\) que possui vértices \(u\) e \(v\) sem vizinhança comum — isto é, \(N(u)\cap N(v)=\varnothing\). É possível que ele seja máximo (no número de arestas)? Em outras palavras, estamos certos de que não existe grafo com mais arestas do que \(G\) e que seja livre de \(C_4\)?

Tamanho importa

Valores Assintóticos

Que número é maior: \(\binom{n}{3}\) ou \(n^2\)?

Nem sempre conseguimos valores exatos em uma contagem. E nem sempre expressões exatas são tão informativas assim.

Responda rápido: existem mais subconjuntos de 3 elementos ou pares ordenados em um conjunto?

Uma estimativa útil (para \(n\) suficientemente grande…): \[\left(\frac{n}{k}\right)^k\leq \binom{n}{k}\leq\left(\frac{en}{k}\right)^k.\]

Pergunta: escolhemos uniformemente ao acaso um grafo (rotulado) com 30 vértices, e contamos o número de circuitos com 5 vértices. Quantos ciclos esperamos encontrar?