9
$\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$

Improve this question
$\endgroup$
4
  • $\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, 2015 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, 2015 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, 2015 at 20:04
  • $\begingroup$ @user12365 I tried adding a less "mathy" explanation. See if that helps to understand it. $\endgroup$
    – GentlePurpleRain
    Aug 17, 2015 at 20:53

3 Answers 3

Reset to default
8
$\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

Improve this answer
$\endgroup$
5
  • $\begingroup$ Yes, this is an acceptable solution! Good job! $\endgroup$
    – Carl Löndahl
    Aug 17, 2015 at 20:16
  • $\begingroup$ An example might make this answer even better. $\endgroup$
    – Rohcana
    Aug 17, 2015 at 20:38
  • 1
    $\begingroup$ I take the liberty of providing an example: $\endgroup$
    – Carl Löndahl
    Aug 17, 2015 at 20:47
  • 1
    $\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, 2015 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
    Aug 17, 2015 at 21:23
9
$\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.

Improve this answer
$\endgroup$
2
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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