Last Man Standing - closed form equation

Question

I wrote a matlab code inorder to find the last man standing for the problem given here.

Problem: n people are standing in a circle with gun in their hands. 1 kills 2, 3 kills 4, 5 kills 6 and so on (circularly) till we are left with only one person. Who will be the last person alive.

function N = lastManStanding(n)

while length(n) ~= 1
    if mod(length(n),2) == 0
        for ii = 1:length(n)/2
            a(ii) = [ii*2];
        end
        n(a) = [];
        a = [];
    end
    if mod(length(n),2) == 1
        for jj = 1:floor(length(n)/2)
            b(jj) = [jj*2];
        end
        n(b) = [];
        n = circshift(n,[0,1]);
        b = [];        

    end
end

N = n;

What this code basically does is it takes a range array (1,....,n) as input and returns the last remaining index. I was wondering if there exists a closed form equation to solve this or if the above code can be simplified further.

UPDATE Find the updated code below

function N = lastManStanding(n)

while length(n) ~= 1
    if mod(length(n),2) == 0
        n(2:2:end) = [];        
    else mod(length(n),2) == 1
        n(2:2:end) = [];
        n = circshift(n,[0,1]);
    end
end

N = n;

Answer 1

Closed form solution:

If you plot the "survivor" index i for n = 1:100 using your script, you will see a sawtooth shaped function which falls back to 1 for every n = 2^k, where k being integer values. Which means that at those points mod(n, 2^k) = 0.

You can find 2^k to be the next minor multiple of 2 of n. Hence k is:

k = floor(log2(n));

In between the edges of the function where n > 2^k the function rises with 2 * mod(n, 2^k). Since the function has an offset of 1 we can thus write the closed form solution as:

i = 2 * mod(n, 2^k) + 1;

or inline:

i = 2 * mod(n, 2.^floor(log2(n))) + 1;

The plot:

UPDATE:

This problem is also known as the Josephus problem. You can find a more general and mathematically rigorous derivation here: https://en.wikipedia.org/wiki/Josephus_problem.

Answer 2

You can also solve this problem without loop, in a more mathematical way:

%for n in [1,inf[
lastManStanding = mod(n,2.^floor((log(n)/log(2))))*2+1;

As suggested by wolfie you can also use directly the function log2

lastManStanding = mod(n,2.^floor(log2(n)))*2+1;

The function mod can deal with vector, so n can be a vector.

Answer 3

Your updated code is broken, you have an end statement before your else statement. Your code:

function N = lastManStanding(n)

while length(n) ~= 1
    if mod(length(n),2) == 0
        n(2:2:end) = [];        
    end % <------------------------ PROBLEM!! end before else
    else mod(length(n),2) == 1 % <- PROBLEM!! condition not needed for else
        n(2:2:end) = [];
        n = circshift(n,[0,1]);
    end
end

N = n;

It can be further simplified by noting that n(2:2:end) = []; is common in the if and the else, so can be pulled outside...

function N = lastManStanding(n)

while length(n) ~= 1
    n(2:2:end) = [];  
    if mod(length(n),2) == 1
        n = circshift(n,[0,1]);
    end
end

N = n;

Also you can actually remove the if entirely because the output of your mod is either 0 or 1, and that's how much you want to shift by!

function N = lastManStanding(n)

while length(n) ~= 1
    shft = mod(length(n),2); % Have to calculate here before n gets changed
    n(2:2:end) = [];  
    n = circshift(n,[0,shft]);
end

N = n;

Last optimisation suggested in the comments is to not use N at all. Since n will just be a scalar at the end anyway, use

function n = lastManStanding(n)

while length(n) ~= 1
    shft = mod(length(n),2); % Have to calculate here before n gets changed
    n(2:2:end) = [];  
    n = circshift(n,[0,shft]);
end

Note that I've not tested if the answers are correct, but the results are the same as yours.