1
$\begingroup$

It begins with a simple question: "Can you write the numbers 1 through 5 in the boxes below in a way that respects the inequalities shown?"
__ $\lt$ __ $\lt$ __ $\gt$ __ $\lt$ __
This is so easy and can be solved in more than one way. For example, {1, 2, 5, 4, 3} in ordered way.

The question that I THINK I have solved it was: "Prove that problems like these can always be solved, that is, given N boxes with pre-set inequalities between them, there is always at least one way to arrange the numbers 1 through N respecting those inequalities".

My attempt:
Suppose that we have N boxes. The number of inequalities between them would be (N-1). For clarification, I will put N as 6 so that I can show what I meant exactly. So we have 6 numbers (From 1 to 6) and we have five inequality symbols.
We choose any two numbers from the set randomly. The symbol between them may be $\lt$ or $\gt$ (two possibilities), Then put the third number and we have the same possibility for the symbol between it and the second number... We do the same until we get to the last number which has no symbol after it. So to calculate the different ways that inequalities can be set in regarding to the chosen number in every box, we get $2^5$ which definitely covers all the cases of writing $\lt$ or $\gt$ five times = $2^5$.
I wrote much cause I wanted to make sure that you understand my "bad" English..

$\endgroup$
  • $\begingroup$ But as you pointed out, your example could be solved in multiple ways, yet your proposed proof implies that there is exactly one unique solution for each such problem. $\endgroup$ – Gabriel Burns Oct 26 '16 at 18:36
  • $\begingroup$ @Gabriel Burns My example does prove that "problems like these can always be solved" isn't it? I would be grateful if you have a better proof (I'm sure that there is a better one). $\endgroup$ – Ahmed Amir Oct 26 '16 at 18:40
  • 1
    $\begingroup$ You might be interested in google-ing the phrase "linear extensions of posets" $\endgroup$ – Nate Oct 26 '16 at 19:33
  • $\begingroup$ @Nate I googled it.. It would be useful if you have a specific article or a video about a part of "linear extensions of posets" which you think is related to the problem. $\endgroup$ – Ahmed Amir Oct 29 '16 at 8:00
1
$\begingroup$

The issue with your proof is that it essentially assumes its result. You're basically claiming that each ordering of "$\lt$" and "$\gt$" has a solution, because you can always pick numbers from the set that have that order, but that's exactly what "has a solution" means, so your argument is circular.

A better proof would be to simply construct a general solution, like so:

Each arrangement of "$\lt$" and "$\gt$" can be broken down as follows:

Max positions - either "$\_\_\gt$", "$\lt\_\_$" or "$\lt\_\_\gt$"

Min positions - either "$\_\_\lt$", "$\gt\_\_$" or "$\gt\_\_\lt$"

Chain positions - either "$\gt\_\_\gt$" or "$\lt\_\_\lt$"

To form a solution, first fill the max and min positions with the largest and smallest numbers of the set, respectively. Note that if you have, say, two max positions, it doesn't matter which one has the highest value and which has the second highest. Next, fill in the chain positions with sequential numbers from the set in the required order, moving from left to right, and starting at the top of the (remaining) set for "$\gt\_\_\gt$" chains and the bottom for "$\lt\_\_\lt$" chains. Since this process is always possible, and satisfies an arbitrary problem of this type, all such problems have a solution.$\blacksquare$

Note: the above process does not necessarily generate all possible solutions for a given problem (in fact it usually won't), but it will always produce at least one solution, which is all that is required for the proof.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I tried it in more than one problem and it worked. I quite understand why it should always work.. Thank you! $\endgroup$ – Ahmed Amir Oct 26 '16 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.