Consider the following system of inequalities: { <mtable columnalign="left left" row

Summer Bradford

Summer Bradford

Answered question

2022-06-05

Consider the following system of inequalities:
{ x a b + x a c + x a d + x a b c + x a b d + x a c d + x a b c d 4 + x b c + x b d + x c d + x b c d x a b + x b c + x b d + x a b c + x a b d + x b c d + x a b c d 4 + x a c + x c d + x a d + x a c d x a c + x b c + x c d + x a b c + x a c d + x b c d + x a b c d 4 + x a b + x a d + x b d + x a b d x a d + x b d + x c d + x a b d + x a c d + x b c d + x a b c d 4 + x a b + x a c + x b c + x a b c
where each x { 0 , 1 }. Does this system of inequalities have a solution?

Answer & Explanation

Savanah Hernandez

Savanah Hernandez

Beginner2022-06-06Added 16 answers

If you transfer all the variables on the left side of each inequality, you get four inequalities of the form
c i a b x a b + c i a c x a c + c i a d x a d + c i b c x b c + c i b d x b d + c i c d x c d + c i a b c x a b c + c i a b d x a b d + c i a c d x a c d + c i b c d x b c d + c i a b c d x a b c d 4   ,
where the coefficients   c i w x , c i w x y , c i w x y z   are as listed in the following table
i x a b x a c x a d x b c x b d x c d x a b c x a b d x a c d x b c d x a b c d 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 sum 0 0 0 0 0 0 2 2 2 2 4
Summing all the inequalities tells you that they can only be satisfied if
2 x a b c + 2 x a b d + 2 x a c d + 2 x b c d + 4 x a b c d 16   .
But this is impossible if the variables are required to have values 0 or 1 because the value of the expression on the right can be at most 12.
Winigefx

Winigefx

Beginner2022-06-07Added 4 answers

You should add all inequalities and exclude all the terms that repeat on both sides. The result is:
2 x b c d + 2 x a c d + 2 x a b d + 4 x a b c d + 2 x a b c 16
But if all the x's are 0 or 1 left-hand side is not greater than 12.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?