1
$\begingroup$

A mart has $10^7$ items in stock. It has collected billing data for $10^{10}$ customer transactions. Each individual bill can have at most $10$ distinct items on it. The owner of the mart wants to optimise the company inventory and wants a list of the items that appear in at least $2$ percent of the billed transactions. What is the most precise upper bound that can be computed for the number of such items, given the data?

So, two percent of the total bills amounts to $2*10^8$ bills. And the maximum number of times the printing of any item can occur on ALL bills is $10^{10}*10 = 10^{11}$.

The solution shows $10^{11}/(2*10^8) = 500$ but I do not understand this step.

$\endgroup$

1 Answer 1

1
$\begingroup$

Assume that $N$ items appear in $2\%$ or more of all $10^{10}$ transactions. These items use $L$ item-lines in the collection of all customer bills, whereby $$L\geq 2\cdot10^8\cdot N\ .$$ Since there are $10^{10}$ bills, and each of them can have at most $10$ item-lines, we have $L\leq 10\cdot10^{10}$, so that we obtain the condition $$2\cdot10^8\cdot N\leq L\leq 10\cdot10^{10}\ ,$$ or $N\leq500$.

$\endgroup$
1
  • $\begingroup$ This explains it nicely. Thank you! $\endgroup$
    – user733666
    Sep 30, 2020 at 13:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .