by **Guest** » Sun Jul 10, 2016 7:18 pm

In your example, you had item 100, which is heavily underpriced, so we should expect the group to be underpriced (everything else is slightly overpriced), but the question is how can we be 100% sure. The reason is as follows:

Let [tex]c_1, \ldots, c_{100}[/tex] be the change in prices of items 1 to 100 respectively.

Observe that [tex]c_i = (\text{new price of item } i)-(\text{old price of item } i)[/tex] which means:

[tex]c_1+c_2+\ldots+c_{100}=(\text{sum of new prices}) - (\text{sum of old prices}) = 0[/tex]

because the prices before and after the relabelling are the same (just rearranged).

Rearranging the above equation gives

[tex]c_{100} = -c_1-c_2-...-c_{99}[/tex]

furthermore we know that [tex]c_i>0[/tex] when [tex]i=1,...,99[/tex] because of the way we rearranged the labels (items 1,...,99 are overpriced, and item 100 is underpriced).

If a subset of the items has the same price before and after relabelling we have that the sum of the items' [tex]c_i[/tex] values must add up to 0. For example if items 1, 4, 9, had the same group price before and after relabelling, we would have to have

[tex]0 = (\text{sum of new prices of items 1, 4, 9}) - (\text{sum of old prices of items 1, 4, 9}) = c_1+c_4+c_9[/tex],

however, we know that [tex]c_1>0, c_4>0,[/tex] and [tex]c_9>0[/tex] (see above), so they can't add up to 0.

In fact any subset of items, that doesn't include item 100, will not have the same price after relabelling because the [tex]c_i[/tex] are all positive so cannot add up to 0. (Another way of looking at it as that a subset consisting solely of overpriced items will itself be overpriced.)

If the subset of items contains item 100, for example items 3, 5, 10, 33, 100, then the sum of the [tex]c_i[/tex] are

[tex]c_3+c_5+c_{10}+c_{33}+c_{100}[/tex]

By substituting the expression for [tex]c_{100}[/tex] we found earlier, we get that the sum equals

[tex]c_3+c_5+c_{10}+c_{33}+(-c_1-c_2-c_3-...-c_{99})[/tex]

Note that the terms outside the bracket will cancel with some of the terms inside the bracket leaving

[tex]-c_1-c_2-c_4-c_6-c_7-c_8-c_9-c_{11}-c_{12}-...-c_{99}[/tex]

i.e. every term is there except [tex]-c_3, -c_5, -c_{10}[/tex], and [tex]-c_{33}[/tex]

The sum is obviously less than 0, because [tex]c_i[/tex] is positive for all [tex]i<100[/tex]. Which proves the subset is underpriced. The same argument holds for any subset containing item 100.

(Another way of looking at it as that any subset containing item 100 will be underpriced because the only way we could avoid this is if we had lots of overpriced items counterbalancing item 100's massive underpricing, but even if our subset contains every overpriced item we only manage to break even, and so if any overpriced items are missing from the subset the whole thing will be underpriced.)

Hope this helped,

R. Baber.