Chocolate store

[Guest]

At the window of a chocolate store there are 100 different types of chocolates, each having a label with its price, all of them different from each other.
Is it possible to rearrange all the labels so that the sum of the prices of any group of 1 to 99 labels is different from the sum of the original prices?
If your answer is positive, please give also an example; otherwise, justify it.

[Guest]

The answer is always yes.

Arrange your items in order of price. Relabel every item, except the most expensive item, with a label that is the next most expensive. Label the most expensive item with the label that is the least expensive. Now any group not containing the most expensive item will be overpriced, and any group containing the most expensive item will be underpriced (except in the case where the group contains all 100 items).

For example let us suppose that there are only 4 items, A,B,C,D, priced:
A 1, B 3, C 5, D 6
We relabel as follows
A 3, B 5, C 6, D 1
A, B, C are overpriced by 2, 2, 1 respectively, and D is underpriced by 5.
Without including D in the group the group will be overpriced.
Including D in the group will leave the group underpriced, unless the group includes every overpriced item, making the group A,B,C,D.

Hope this helped,

R. Baber.

[Guest]

Yes but what about the subgroups that will include D? Say, for example, all the subgroups of 1, 2 or 3 elements that will have D into them?
The condition for the different sum must be met for every subgroup! We can't select which elements will be included!

I want to thank you, however, for your reply!

[Guest]

Sorry for not being clear enough, but what I meant was the solution I gave would work for all subsets containing D and all subsets not containing D.

Subsets not containing D:
A is overpriced by 2
B is overpriced by 2
C is overpriced by 1
A, B is overpriced by 4
A, C is overpriced by 3
B, C is overpriced by 3
A, B, C is overpriced by 5

Subsets containing D:
D is underpriced by 5
A, D is underpriced by 3
B, D is underpriced by 3
C, D is underpriced by 4
A, B, D is underpriced by 1
A, C, D is underpriced by 2
B, C, D is underpriced by 2
A, B, C, D is equally priced.

Every subset not containing D is overpriced, because every item in the set is overpriced.
Every proper subset containing D is underpriced, because D is massively underpriced.

The only way to make a subset containing D not underpriced is by adding lots and lots of overpriced items to counterbalance D, but even if we add every single possible overpriced item we just manage to break even, which means if we exclude just one overpriced item the whole thing will be underpriced.

Hope this helped,

R. Baber.

[Guest]

It really helped!
Is there any way to generalize this for the subsets of 1 and up to 99 elements and with "random" prices?

[Guest]

Yes, it generalizes in the way I described in my original post (give the cheapest label to the most expensive item, and for every other item simply label it with the price of the next most expensive item). The A, B, C, D thing was just a small concrete example to demonstrate how the relabelling works.

R. Baber.

[Guest]

Let's say that the chocolates originally had the prices p1, p2, ... , p100 (arranged from smallest to largest) and then we shift the labels one position forward (p2, p3, p4,...,p1) so that the most expensive chocolate has the label of the cheapest price in front of it (p1).
If we make a group of, say, 5 labels (p4, p6, p11, p34, p1), how do we know 100% that the sum of these 5 will be different from the sum of the original 5 prices (p3, p5, p10, p33, p100)?

Sorry to insist so much, but I am not too much into math

Thank you so much!!!

[Guest]

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.

[Guest]

Another argument I thought of is the following:

A quick definition: A counterexample, for our purposes, is a subset which has the same price before and after relabelling.

(1) All counterexamples must contain item 100.
If one existed not containing item 100 then it would consist solely of overpriced items yet not be overpriced itself, which is impossible.

(2) If there is a counterexample containing item 100, then there must be a counterexample not containing item 100 (which would contradict (1), therefore there are no counterexamples).
The proof of (2) is as follows:
Let A be the set of All items, let C be the set of all items in our Counterexample containing item 100, let N be the set of the items Not in C.
So old price of A = new price of A (because all the labels are present just in a different order)
also old price of C = new price of C (because it is a counterexample, so by definition its price remains the same)
Which means
old price of N
= old price of A - old price of C (by the fact that N is A with C removed)
= new price of A - new price of C (by the fact that both A and C don't change in price after relabelling)
= new price of N (by the fact that N is A with C removed)
So N also has the same price before and after relabelling therefore is also a counterexample (and does not contain item 100).

R. Baber.

[Guest]

R. Baber you are a genius!!!!! Congrats!!