Uniform cost variable member constraint problem

Question

I have this algorithmic problem that I'm trying to solve in code at the moment which requires costing uniformly across a number of members who have variable resource. I'll illustrate with an example:

(A)my wants to wants to buy an appliance for a house she's sharing with (B)en and (C)arlos. The appliance costs X money.

Amy has an amount of money (A) where A < X. So she wants to share the cost with Ben and Carlos, but only if they can afford to share uniformly.

If she shares with all of them, they each must be able to afford X/3. Otherwise, she must decide to either share only with Ben or Carlos, in some combination of two:

(A > X/2 AND B > X/2) OR (A > X/2 AND C > X/2) OR (B > X/2 AND C > X/2)

If none of these work out, she can get Ben or Carlos to pay for her, but only if they can each afford the whole cost.

(B > X) OR (C > X)

If none of these work out, tough luck!

Firstly, is there a general way to determine if a solution exists for any tuple of values (A,B,C,X), and to determine what that solution is? The solution should be in the form of a subset of Amy, Ben and Carlos.

Secondly, what if there are n tenants? (a1,a2....an,X)

I think this is a nonlinear optimization problem, but I could be wrong! I have CompSci degree-level maths knowledge.

Thank you in advance!

Answer 1

A friend of mine provided a O(n^2) pseudocode algorithm on twitter:

people = [100, 120, 130, 140... ]
x = 150
ratios = [p/x for p in people]

for n in range(1, len(ratios)):
   enough = 0
   for i in range(0, len(ratios)):
      if ratios[i] > (1/n):
           enough += 1
    if enough >= n: return True

return False