17
$\begingroup$

My daughter has always been very picky when it came to food. Initially, I thought she made random choices, but after observing this for a while, I found a pattern in her preferences. Let me explain.

Say there are n different candies in a box.

  1. If I give her two options, A and B, which are subsets of the candies, she always prefers one of them and her preference never changes.
  2. Moreover, if she prefers A to B and B to C, then I know that she prefers A to C.
  3. In addition, if B has everything A does, then she always prefers B.
  4. And finally, removing the same candy from A and B doesn’t change her preference.

Based on these observations, I wondered if she had a value (a positive real number) assigned to each of the n candies so that the value of an option is just what you would expect: the sum of values of all the candies in that option. But try as I might, I couldn’t find any set of values that matched her preferences. Maybe I just haven’t tried hard enough. So here I am, asking for your help.

  1. Can I always find a set of values that matches her preferences?
  2. If not, what’s the smallest value of n for which it’s possible that her preferences are such that I am doomed to fail?
Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What do you mean by ‘find a set of values that match her preferences’ precisely? Reading this, the most natural way to assess her preference is by which set she picks. Do you mean you want values for each piece of candy? $\endgroup$
    – Theguyabovemeislying
    Commented 23 hours ago
  • 1
    $\begingroup$ @Theguyabovemeislying. Yes, assigning a value to each candy gives a value for any subset of candies as I described in the OP. You can now compare any two subsets by comparing their values. The “set of (n) values” matches with her preference if the comparing the values gives the same preference as my daughter’s. $\endgroup$
    – Pranay
    Commented 23 hours ago
  • $\begingroup$ @Theguyabovemeislying the guy below me is telling the truth; if you try to comment below me you just made a contradiction $\endgroup$
    – Lucenaposition
    Commented 7 hours ago
  • 1
    $\begingroup$ The people above and below me aren't necessarily guys.... $\endgroup$
    – Greg Martin
    Commented 7 hours ago

2 Answers 2

Reset to default
3
$\begingroup$
  1. Can I always find a set of values that match her preferences?

No, this is not always possible. Assume that n = 4, candies are labeled ABCD , and her preferences are given by D < C < B < CD < BD < BC < A < AD < AC < AB < BCD < ACD < ABD < ABC < ABCD This satisfies the criteria. But if we assume that the candies can be assigned numbers a, b, c and d, then we have 3(b+c+d) > (a+b) + (a+c) + (a+d) = (b+c+d) + 3a > (b+c+d) + (b+c) + (b+d) + (c+d) = 3 (b+c+d) which is a contradiction.

If not, what’s the smallest value of n for which I am doomed to fail?

n = 4 is the smallest such value. With n = 3, once we have C < B < A, there is only two possibilities for the rest of the preferences - either C < B < BC < A < AC < AB < ABC or C < B < A < BC < AC < AB < ABC. Both of these can be achieved by assigning numbers, for instance (a,b,c) = (4,2,1) and (a,b,c) = (4,3,2) respectively.

Improve this answer
$\endgroup$
4
  • 5
    $\begingroup$ I don't think this satisfies 4. (since you have BC<A but also AD<BCD) $\endgroup$
    – Tim Seifert
    Commented 15 hours ago
  • $\begingroup$ True :-(. It also looked too easy. $\endgroup$
    – Nis Jørgensen
    Commented 15 hours ago
  • $\begingroup$ As @TimSeifert already said, this doesn’t satisfy the fourth condition. $\endgroup$
    – Pranay
    Commented 14 hours ago
  • $\begingroup$ But you are right that n=3 can be done so +1. $\endgroup$
    – Pranay
    Commented 14 hours ago
0
$\begingroup$
  1. Can I always find a set of values that match her preferences?

Yes. For any integer n greater than or equal to 0, it is always possible to find a set of n numbers where the sum of the numbers in any subset is unique to that subset. An example of this type of set is {2^0, 2^1, ... , 2^(n-1)}. In this set, there are 2^n possible unique subsets, and the sum of the numbers in each one is one of the integers between 0 and 2^n - 1. Thus, no subset has the same sum as any other different subset.

Given a set of candies, any total ordering of all possible subsets can be represented in this way, assuming the values are assigned correctly. The daughter is guaranteed to not have any two candies that she likes the same amount, or else it would be possible to have two subsets with no clear preference, simply by substituting one candy for the candy she likes the same amount. Thus, each candy must be liked a different amount, and it is therefore possible to arrange the candies in order of preference, and assign each one a value in the set given, in ascending order.

  1. If not, what’s the smallest value of n for which I am doomed to fail?

There is no value of n for which this is not possible.

Improve this answer
New contributor
Bitey is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
9
  • 2
    $\begingroup$ You haven’t addressed the crucial question: why does realising distinct values for all subsets ensure that all possible preferences satisfying the four given conditions can be generated this way? All it ensures is that no two subsets have the same value, so you get a valid preference satisfying all the four conditions. $\endgroup$
    – Pranay
    Commented 23 hours ago
  • 1
    $\begingroup$ I think I might be misunderstanding, sorry. In the example set I gave, I stated that each subset has a unique sum. Doesn't that mean that a total order exists? Do you want me to add text to explain that? $\endgroup$
    – Bitey
    Commented 22 hours ago
  • 1
    $\begingroup$ I appreciate you trying to help! Hopefully someone else will come in and give a good answer. $\endgroup$
    – Bitey
    Commented 22 hours ago
  • 4
    $\begingroup$ As an example where this approach fails, consider a set of candies x,y,z such that x<y<z. This answer has successfully found a way to ensure that (x+y) != z, but only handles the case where (x+y)<z. Whereas, possibly (x+y)>z, which could be resolved with x=5,y=6,z=7, but would not be resolved by x=1,y=2,z=4. $\endgroup$
    – Brian
    Commented 21 hours ago
  • 2
    $\begingroup$ Thanks for explaining, I definitely wasn't thinking about that kind of case. $\endgroup$
    – Bitey
    Commented 21 hours ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.