Skip to main content
MathOverflow

Return to Answer

Erdos -> Erdős, and other light editing
Source Link
LSpice
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Have you read The Probabilistic Method by Joel Spencer and Noga Alon?

Although originally developed by ErdosErdős, here's an example of the probabilistic method taken from combinatoricist Po-Shen Loh (Po-Shen LohProbabilistic methods in combinatorics):

$A_1, \dots, A_s \subseteq \{ 1, 2, \dots, M \}$$A_1, \dotsc, A_s \subseteq \{ 1, 2, \dotsc, M \}$ such that $A_i \not \subset A_j$ and let $a_i = |A_i|$$a_i = \lvert A_i\rvert$. Show that $$ \sum_{i=1}^s \frac{1}{\binom{M}{a_i}} \leq 1$$$$ \sum_{i=1}^s \frac{1}{\binom{M}{a_i}} \leq 1.$$ The hint is to consider a random permutation $\sigma = (\sigma_1, \dots, \sigma_M)$$\sigma = (\sigma_1, \dotsc, \sigma_M)$. Loh defines the event $E_i$ when $\{ \sigma_1, \dots, \sigma_{a_i}\} = A_i$$\{ \sigma_1, \dotsc, \sigma_{a_i}\} = A_i$. Then he observes the events $E_i$ are mutually exclusive and that $\mathbb{P}(E_i)$ is relevant to our problem..problem….

There are probably a lot of olympiad combinatorics problems that can be solved this way. Err... Err… you were asking for number theory, but you will find both in Spencer and Alon's book.

Have you read The Probabilistic Method by Joel Spencer and Noga Alon?

Although originally developed by Erdos, here's an example of the probabilistic method taken from combinatoricist Po-Shen Loh:

$A_1, \dots, A_s \subseteq \{ 1, 2, \dots, M \}$ such that $A_i \not \subset A_j$ and let $a_i = |A_i|$. Show that $$ \sum_{i=1}^s \frac{1}{\binom{M}{a_i}} \leq 1$$ The hint is to consider a random permutation $\sigma = (\sigma_1, \dots, \sigma_M)$. Loh defines the event $E_i$ when $\{ \sigma_1, \dots, \sigma_{a_i}\} = A_i$. Then he observes the events $E_i$ are mutually exclusive and that $\mathbb{P}(E_i)$ is relevant to our problem...

There are probably a lot of olympiad combinatorics problems that can be solved this way. Err... you were asking for number theory, but you will find both in Spencer and Alon's book.

Have you read The Probabilistic Method by Joel Spencer and Noga Alon?

Although originally developed by Erdős, here's an example of the probabilistic method taken from combinatoricist Po-Shen Loh (Probabilistic methods in combinatorics):

$A_1, \dotsc, A_s \subseteq \{ 1, 2, \dotsc, M \}$ such that $A_i \not \subset A_j$ and let $a_i = \lvert A_i\rvert$. Show that $$ \sum_{i=1}^s \frac{1}{\binom{M}{a_i}} \leq 1.$$ The hint is to consider a random permutation $\sigma = (\sigma_1, \dotsc, \sigma_M)$. Loh defines the event $E_i$ when $\{ \sigma_1, \dotsc, \sigma_{a_i}\} = A_i$. Then he observes the events $E_i$ are mutually exclusive and that $\mathbb{P}(E_i)$ is relevant to our problem….

There are probably a lot of olympiad combinatorics problems that can be solved this way. Err… you were asking for number theory, but you will find both in Spencer and Alon's book.

http -> https (the question was bumped anyway)
Source Link
Martin Sleziak
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Have you read The Probabilistic Method by Joel Spencer and Noga Alon?

Although originally developed by Erdos, here's an example of the probabilistic method taken from combinatoricist Po-Shen LohPo-Shen Loh:

$A_1, \dots, A_s \subseteq \{ 1, 2, \dots, M \}$ such that $A_i \not \subset A_j$ and let $a_i = |A_i|$. Show that $$ \sum_{i=1}^s \frac{1}{\binom{M}{a_i}} \leq 1$$ The hint is to consider a random permutation $\sigma = (\sigma_1, \dots, \sigma_M)$. Loh defines the event $E_i$ when $\{ \sigma_1, \dots, \sigma_{a_i}\} = A_i$. Then he observes the events $E_i$ are mutually exclusive and that $\mathbb{P}(E_i)$ is relevant to our problem...

There are probably a lot of olympiad combinatorics problems that can be solved this way. Err... you were asking for number theory, but you will find both in Spencer and Alon's book.

Have you read The Probabilistic Method by Joel Spencer and Noga Alon?

Although originally developed by Erdos, here's an example of the probabilistic method taken from combinatoricist Po-Shen Loh:

$A_1, \dots, A_s \subseteq \{ 1, 2, \dots, M \}$ such that $A_i \not \subset A_j$ and let $a_i = |A_i|$. Show that $$ \sum_{i=1}^s \frac{1}{\binom{M}{a_i}} \leq 1$$ The hint is to consider a random permutation $\sigma = (\sigma_1, \dots, \sigma_M)$. Loh defines the event $E_i$ when $\{ \sigma_1, \dots, \sigma_{a_i}\} = A_i$. Then he observes the events $E_i$ are mutually exclusive and that $\mathbb{P}(E_i)$ is relevant to our problem...

There are probably a lot of olympiad combinatorics problems that can be solved this way. Err... you were asking for number theory, but you will find both in Spencer and Alon's book.

Have you read The Probabilistic Method by Joel Spencer and Noga Alon?

Although originally developed by Erdos, here's an example of the probabilistic method taken from combinatoricist Po-Shen Loh:

$A_1, \dots, A_s \subseteq \{ 1, 2, \dots, M \}$ such that $A_i \not \subset A_j$ and let $a_i = |A_i|$. Show that $$ \sum_{i=1}^s \frac{1}{\binom{M}{a_i}} \leq 1$$ The hint is to consider a random permutation $\sigma = (\sigma_1, \dots, \sigma_M)$. Loh defines the event $E_i$ when $\{ \sigma_1, \dots, \sigma_{a_i}\} = A_i$. Then he observes the events $E_i$ are mutually exclusive and that $\mathbb{P}(E_i)$ is relevant to our problem...

There are probably a lot of olympiad combinatorics problems that can be solved this way. Err... you were asking for number theory, but you will find both in Spencer and Alon's book.

Post Made Community Wiki
Source Link
john mangual
john mangual
  • 22.8k
  • 4
  • 63
  • 172

Have you read The Probabilistic Method by Joel Spencer and Noga Alon?

Although originally developed by Erdos, here's an example of the probabilistic method taken from combinatoricist Po-Shen Loh:

$A_1, \dots, A_s \subseteq \{ 1, 2, \dots, M \}$ such that $A_i \not \subset A_j$ and let $a_i = |A_i|$. Show that $$ \sum_{i=1}^s \frac{1}{\binom{M}{a_i}} \leq 1$$ The hint is to consider a random permutation $\sigma = (\sigma_1, \dots, \sigma_M)$. Loh defines the event $E_i$ when $\{ \sigma_1, \dots, \sigma_{a_i}\} = A_i$. Then he observes the events $E_i$ are mutually exclusive and that $\mathbb{P}(E_i)$ is relevant to our problem...

There are probably a lot of olympiad combinatorics problems that can be solved this way. Err... you were asking for number theory, but you will find both in Spencer and Alon's book.