| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Berge Sorting | Antoine Deza
; William Hua
; | Date: |
28 Dec 2005 | Subject: | Combinatorics | Abstract: | In 1966, Claude Berge proposed the following sorting problem. Given a string of $n$ alternating white and black pegs on a one-dimensional board consisting of an unlimited number of empty holes, rearrange the pegs into a string consisting of $lceilfrac{n}{2}
ceil$ white pegs followed immediately by $lfloorfrac{n}{2}
floor$ black pegs (or vice versa) using only moves which take 2 adjacent pegs to 2 vacant adjacent holes. Avis and Deza proved that the alternating string can be sorted in $lceilfrac{n}{2}
ceil$ such {em Berge 2-moves} for $ngeq 5$. Extending Berge’s original problem, we consider the same sorting problem using {em Berge $k$-moves}, i.e., moves which take $k$ adjacent pegs to $k$ vacant adjacent holes. We prove that the alternating string can be sorted in $lceilfrac{n}{2}
ceil$ Berge 3-moves for $n
otequiv 0pmod{4}$ and in $lceilfrac{n}{2}
ceil+1$ Berge 3-moves for $nequiv 0pmod{4}$, for $ngeq 5$. In general, we conjecture that, for any $k$ and large enough $n$, the alternating string can be sorted in $lceilfrac{n}{2}
ceil$ Berge $k$-moves. This estimate is tight as $lceilfrac{n}{2}
ceil$ is a lower bound for the minimum number of required Berge $k$-moves for $kgeq 2$ and $ngeq 5$. | Source: | arXiv, math/0512612 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |