User Tools

Site Tools


public:calculating_the_size_of_a_set_by_observing_the_proportionality_change_of_its_disjoint_subsets

This is an old revision of the document!


Calculating the size of a set by observing the proportionality change of its disjoint subsets

Problem statement

Set $A$ consists of disjoint subsets $a_1, a_2, ..., a_n$. Although we do not know the cardinality of set $A$ (denoted by $|A|$) and the cardinality of each of the subset, we do know the proportion of each subset in terms of set $A$, that is we know $\frac{|a_1|}{|A|}, \frac{|a_2|}{|A|}, ... \frac{|a_n|}{|A|}$. We are allowed to add elements into subsets of $A$, and observe the changes in proportionality of the subsets. What is the cardinality of set $A$ before elements were added to its subsets?

Solution

This problem can be solved by modelling the process of adding $n$ elements to subset $a_1$. We denote the proportionality of $a_1$ as $\alpha_1$, that is $\alpha_1 = \frac{|a_1|}{|A|}$, and the change in proportionality of $a_1$ using $\delta_{a_1}$

We begin by writing down the process that leads to the proportionality change:

$$ \frac{|a_1| + n }{|A| + n} - \frac{|a_1|}{|A|} = \delta_{a_1} $$

By multiplying the equation with the denominators in the right hand side, we obtain:

$$ (|a_1| + n )|A| - |a_1|(|A| + n) = \delta_{a_1}(|A| + n)(|A|)$$

By expanding the brackets, we obtain:

$$ |a_1||A| + n|A| - |a_1||A| - |a_1|n = \delta_{a_1}|A|^2 + \delta_{a_1}n|A| $$

By simplifying and rearranging the above equation, we obtain:
$$ |A|^2\delta_{a_1} + |A|(\delta_{a_1}n - n) + |a_1|n= 0$$

The above equation has two unknowns – $|A|$ and $|a_1|$. We can remove the unknown $|a_1|$ by substituting in $|a_1| = \alpha_1|A|$. By doing so, we obtain:

$$ |A|^2\delta_{a_1} + |A|(\delta_{a_1}n - n) + \alpha_1|A|n = 0 $$

By simplifying the above equation, we obtain:
$$ |A|^2\delta_{a_1} + |A|n(\delta_{a_1} - 1 + \alpha_1)= 0 $$

By dividing the above equation by $|A|$ and rearrangement, we obtain:
$$ |A| = \frac{-n(\delta_{a_1} - 1 + \alpha_1)}{\delta_{a_1}} $$

public/calculating_the_size_of_a_set_by_observing_the_proportionality_change_of_its_disjoint_subsets.1555410138.txt.gz · Last modified: 2019/04/16 10:22 by fangfufu