Author |
Topic: smallest string with nondistinct consecutive chars (Read 4181 times) |
|
inexorable
Full Member
Posts: 211
|
 |
smallest string with nondistinct consecutive chars
« on: Sep 21st, 2012, 12:17pm » |
 Quote  Modify
|
Given a string consisting of a, b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'.
What is the smallest string which can result by applying this operation repeatedly?
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
|
Re: smallest string with nondistinct consecutive c
« Reply #1 on: Sep 22nd, 2012, 8:37pm » |
Quote Modify
|
Haven't thought through completely, but seems like the smallest string is of length either 1 or 2 (of the same character).
Basically if n_a, n_b, n_c are the number of a's, b's and c's in the string.
Then either all three (n_a,n_b,n_c) are of the same parity, in which case, the answer is 2 and that can be made to be either the first or last character of the string.
Or there is one of a different parity, say n_a, in which case, we can end up with a single a.
A proof by induction seems to work, but since you have posted this in the cs forum...
The observation used is that the parity of n_a+n_b, n_b+n_c, n_a + n_c are invariant.
|
| « Last Edit: Sep 22nd, 2012, 8:40pm by Aryabhatta » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: smallest string with nondistinct consecutive c
« Reply #2 on: Sep 23rd, 2012, 2:15am » |
Quote Modify
|
on Sep 22nd, 2012, 8:37pm, Aryabhatta wrote:| Haven't thought through completely, but seems like the smallest string is of length either 1 or 2 (of the same character). |
|
Definitely not so if you start with a string that contains only the same character (more than two time). You can't reduce, say, aaaaaaaaaaa to anything smaller.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: smallest string with nondistinct consecutive c
« Reply #3 on: Sep 23rd, 2012, 7:58am » |
Quote Modify
|
on Sep 23rd, 2012, 2:15am, towr wrote:
Definitely not so if you start with a string that contains only the same character (more than two time). You can't reduce, say, aaaaaaaaaaa to anything smaller.
|
|
Yes, those are the special cases I forgot to mention and I suppose you agree that they are the uninteresting cases 
|
| « Last Edit: Sep 23rd, 2012, 11:21am by Aryabhatta » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: smallest string with nondistinct consecutive c
« Reply #4 on: Sep 23rd, 2012, 12:43pm » |
Quote Modify
|
Well, seeing as this is a CS puzzle, I'm guessing we need to find an algorithm that will lead us to the shortest string. In which case it's important not to get trapped in those special cases, since that's quite easy.
Say you have abccc, and approach it greedily from left to right, then abccc => cccc, and you're stuck. Whereas a winning route is e.g. abccc => aacc => abc => cc.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: smallest string with nondistinct consecutive c
« Reply #5 on: Sep 23rd, 2012, 9:10pm » |
Quote Modify
|
The proof by induction actually gives an algorithm.
Let n_a, n_b, n_c be the numbers of a's, b's and c's.
At least two of n_a, n_b, n_c have the same parity (even or odd basically): say n_b and n_c.
Property P: Also keep the observation in mind that an operation keeps the parity of n_a+n_b, n_b + n_c and n_c+n_a invariant.
Case I)
First consider the case when n_a is of different parity than n_b and n_c. Since we will always end up with a string formed by a single character(possibly repeated), by property P above, we end up with an odd number of a's. By induction on the length of the string, this will be shown to be a single a.
Given a string satisfying Case I), we simply make one transformation which involves an a (or any random transform if there aren't any a's). This reduces the length, while maintaining the property of n_a being different from n_b and n_c (parity wise), and not making the whole string comprise solely of 3 or more a's (or b's or c's). By induction, we can now claim that we will end up with a single a.
This give an algorithm: Picking any transform which does not make all the characters equal (and there will always be one, as we greedily pick the one with mismatched parity, if it exists).
Case II)
Now consider the second case, when all have the same parity.
Consider one of the characters at the end, say c.
Now consider the string without that c. In this string, n_c has different parity from the others, and by the above Case I, that string can be transformed to c.
Thus the whole string can be transformed to cc.
cc is the best we can do, since parity of n_a + n_c is invariant, and thus the number of c's at the end has to be even.
This gives an algorithm for the all same parity case: fix an end, and then apply the transformations as in Case I).
For instance in the example you give:
abccc: Fix the last c and consider abcc -> aac->ab->c
Thus we get to cc.
If we chose to fix a, we can get to aa.
|
| « Last Edit: Sep 23rd, 2012, 9:36pm by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print