Nice problem regarding arrows

Hi everyone! I recently came across this nice problem, and decided to share it here for others to enjoy. Feel free to post your thoughts and solutions!


When you write the string abcda \leftarrow bc \leftarrow d in a text editor (where \leftarrow denotes the left-arrow key of the keyboard), you get the string bdcabdca. Hence, we can insert arrows within string abcdabcd in such a way that we get the string bdca.bdca.

Now, consider two strings AA and BB. Suppose that you can insert arrows within string AA to obtain string B.B. Show that you can also insert arrows within string BB to obtain string A.A.

Just to clarify, you are allowed to enter multiple arrows before a character. For example, doing abcdab \leftarrow \leftarrow cd (which gives the string cdbacdba) is allowed. However, you cannot use right arrows.


Here's an example which shows this for the strings abcdabcd and bcdabcda:

As already shown above, we can insert arrows within abcdabcd to obtain bcdabcda. We shall show that we can insert arrows within bcdabcda to obtain abcd.abcd. This is simple; just do bcda.bcd \leftarrow \leftarrow \leftarrow a.


Also, just to be specific, we're working with strings of any length, not just length 44, and all characters of the strings are distinct (thanks Daniel).

Source: USA TSTST 2014


This is one of my favorite problems. I've given this to many of my friends (mostly people who qualified RMO but unfortunately failed INMO), and we've gotten many different solutions to this problem. I have a solution which finds a condition for the string {1,2,,n}\{1, 2, \cdots , n\} to be attainable from a permutation of {1,2,,n},\{1, 2, \cdots , n\}, and then shows that if this condition holds for a permutation, it must also hold for its inverse, completing the proof (I can post it if necessary). A friend of mine has another nicer solution using induction, I can also post that for him if anyone wants.

I'm looking forward to how the people here approach this really nice problem. Thanks for reading this. :)

Note by Sreejato Bhattacharya
5 years, 1 month ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

wlog take the initial string Sn S_n as composed of the integer i at each index i. For example, instead of 'abcd' in your example we would call it '1234'. Now, any string obtained from S consists of a permutation on (1, 2, ... n). Call this a1,a2,...an a_1, a_2, ... a_n. What strings can NOT be obtained? It is easy to see that the strings which cannot be obtained are precisely those for which we can find three indices i < j < k such that aj<ai<ak a_j < a_i < a_k . But in this case we can take ai,aj,ak a_i, a_j, a_k as i,j,ki, j, k in the operation to see that the inverse of the permutation also satisfies this condition. In other words, if a permutation cannot be obtained from SnS_n, then neither can its inverse. Therefore, if a permutation CAN be obtained then so can its inverse.

ww margera - 5 years, 1 month ago

Log in to reply

Yup, that's precisely my solution. Just filling out the details; here's the solution I wrote in the AoPS thread.


WLOG let string AA be 1,2,,n,1, 2, \cdots , n, so BB is a permutation of 1,2,,n.1, 2, \cdots , n. Let's characterize all permutations from which AA is reachable. Consider a permutation b1,b2,,bnb_1, b_2, \cdots , b_n of 1,2,,n1, 2, \cdots , n from which AA can be reached.

Define an increasing block starting from bib_i to be a subset of {b1,b2,,bn}\{b_1, b_2, \cdots , b_n\} of the form {bi,bi+1,,bi+j},\{b_i, b_{i+1}, \cdots , b_{i+j}\}, where bi+k>bi+k1b_{i+k} > b_{i+k-1} for all 1kj.1 \leq k \leq j. Also, define the associate of bib_i to be the largest bjb_j satisfying j<ij<i and bj<bi.b_j<b_i.

Note that to transform b1,b2,,bnb_1, b_2, \cdots , b_n into 1,2,,n,1, 2, \cdots , n, we must add arrows according to the following rules.

  • Start with b1.b_1. Let S1S_1 be the largest increasing block starting from b1.b_1. Let bjb_j be the last element of S1S_1. Add a suitable number of arrows to the left of bj+1b_{j+1} such that bj+1b_{j+1} gets placed just to the right of its associate.

  • Let bib_i be the element our cursor is currently on. Do the basically same thing with bib_i: let SiS_i be the largest increasing block starting from bi.b_i. Add arrows at the end of its last element so that the element after it gets placed right after its associate.

  • Keep doing this throughout the whole sequence.

(Just to clarify, the string b1,b2,,bnb_1, b_2, \cdots , b_n gets modified after each step accordingly.)

