4

Sorry if I'm being a bit vague. Feel free to ask if you need more info:

I have 57 statements about a number m. These statements are obviously contradictory - for example, statement 7 and 35 are not compatible, as well as statements 6, 14 and 22 (when taken together). I want to prove (by hand) that I will have to remove at least 25 statements for the system to stop being contradictory (this is true - the whole problem is of number-theoretical nature, and I have been able to show by computer that it is correct). I was able to write a program that outputs all pairs of contradictory statements (of which there are 78, but not disjoint at all. For example, statement 57 is in 14 such pairs). Also, I have all triples of contradictory statements. I can prove by hand that a certain set of statements is contradictory, as well as that it isn't (by providing a number m that fulfills all conditions).

My question: What strategy should I follow to prove that there does not exist a subset of 33 statements that is not contradictory? I could find 25 disjoint pairs of contradictory statements, but these don't exist. I've found 17. Thanks in advance. I'll try and answer any question that can help!

Georgi Kocharyan
  • 451

2 Answers2

0

About all you can do is exhibit a value and a list of $33$ statements that are true for that value. You can just do a search. From the statements you might decide that if there is such a value it is likely to be in the range $[-100,100]$, say. You could make a spreadsheet with values down the first column and each statement represented by a column. Put a $1$ in the cell if the statement is true for that value. Mixed addressing (like $\$A2$ to keep A fixed but have the $2$ relative) will make copying across and down easier. Then sum up all the rows and look for one with a number at least $33$. You could also program this and use a larger range.

Ross Millikan
  • 374,822
  • I want to prove, by hand, that there does not exist such a number. I have already tested this with a program, and I know that this is actually the case. – Georgi Kocharyan Aug 06 '19 at 14:50
0

If you define a graph with a node for each statement and an edge for each pair of contradictory statements, your problem is to find a maximum independent set.

RobPratt
  • 45,619
  • 1
    There is a problem with this approach. There could be 3 statements A, B and C. Any two of them can hold simultaneously, but still all three can't. (However not sure it's a problem after clarification about nature of statements.) – lesnik Aug 06 '19 at 14:41
  • 1
    But there also exist triples of statements, which are contradictory only when taken together. – Georgi Kocharyan Aug 06 '19 at 14:48
  • @Iesnik this is what I mean by a "triple" of contradictory statements, this happens fairly often, actually. My program found over a hundred such triples. – Georgi Kocharyan Aug 06 '19 at 14:51
  • In that case, you are looking for maximum independent set in a hypergraph. – RobPratt Aug 06 '19 at 15:00
  • @RobPratt Consider $a \vee b$, $a \vee \neg b$, $\neg a \vee b$, and $\neg a \vee \neg b$. They are all pairwise satisfiable, and also satisfiable if taken three at a time. To build the hypergraph, you'd have to solve the actual problem first. – Fabio Somenzi Aug 06 '19 at 15:10
  • You can build the hypergraph dynamically, as long as you have a way to determine whether a given set of statements is feasible. Find a maximum independent set in the current hypergraph, add a new hyperedge if needed, and repeat. – RobPratt Aug 06 '19 at 16:03
  • @RobPratt By the time you've built the hypergraph, you already know which subsets are consistent and which are not. Hence, you have already solved the problem. – Fabio Somenzi Aug 06 '19 at 16:18
  • You need not check all subsets. By examining the maximum independent sets dynamically, the hope is that you generate only a small fraction of the hypergraph. A similar idea (subtour elimination) works very well for the traveling salesman problem, even though there are an exponential number of subtours. – RobPratt Aug 06 '19 at 16:27
  • You don't need to examine all subsets regarless. A superset of an inconsistent set is inconsistent. – Fabio Somenzi Aug 06 '19 at 16:32