7
$\begingroup$

The puzzle

Given a set of numbers $\{1,2,\ldots,n\}$ and an expression of inequalities, e.g., $ x_1 > x_2 < \cdots > x_n$. Prove that there always exists a solution such that $x_i \in \{1,2,\ldots,n\}$ and that each $x_i$ is distinct. Can you design an algorithm which always provides a correct solution in polynomial time?

I will not take credit for this problem. It was originally posed by Jim Tanton here.

In less "mathy" terms:

You are given a string of $>$ and $<$ symbols ($n$ of them in total). Insert the numbers from $1$ to $n+1$ between them, so that all the inequalities are true. Find a general solution that works for any string of symbols of any length, and doesn't take exponentially longer when the string of symbols is longer.

Example

You are given < > >. You must insert the numbers from $1$ to $4$ between the symbols so that all the inequalities are true:

$1<4>3>2$

$\endgroup$
  • $\begingroup$ This seems more like a math question than a puzzling question. That being said, this is way over my head and might be a great puzzle for the people that know what those symbols mean. $\endgroup$ – Deacon Aug 17 '15 at 20:00
  • $\begingroup$ @user12365 Maths questions can be on-topic if they're puzzles as opposed to problems, see here. I would say this is off-topic, but since its computery element makes it not my cup of tea, I'll hold off on voting until others have chimed in. $\endgroup$ – Rand al'Thor Aug 17 '15 at 20:04
  • $\begingroup$ Sorry about the symbols. Clarification: each of the $x_i$ is a number between $1$ and $n$. $\endgroup$ – Carl Löndahl Aug 17 '15 at 20:04
  • $\begingroup$ @user12365 I tried adding a less "mathy" explanation. See if that helps to understand it. $\endgroup$ – GentlePurpleRain Aug 17 '15 at 20:53
7
$\begingroup$

This algorithm is my intuition and I don't know if it's right so please prove me wrong.

First fill in all numbers in order from left to right. Then we look at each number from left to right and do this: If the sign next to it is < do nothing, if it's > take the right most number in your sequence, put it there and shift all other numbers to the right

$\endgroup$
  • $\begingroup$ Yes, this is an acceptable solution! Good job! $\endgroup$ – Carl Löndahl Aug 17 '15 at 20:16
  • $\begingroup$ An example might make this answer even better. $\endgroup$ – Rohcana Aug 17 '15 at 20:38
  • $\begingroup$ I take the liberty of providing an example: $\endgroup$ – Carl Löndahl Aug 17 '15 at 20:47
  • $\begingroup$ Start off with $1 < 2 < 3 < 4 < 5$. If the desired inequality is $x_1 > x_2 < x_3 < x_4 > x_5$, then we set $5$ since the inequality is reversed. Next inequality is not reversed so we obtain $5 > 1$. Next is not reversed, so we have $5 > 1 < 2$ and then next is reversed, so $5 > 1 < 2 < 4$. Finally, we have $5 > 1 < 2 < 4 > 3$. $\endgroup$ – Carl Löndahl Aug 17 '15 at 20:52
  • 3
    $\begingroup$ Maybe an easier explanation would be this strategy which yields the same result. Go from left to right and when it has a > put the largest number there you still have and when there is a < put the smallest number there $\endgroup$ – Ivo Beckers Aug 17 '15 at 21:23
6
$\begingroup$

First, construct a mountain range from the inequality symbols, where $<$ is an upslope and $>$ is a downslope. For example, given $$ x_1 < x_2>x_3>x_4>x_5<x_6<x_7>x_8 $$ you would make

$\qquad\qquad\qquad\qquad$
Next, place the numbers $1$ to $n$ on the vertices of this drawing, filling the levels in order from lowest to highest:

$\qquad\qquad\qquad\qquad$

Finally, read this off from left to right, getting the solution $5<8>6>2>1<3<7>4.$ When done smartly, this takes linear time.

$\endgroup$
1
$\begingroup$

Proof that it's possible:

Let's assume it's the case for all lengths smaller than $n$. Either 1 is at the beginning/end or in the middle. In both cases, it leads to a smaller solvable part or two parts, so it's doable.

How to do it:

Doesn't matter where you put your 1 as long as the spot doesn't have a greater sign next to it. Then do the same for 2, 3, ... Rinse and repeat.

$\endgroup$

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.