## Solitaire game

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Solitaire game

Hi,

This a new game designed to be played on computer.

Mobius solitaire game.

You take an urn with 100 balls numbered from 1 to 100.
You start picking randomly one ball noted k(1) :
- you compute v=mu(k(1)) where mu() is the Mobius function
- if v=0 then you put back the picked ball to the urn
- if v=1 you place a new ball numbered (max(A)+1) where A is the set the remaining balls and put aside the just picked ball with v=1
- if v=-1 you choose "smartly" one ball from the urn and you replace it by the ball just picked with v=-1

You do the process until you empty completely the urn.
If you play smartly how many picks do you need in the worst case to empty the urn?

Example :

URN : 1,2,3,......,100
Pick 1 : k(1)=15 then v=mu(15)=1 as the max(A)=100 you place a new ball numbered 101 on the urn and remove from the game the ball numbered 15
Pick 2 : k(2)=4 then v=mu(4)=0 you put back the picked ball 4 to the urn
Pick 3 : k(3)=7 then v=mu(7)=-1 you need to choose one ball from the remaining balls
URN contains :1,2,3,...,14,16,17,....,100,101 (15 was removed and 101 was added)
Let us say that removing a ball with v=0 is "smart" choice (if is up to the player to choose the best strategy not me). So you remove the ball 8 (v=0)
and so on

Is there any coder?

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Solitaire game

In the worst case you'd keep getting only balls with v=1, or v=0. thus never emptying the urb.
A greedy strategy would be to remove the balls with v=1, or v=0, until you have only balls with v=-1

I supposed if you can calculate v fast enough, you could make a strategy relating to whether the next ball you add has v=-1 or not.

Tirear
Posts: 37
Joined: Fri Feb 05, 2016 5:42 pm UTC

### Re: Solitaire game

Demki wrote:I supposed if you can calculate v fast enough, you could make a strategy relating to whether the next ball you add has v=-1 or not.

There's no point. The next ball you add will always have one of two possibilities: one more than the highest you have seen, or some number you have already removed. Thus, removing top numbers to manipulate the next ball added will never result in v=- 1 unless you first remove a ball with v=- 1, which would be counterproductive. So be greedy, but leave the highest number in place (and maybe the second highest if the highest has v=1).

Sandor
Posts: 180
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: Solitaire game

Demki wrote:I supposed if you can calculate v fast enough, you could make a strategy relating to whether the next ball you add has v=-1 or not.

I would have thought so too, but it doesn't seem to work. I tried 3 different strategies for when you pick a v=-1, and had a few millions goes at each:

Strategy 1: Replace the smallest v=0, or if none, the smallest v=1, of if none the smallest v=-1. Approx 153.8 goes required
Strategy 2: Replace the largest v=0, or if none, the largest v=1, of if none the largest v=-1. Approx 159.8 goes required
Strategy 3: If mu(largest)=0, and mu(second largest+1)=-1, replace the largest, else follow strategy 1. Approx 153.9 goes required

The numbers appear to be accurate to +/-0.1 or so. I then tried a few other strategies, but couldn't find anything better than strategy 1.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Solitaire game

If we note :
a the number of balls picked with v=1
b the number of balls picked with v=0
c the number of balls picked with v=-1

Let us note the total number of picks = N

we could express the number of picks R required to empty the urn as :

R=a*k1+b*k2+c*k3

where (k1,k2,k3) are parameters describing some strategy K

Example :
if b=N hence a=c=0 then R is infinite
R has a lower bound too (not hard to compute) and so on