This is the only way we can transform {bi}i=1n\{b_i\}_{i=1}^{n} to {i}i=1n.\{i\}_{i=1}^{n}. To see why this is true, note that after arrows have been placed to the left of some bi,b_i, its position can't be changed later, so we must make sure that each element has been placed just to the right of the largest operated element smaller than it (operated in the sense that arrows have been placed to the right of it so its position can't be changed anymore).

Now, this algorithm fails precisely when there exists an ii such that the largest increasing block starting from bib_i contains an element bjb_j which is larger than at least one of the elements between bkb_k and bi1,b_{i-1}, where kk denotes the position where bjb_j gets placed after shifting the largest increasing block starting from bib_i to the left. If such a ii doesn't exist, the largest block starting from 11 increases in length every time a number is shifted towards the left. Eventually, this block has length n.n. This is when we have the string 1,2,,n.1, 2, \cdots , n. If such a ii exists, we have a number whose position can't be changed anymore larger than a number to the right of it whose position can't be changed either, so we can't reach 1,2,,n.1, 2, \cdots , n.

The existence of such an ii is equivalent to the existence of some positive x,y,zx, y, z satisfying bx+y<bx<bx+y+z.b_{x+y} < b_{x} < b_{x+y+z}. Let's call all permutations for which there exist such x,y,zx, y, z good.

Claim: If a permutation is good, so is its inverse. Proof: Let {σ(i)}i=1n\{\sigma (i)\}_{i=1}^{n} be a good permutation of {i}i=1n,\{i\}_{i=1}^{n}, and let {φ(i)}i=1n\{\varphi (i)\}_{i=1}^{n} be the inverse of σ,\sigma, so φ(σ(i))=i\varphi (\sigma (i))= i for all i.i. Now, there exist x,y,zx, y, z such that σ(x+y)<σ(x)<σ(x+y+z).\sigma(x+y) < \sigma (x) < \sigma (x+y+z). But, we also have that φ(σ(x+y+z))>φ(σ(x+y))>φ(σ(x)),\varphi (\sigma (x+y+z)) > \varphi (\sigma (x+y) ) > \varphi (\sigma (x)), so taking (x2,x2+y2,x2+y2+z2)=(σ(x+y),σ(x),σ(x+y+z))(x_2, x_2+y_2, x_2+y_2+z_2) = (\sigma (x+y) , \sigma (x), \sigma(x+y+z)) does the job. \blacksquare

Using the lemma, it follows that if {i}i=1n\{i\}_{i=1}^{n} can be reached from {bi}i=1n,\{b_i\}_{i=1}^{n}, {bi}i=1n\{b_i\}_{i=1}^{n} can be reached from {i}i=1n.\{i\}_{i=1}^{n}. This shows that if AA can be reached from B,B, BB can be reached from A,A, completing the proof. \blacksquare


I'm well aware that my proof above is a very badly phrased one; sorry if some parts of it are very vague / hard to understand. I'll be glad to add clarifications to certain unclear parts in my solution if someone asks.

There also exists a nice solution using induction which my friend found. I can post it here if necessary. I'm looking for other's solutions here too!

Sreejato Bhattacharya - 5 years, 1 month ago

Log in to reply

That is very interesting

Mezhona Gray - 5 years ago

Log in to reply

Let String = ab Now we can say that ab,ba (only two possible permutations using left arrows) both can be converted back to ab So we know this property holds true for n=2 Now take a string of length n­, A1A2A3A4A5....An where Ai stand for a character i - integer Lets suppose the property holds true for string of length n Now lets prove it for string of length n+1 String S= A1A2A3A4A5....AnA(n+1) Now lets suppose We obtain string k. String k will of of the form 2. k = AiAj....ApA(n+1)........AqAr

If the string is in the first form we can consider AnA(n+1) to be a single character and this is similar to string n.

For second form Consider string X= AiAj....Ap.......AqAr (remove A(n+1) from string K) We can easily say that String X can be obtained from String Y = A1A2A3.....An as K is derived from S... (I can comment on this if any one finds the above statment difficult to understand)

From the assumption, we know String X can also be derived from Y.... Now we know (AiAj<-<-.....)Ap(..An...Ar) = A1A2A3...An The above ... denotes some set of Operations... So I want to denote them by O1 and O2

O1ApO2 = A1A2...An

Now for String K O1ApA(n+1)<-O2 will yield the result A1A2....AnA(n+1)

So we can prove that if this property holds for n then it also holds for n+1

Hence proved!!!!!

I am really bad at writing solutions..... I am not at all accustomed for this formatting and all......So please let me know if

Log in to reply

Is each letter in the string considered distinct?

Daniel Liu - 5 years, 1 month ago

Log in to reply

Yes.

Sreejato Bhattacharya - 5 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...