Some children have made up a simple version of the game “Duck, Duck, Goose”. In this game a group of people stands in a circle, and the person who is “it” taps the first person on the shoulder and says “duck”. The next person is tapped and called “duck” The next person is tapped and called “goose”, and the process is repeated. Every person who is called “goose” must sit down when they are tapped.
If there are a million people in a circle, and they are labeled sequentially from 1 to 1,000,000, and the tapper starts at person 1 going around and around until only one person is left standing, then what is that last person’s number?
E5. Duck, Duck, Goose
This problem was sent to me (as is) by Walter Carter of Seattle.
Subscribe to:
Post Comments (Atom)
1 comment:
I discovered this problem comes from the story of the Jewish historian Josephus Flavius, where every 3rd person in the circle was chosen to be killed in preference to being captured by the Romans. In the original problem there were 41 men in the circle and Josephus, who preferred not to be martyred, chose the last spot.
I wrote a MATLAB program to get the answer, as follows:
last = 1000000;
x = 1:last; %x is initially a vector with last entries, i-th entry equals i.
while last > 2
x(3:3:last) = []; %remove every third entry
m = mod(last,3);
last = length(x);
if m > 0 %create a vector y with 1 or 2 entries, the "tail"
y = ones(1);
for j = 1:m,
y(j) = x(last - m + 1);
x(:,last - m + 1) = []; %take the last 1 or 2 entries off the end of x
end %for
x = [y x]; %move the last 1 or 2 entries to the beginning, concatenate vectors
end %if
end %while
x(2) %only two individuals left, x(1) will be chosen in last round leaving x(2).
The answer is 637798. A non-computer-assisted answer is requested.
Post a Comment