DeletedUser27525
"How many blueprints do I actually need to collect to build a great building, without spending diamonds?"
The answer, as we all know, is not 9! In fact, you have to be really really lucky to get no duplicates, since the probability is
9/9 * 8/9 * 7/9 * 6/9 * ... * 1/9 = 0.0937%.
No swapping
As a starter let's simplify things a little bit by ignoring the swapping feature. This reduces the problem to what's commonly known as the "coupon collector's problem" in probability theory. (Look up Wikipedia for mathematical details.) The expected number of blueprints one needs to collect is:
9*(1 + 1/2 + 1/3 + ... + 1/9) = 25.46
And below I've run a simulation to show graphically how the expected number converges to that value.
With swapping
Now for the real question that allows swapping (either two blueprints with two copies or one blueprint with three copies), the simulation looks as follows, where the value is converging to roughly 16.5. Note that:
In conclusion, you need to collect, on average, slightly less than twice the number of required blueprints for each great building. With the swapping feature the devs have kindly reduced our efforts by about 1/3.
Next, I shall address another highly relevant question:
"I have 8 unique blueprints. How many more do I need?"
Again, let's analyze the cases of no swapping and swapping separately.
No swapping
The answer is trivial from probability theory: for a random variable with equal probability of p the expected number of trials until success is 1/p. In our case, p=1/9, so the expected number is 9.
With swapping
From the simulation below, the expected number converges to about 4.8. That's a huge reduction compared to no swapping!
"And what about N unique blueprints?"
My appended MATLAB code can be easily modified to produce the following results, in case anyone's interested. Mind you, these numbers are just expected values; there is no guarantee that you will ever collect all 9 blueprints!
Good luck!
N_sim=5000; % total number of simulations
N=zeros(1,N_sim); % no. of blueprints collected for each simulation
EX=N; % expectation E(X)
for i=1:N_sim
plot(EX)
xlabel('Number of simulations')
ylabel('Expected number of blueprints collected')
The answer, as we all know, is not 9! In fact, you have to be really really lucky to get no duplicates, since the probability is
9/9 * 8/9 * 7/9 * 6/9 * ... * 1/9 = 0.0937%.
No swapping
As a starter let's simplify things a little bit by ignoring the swapping feature. This reduces the problem to what's commonly known as the "coupon collector's problem" in probability theory. (Look up Wikipedia for mathematical details.) The expected number of blueprints one needs to collect is:
9*(1 + 1/2 + 1/3 + ... + 1/9) = 25.46
And below I've run a simulation to show graphically how the expected number converges to that value.
With swapping
Now for the real question that allows swapping (either two blueprints with two copies or one blueprint with three copies), the simulation looks as follows, where the value is converging to roughly 16.5. Note that:
- Duplicates are swapped whenever it is possible to do so.
- A different copy is obtained from swapping.
In conclusion, you need to collect, on average, slightly less than twice the number of required blueprints for each great building. With the swapping feature the devs have kindly reduced our efforts by about 1/3.
Next, I shall address another highly relevant question:
"I have 8 unique blueprints. How many more do I need?"
Again, let's analyze the cases of no swapping and swapping separately.
No swapping
The answer is trivial from probability theory: for a random variable with equal probability of p the expected number of trials until success is 1/p. In our case, p=1/9, so the expected number is 9.
With swapping
From the simulation below, the expected number converges to about 4.8. That's a huge reduction compared to no swapping!
"And what about N unique blueprints?"
My appended MATLAB code can be easily modified to produce the following results, in case anyone's interested. Mind you, these numbers are just expected values; there is no guarantee that you will ever collect all 9 blueprints!
Good luck!
| Number of unique blueprints already collected | Additional blueprints needed to build a great building |
|---|---|
| 0 | 16.5 |
| 1 | 15.5 |
| 2 | 14.5 |
| 3 | 13.3 |
| 4 | 12.1 |
| 5 | 10.8 |
| 6 | 9.2 |
| 7 | 7.3 |
| 8 | 4.8 |
N_sim=5000; % total number of simulations
N=zeros(1,N_sim); % no. of blueprints collected for each simulation
EX=N; % expectation E(X)
for i=1:N_sim
x=zeros(1,9); % initialize blueprint count
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% to begin with 8 unique blueprints,
% comment the line above and uncomment the line below
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%x=[0 ones(1,8)];
trial=0; % counter for copies of blueprints
while any(x==0) % keep trying until all blueprints are collected
N(i)=trial;
EX(i)=sum(N(1:i))/i; % running average
end%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% to begin with 8 unique blueprints,
% comment the line above and uncomment the line below
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%x=[0 ones(1,8)];
trial=0; % counter for copies of blueprints
while any(x==0) % keep trying until all blueprints are collected
num=randi([1 9]);
x(num) = x(num)+1;
dup = find(x==2); % duplicate case 1: 2 copies each ...
if size(dup,2)==2 % ... of 2 blueprints
dup = find(x==3); % duplicate case 2: 3 copies of 1 blueprint
if size(dup,2)==1
trial = trial + 1; % swapping is not counted as a trial
endx(num) = x(num)+1;
dup = find(x==2); % duplicate case 1: 2 copies each ...
if size(dup,2)==2 % ... of 2 blueprints
num=datasample( find(x~=2), 1 ); % swap for a different copy
x(num) = x(num)+1; % add new copy
x(dup) = x(dup)-1; % remove swapped copies
end x(num) = x(num)+1; % add new copy
x(dup) = x(dup)-1; % remove swapped copies
dup = find(x==3); % duplicate case 2: 3 copies of 1 blueprint
if size(dup,2)==1
num=datasample( find(x~=3), 1 );
x(num) = x(num)+1;
x(dup) = x(dup)-2; % remove 2 swapped copies
end x(num) = x(num)+1;
x(dup) = x(dup)-2; % remove 2 swapped copies
trial = trial + 1; % swapping is not counted as a trial
N(i)=trial;
EX(i)=sum(N(1:i))/i; % running average
plot(EX)
xlabel('Number of simulations')
ylabel('Expected number of blueprints collected')
Last edited by a moderator:
