Some interesting problems I can't solve
(from Chalk Up Another One by Sidney Harris)
Of course, there have been lots of problems I haven't been able to solve. But these problems are fun to think about, even if they seem to be difficult (at least to me!, but I am not a mathematician).
Find all the points where Newton's root-finding method converges to a root of the sine function.
Find a constant-time method for the children's game one-potato two-potato. Or prove it can't be done.
After I had worked on this problem, I was re-reading the outstanding book Introduction To Algorithms by Cormen, Leiserson, and Rivest. I came across the following exercise problem: (pg. 296)
Josephus permutation
The Josephus problem is defined as follows. Suppose that n people are
arranged in a circle and that we are given a positive integer
m<=n. Beginning with a designated first person, we proceed around
the circle, removing every mth person. After each person is
removed, counting continues around the circle that remains. This
process continues until all n people have been removed. The order in
which the people are removed from the circle defines the
(n,m)-Josephus permutation of integers 1,2,...,n. For example,
the (7,3)-Josephus permutation is <3,6,2,7,5,1,4>.
a. Suppose that m is constant. Describe an O(n)-time algorithm that
given an integer n, outputs the (n,m)-Josephus permutation.
b. Suppose that m is not constant. Describe an O(n lg n)-time
algorithm that, given integers n and m, outputs the (n,m)-Josephus
permutation.
Of course, my question asks for a constant-time algorithm (or a lower-bound for the algorithm) for the last number in a (n,8)-Josephus permutation.
I'm thinking of a number between zero and sixty-three. What is
the minimum number of yes-no questions you need to ask to guess
my number? What if I'm allowed to lie once (if I choose)? Twice?...
With one lie,
I have found a solution that takes:
clog2(N)+clog2(clog2(N)+1)+1;
Where the 0<number<(N-1) &
clog2(N)=ceil(log2(N)).
but I haven't proved this is optimal.