6
$\begingroup$

You are trying to make an impossible game where there are $100$ balls numbered from $1$ to $100$ and ordered in the worst case and put next to each other. The player is supposed to order the balls from $1$ to $100$ with the simple rule you are going to assign:

The player can switch two balls location if there is at least $x$ amount of balls between these two balls.

What should be the least $x$ value to make the player not able to win this game in the worst ordered form possible? So the player may think it is a fair game.

Improve this question
$\endgroup$
6
  • $\begingroup$ "Not able to win this game whatsoever"? Does that mean all starting positions are unwinnable, or that there exist unwinnable positions? $\endgroup$
    – Deusovi ♦
    Apr 11, 2017 at 19:15
  • $\begingroup$ probably 48? So you cant move middle one, first and last?.... well.. if its not first, last or 50. $\endgroup$
    – Jan Ivan
    Apr 11, 2017 at 19:19
  • $\begingroup$ @Deusovi tried to explain more clearly... please reread it. $\endgroup$
    – Oray
    Apr 11, 2017 at 19:19
  • $\begingroup$ What do you mean by 'ordered in the worst case'? $\endgroup$
    – Beastly Gerbil
    Apr 11, 2017 at 19:20
  • $\begingroup$ @BeastlyGerbil that means the balls are ordered where the player will not able to win the game with the least x value you are going to assign, and if x value is one less, the game is winnable whatever the order is. $\endgroup$
    – Oray
    Apr 11, 2017 at 19:28

3 Answers 3

Reset to default
11
$\begingroup$

Looking at both answers before me, if I understand question correctly, x means number of balls between two positions. And if my math is correct, between positions 50 and 100 are 49 balls. So at x=49, the closest ball that can move to position 100 is the one at position 50. Same reasoning says that at x=49, the closest ball that can move to position 1 is the one at position 51. So x=49 is still solvable using Deusovi's solution since balls at positions 51+ can just swap with position 1, and balls at positions 50- can just swap with position 100. I'd say minimum x for a no-solution is at x=50, where balls 50 and 51 are immovable.

Improve this answer
$\endgroup$
20
$\begingroup$

Trivially, 50 will make the game impossible, since positions 50 and 51 will be unmovable.

It's also the lowest that will be impossible. If $x$ is 49, then there exists a strategy:
enter image description here Use slots 1 and 100 as "buffer" slots to transfer the other ones. 1 is the buffer for 51-99, and 100 is the buffer for 2-50. To get any ball from one slot to another, use these steps:
- Move it to its buffer
- Move it to the goal point's buffer (if they're the same, don't do anything)
- Move it to the goal point

For instance, if ball 40 is in slot 97, then swap 97-1, 1-100, and 100-40.
This does not disturb any of the other non-buffer slots. At the end, all of the nonbuffer slots will be filled with the correct numbers - after that, you can simply swap 1 and 100 if they're in the wrong places.

Therefore the solution is:

$x=50$.

(Thanks to Hakdo for making me realize I was off by one, and justhalf for pointing it out!)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Like noted by Hakdo, with x=49 you can move 49 to 100, right? $\endgroup$
    – justhalf
    Apr 12, 2017 at 3:26
  • $\begingroup$ @justhalf - Whoops, that's right! Fixed! $\endgroup$
    – Deusovi ♦
    Apr 12, 2017 at 3:45
  • $\begingroup$ Position 49 can be moved to 100 with x=50. I think it should be positions 50 and 51 that are unmovable, as also noted by Hakdo. I suggest you upvote his/her answer also =) $\endgroup$
    – justhalf
    Apr 12, 2017 at 3:51
9
$\begingroup$

If $x$ is $48$ or less, then we can imagine rearranging the balls' positions in the following order:

$1,51,2,52,3,53,\dots,49,99,50,100$.

Since under this order we can exchange any two adjacent balls, it's clear that we can rearrange them in any possible way so we will always be able to sort them.

But if $x$ is $49$ or more, then we can't move positions $49$ or $50$, so it will be impossible to win in some cases.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ Oooh, that's a good way of putting it. $\endgroup$
    – Deusovi ♦
    Apr 11, 2017 at 19:37

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.