A graph is constructed iteratively according to the following algorithm. The graph starts as a single vertex. With probability p, the graph stops here. Otherwise, 3 new
vertices are constructed and joined to this vertex. If we have a graph with more than one vertex, for each vertex created at the previous stage, 3 new vertices are construed and joined to it with probability 1−p. We repeat this
process until no new vertices are added. When the expected number of vertices in this graph is 100, the value
of p can be expressed as a/b
where
a and
b are coprime
positive integers. What is the value of a+b
To find the value of p when the expected number of vertices in the graph is 100, we can start by analyzing the first stage of the algorithm.
At the first stage, there is only 1 vertex. With probability p, the graph stops here, so the expected number of vertices is 1 * p = p.
If the graph doesn't stop at the first stage, 3 new vertices are constructed and joined to the initial vertex. This means that the expected number of vertices after the second stage is 1 + 3 * (1 - p).
We can continue this analysis for subsequent stages. At each stage, the expected number of vertices is calculated as the sum of the vertices from the previous stage multiplied by the probability of not stopping (1 - p). So the expected number of vertices at the third stage is (1 + 3 * (1 - p)) * (1 - p).
We repeat this process until no new vertices are added. At the nth stage, the expected number of vertices can be expressed as:
E(n) = (1 + 3 * (1 - p)) * (1 - p) * (1 - p) * ... * (1 - p) (n times)
Since the graph stops when no new vertices are added, the expected number of vertices when the graph stops is the summation of all expected values at each stage.
100 = E(1) + E(2) + E(3) + ...
To simplify this equation, we can use the formula for the sum of an infinite geometric series:
100 = E(1) / (1 - r) where r = (1 - p)
Substituting E(1) from earlier:
100 = (p) / (1 - (1 - p))
Simplifying:
100 = p / p
This equation holds for any value of p. Since we are looking for a specific value of p, we need additional information. It seems there might be a mistake in the problem statement or missing information required to determine the value of p.
Without further information, we cannot determine the value of a+b.
To find the value of p, we need to determine the expected number of vertices in the graph and set it equal to 100. Let's break down the problem step by step.
At the first stage, the graph starts with a single vertex. There are two possibilities:
1. With probability p, the graph stops here, and we have one vertex.
2. With probability 1-p, three new vertices are constructed and joined to this vertex. In this case, the graph will have 1 + 3 = 4 vertices.
So, at the end of the first stage, the expected number of vertices is given by E₁ = p * 1 + (1-p) * 4.
At each subsequent stage where the graph has more than one vertex, for each vertex created in the previous stage:
1. With probability 1-p, three new vertices are constructed and joined to it.
2. With probability p, the graph stops growing from that vertex.
Let's denote the expected number of vertices at the i-th stage as Eᵢ. For i = 1, E₁ is already calculated.
For i > 1, we can express Eᵢ in terms of Eᵢ₋₁:
Eᵢ = (1-p) * 3 * Eᵢ₋₁ + p * Eᵢ₋₁
Essentially, at each stage, we have a probability of (1-p) for the graph to grow by a factor of 3, and a probability of p for it to stop growing from that vertex. Therefore, the expected number of vertices increases by a factor of 3 * (1-p) and stays the same with a probability of p.
To find the value of p, we need to solve the equation E = E₁ = 100, where E is the expected number of vertices.
Let's start by finding E₂. We substitute E₁ into the equation for Eᵢ:
E₂ = (1-p) * 3 * E₁ + p * E₁
Similarly, we find E₃, E₄, and so on, until we find E where E = E₁ = E₂ = E₃ = ...
Now, we have an equation in terms of p:
E = (1-p) * 3 * E + p * E
We can solve this equation for E:
E = 3 * (1 - p) * E + p * E
E = 3E - 3pE + pE
E = 3E - 2pE
2pE = 2E
p = 1/2
Therefore, the value of p is 1/2.
The value of a + b = 1 + 2 = 3.