Author |
Topic: Circular jail cell revisited (Read 3123 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Circular jail cell revisited
« on: Jan 7th, 2008, 4:51am » |
 Quote  Modify
|
This is based on Circular Jail Cell. August and Bernhard work at a circular jail with 100 cells, numbered 1-100. Bernhard's job is to lock the cells, but he's a little bit funny: for each cell n that August tells him to lock, Bernhard will go around and toggle cells n, 2n, 3n, ..., locking them if they are unlocked, and unlocking them if they are locked.
So if August tells Bernhard to lock some set S of cells, then assuming the cells start out unlocked, the ones that actually end up locked is another set T, which is a function of S, say T = Z(S). So the original riddle is to determine Z(C), where C = {1,2,3,...} is the complete set of cells.
Now suppose all the cells are unlocked, and August needs a certain subset T of them locked. Luckily, there's always a unique set S = M(T) such that if August tells Bernhard to lock set S, the ones that actually end up locked will be precisely T, i.e., T=Z(S). In other words, the function M is the inverse of Z.
What is M(T), when:
(S) T = {1,4,9,...} is the set of squares? 
(C) T is the set of cubes?
(K) T is the set of perfect k-th powers, for some fixed k>1?
(P) T is the set of primes?
(1) T = {1}?
(SF) T is the set of square-free integers?
(BT) Let S0 = T0={1}, and recursively define Sn+1=M(Sn), Tn+1 = Z(Tn). What are Sn and Tn?
And most importantly, why did I call the two functions Z and M?
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Circular jail cell revisited
« Reply #1 on: Jan 7th, 2008, 7:13am » |
Quote Modify
|
I don't have a function, but I have an algorithm. 
Based on the simple observation that no i in S affects any elements of T < i:
given T, let sets S and U be initially empty
for each 1 <= i <= 100:
if (i in T and not i in U) or (i in U and not i in T)
add i to S
for each i <= j <= 100, j = 0 (mod i)
if j in U
remove j from U
else
add j to U
The obvious results to interpret are:
S: all integers
1: the squarefree integers
SF: the perfect squares
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Circular jail cell revisited
« Reply #2 on: Jan 7th, 2008, 8:05am » |
Quote Modify
|
on Jan 7th, 2008, 7:13am, SMQ wrote:
The obvious results to interpret are:
S: all integers
1: the squarefree integers
SF: the perfect squares
|
|
The first two are right. Do you have a proof for the second one?
|
| « Last Edit: Jan 7th, 2008, 8:11am by Eigenray » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Circular jail cell revisited
« Reply #3 on: Jan 7th, 2008, 8:33am » |
Quote Modify
|
Ahh, yes, for SF I missed that it's only the squares of squarefree numbers. 
And no, I have no proofs, just lists of numbers.  I generally start from the empirical and work toward the analytical...
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Circular jail cell revisited
« Reply #4 on: Jan 7th, 2008, 12:16pm » |
Quote Modify
|
on Jan 7th, 2008, 4:51am, Eigenray wrote:| (C) T is the set of cubes? |
|
Let N be a number with prime factorization p0n0*...*pini. Then N is in S if and only if all ni are congruent to 0 or 1 (mod 3).
Proof: Let M be a number with prime factorization q0m0*...*qimi. Then how many factors of M fit the criteria above? It's the product of:
a) For all mi = 0 (mod 3): (2*(mi / 3) + 1)*
b) For all mi = 1 (mod 3): 2*((mi + 2) / 3)*
c) For all mi = 2 (mod 3): 2*((mi + 1) / 3)*
Thus, the number of factors is even unless all mi = 0 (mod 3), which is equivalent to M being a cube. Thus, with S defined as above, T is the set of cubes.
|
| « Last Edit: Jan 7th, 2008, 12:17pm by Joe Fendel » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Circular jail cell revisited
« Reply #5 on: Jan 7th, 2008, 12:16pm » |
Quote Modify
|
Cute twist Eigenray!
Moo!
btw, isn't it Ferdinand and not Bernhard ?
|
| « Last Edit: Jan 7th, 2008, 12:48pm by Aryabhatta » |
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Circular jail cell revisited
« Reply #6 on: Jan 7th, 2008, 2:30pm » |
Quote Modify
|
on Jan 7th, 2008, 12:16pm, Joe Fendel wrote:
Let N be a number with prime factorization p0n0*...*pini. Then N is in S if and only if all ni are congruent to 0 or 1 (mod 3).
Proof: Let M be a number with prime factorization q0m0*...*qimi. Then how many factors of M fit the criteria above? It's the product of:
a) For all mi = 0 (mod 3): (2*(mi / 3) + 1)*
b) For all mi = 1 (mod 3): 2*((mi + 2) / 3)*
c) For all mi = 2 (mod 3): 2*((mi + 1) / 3)*
Thus, the number of factors is even unless all mi = 0 (mod 3), which is equivalent to M being a cube. Thus, with S defined as above, T is the set of cubes. |
|
Occurs to me now that this method works for perfect K-th powers also, replacing "3" with "K". In fact, works for perfect squares, too - and results in S being all integers.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Circular jail cell revisited
« Reply #7 on: Jan 7th, 2008, 4:58pm » |
Quote Modify
|
on Jan 7th, 2008, 2:30pm, Joe Fendel wrote:| Occurs to me now that this method works for perfect K-th powers also, replacing "3" with "K". In fact, works for perfect squares, too - and results in S being all integers. |
|
Yes, exactly! More generally, what happens if T is defined by an allowable set of exponents for each prime?
on Jan 7th, 2008, 12:16pm, Aryabhatta wrote:| btw, isn't it Ferdinand and not Bernhard ? |
|
No, they're two different people 
But I take it you know the formula for M(T)?
Here are two more:
(PO) As before, Sn=Mn({1}), Tn=Zn({1}). Determine the partial order on the sets {Sn} and on {Tn} (I haven't actually worked out the latter but it seems doable.) I realize now it would have been better to call these sets An and Bn, respectively. Oh well.
(PP) What is M(T), where T is the set of prime powers? All perfect powers?
And of course,
(BONUS) Anything else you can think of!
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Circular jail cell revisited
« Reply #8 on: Jan 7th, 2008, 7:28pm » |
Quote Modify
|
on Jan 7th, 2008, 4:58pm, Eigenray wrote:
No, they're two different people
But I take it you know the formula for M(T)?
|
|
I guess...
Anyway I think this is the formula for M(T)
if t(n) is the indicator function for T, i.e t(k) = 1 if k is in T, else t(k) = 0
then the indicator function s for S = M(T) is given by
s(n) = sum{d | n} mu(d) * t(n/d) mod 2
where mu is the mobius function.
Basically, this is the mobius inversion formula.
|
| « Last Edit: Jan 7th, 2008, 7:28pm by Aryabhatta » |
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Circular jail cell revisited
« Reply #9 on: Jan 8th, 2008, 8:13am » |
Quote Modify
|
on Jan 7th, 2008, 4:58pm, Eigenray wrote:
Yes, exactly! More generally, what happens if T is defined by an allowable set of exponents for each prime? |
|
Let's consider A to be a subset of positive integers which are "allowable exponents" for members of T. That is, T consists of all numbers N such that when N is decomposed into N = p0n0*...*pini, then all the nk are in A. (So in the case of T = perfect kth powers, A is simply all multiples of k.)
Then let B be all numbers m such that either:
m in A and m-1 not in A or
m not in A and m-1 in A
(So in the case of T = perfect kth powers, B is the set of numbers = 0 or 1 mod k.)
Then S will consist of all numbers M such that when M is decomposed into M = p0m0*...*pimi, we have all mi in B.
|
|
IP Logged |
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Circular jail cell revisited
« Reply #10 on: Jan 8th, 2008, 8:46am » |
Quote Modify
|
Let f(N) represent the indicator function that the door will be ordered to be closed.
Then in order to get all the kth powers closed we need
f(p1m1p2m2...pnmn)
=1 if mi==1(mod)k where i is the smallest index such that mi%k!=0
f(p1m1p2m2...pnmn)
=1 if mi==0(mod)k for all i
f(p1m1p2m2...pnmn)
=0 if mi==r(mod)k and 2<=r<=k-1 where i is the smallest index such that mi%k!=0
This is just 1 solution. Note that many solutions can be obtained by permuting the order of primes.
|
|
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Circular jail cell revisited
« Reply #11 on: Jan 8th, 2008, 11:00am » |
Quote Modify
|
on Jan 7th, 2008, 4:51am, Eigenray wrote:| (P) T is the set of primes? |
|
This turned out to be a pretty tricky one, so I'll hide my answer:
| hidden: | S is the set of numbers which are either:
(Type A) A prime-square times a squarefree number (relatively prime to the square) or
(Type B) A product of an odd number of distinct primes.
Here's the proof:
First I claim that any N which is not a prime power contains an even number of "Type A" divisors. For each prime p such that p2 divides N, there is a divisor for every squarefree divisor of N relatively prime to p, which is equal to 2i-1, where i is the number of prime divisors of N. Since N is not a prime power, i > 1, and thus there is an even number of "Type A" divisors for each p2 which divides N, and thus a total even number of "Type A" divisors.
Next I claim that any N which is not a prime power contains an even number of "Type B" divisors. Let i be the number of prime divisors of N, and let D be the largest squarefree divisor of N (ie the product of all i primes which divide N). Suppose i is odd. Then exactly half of all squarefree divisors of N are odd, since for any squarefree divisor d, either d or D/d contains an odd number of primes. Thus the total number of "Type B" divisors is 2i/2, which, since i > 1, is even. Suppose i is even. Then we can pair the squarefree divisors into couples of {d, D/d}, and for each pair either both numbers are "Type B" divisors or neither are. Therefore the number of "Type B" divisors is even.
That shows that all N which are not prime powers are outside T. So let N = pi. If i=0 (N=1), then N contains 0 divisors in S, so N is not in T. If i=1, (N=p) then p is the only divisor of N which is in S, so N is in T. If i>1, then p and p2 are the only divisors of N which are in S, so N is not in T.
Thus T contains all, and only, prime numbers.
|
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Circular jail cell revisited
« Reply #12 on: Jan 8th, 2008, 2:10pm » |
Quote Modify
|
on Jan 7th, 2008, 4:58pm, Eigenray wrote:
(PP) What is M(T), where T is the set of prime powers? All perfect powers?
|
|
It's easier than primes ... just take products of odd number of primes.
How many times p1^n1.p2^n2.p3^n3...pk^nk is (un)locked?
\sum_{i odd} {k \choose i}.
Pair {k \choose i} with {k \choose k-i}.
For k odd we pair missing in sum with presented so the sum equals 2^{k-1}.
For k=0(mod 4) each is paired so the sum is even.
For k=2 (mod 4) all except the {k \choose k/2} are paired. But {2i \choose i}=2{2i-1\choose i-1} is even.
So the only case when the sum is odd is k=1. The power of prime.
I was interupted ... I wanted originaly to hide it , but as it was already quoted ...
|
| « Last Edit: Jan 8th, 2008, 3:41pm by Hippo » |
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Circular jail cell revisited
« Reply #13 on: Jan 8th, 2008, 2:32pm » |
Quote Modify
|
on Jan 8th, 2008, 2:10pm, Hippo wrote:
It's easier than primes ... just take products of odd number of primes.
How many times p1^n1.p2^n2.p3^n3...pk^nk is (un)locked?
\sum_{i odd} {k \choose i}.
Pair {k \choose i} with {k \choose k-i}.
For k odd we pair missing in sum with presented so the sum equals 2^{k-1}.
For k=0(mod 4) each is paired so the sum is even.
For k=2 (mod 4) all except the {k \choose k/2} are paired. But {2i \choose i}=2{2i-1\choose i-1} is even.
So the only case when the sum is odd is k=1. The power of prime. |
|
Is 1 considered a "prime power"? I would think so (it's 20, for example), but this method misses them. If we decide that it is, then just take products of even numbers of distinct primes instead!
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Circular jail cell revisited
« Reply #14 on: Jan 8th, 2008, 4:31pm » |
Quote Modify
|
on Jan 7th, 2008, 7:28pm, Aryabhatta wrote:| Anyway I think this is the formula for M(T) |
|
Right, but it can be simplified a bit...
Quote:| Basically, this is the mobius inversion formula. |
|
But have you figured out the relevance of the letter Z?
on Jan 8th, 2008, 8:46am, balakrishnan wrote:| This is just 1 solution. Note that many solutions can be obtained by permuting the order of primes. |
|
I don't understand why you order the primes: they're all treated equally, and there's a unique solution for S. For example, nothing of the form pq2 would be in it for K>2.
on Jan 8th, 2008, 11:00am, Joe Fendel wrote:| This turned out to be a pretty tricky one, so I'll hide my answer: |
|
Right again. Do you see how to use Aryabhatta's post for a simpler derivation? (Though I'm not sure how you derived it.)
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Circular jail cell revisited
« Reply #15 on: Jan 8th, 2008, 4:33pm » |
Quote Modify
|
on Jan 8th, 2008, 8:13am, Joe Fendel wrote:Let's consider A to be a subset of positive integers which are "allowable exponents" for members of T. <snip> Then let B be all numbers m such that either:
m in A and m-1 not in A or
m not in A and m-1 in A |
|
Exactly! Does this process look familiar? (If not, you're in for a treat )
Note that this works whenever T is 'multiplicative' and treats all primes equally, which is actually all parts except (P) and (PP). Try part (BT)! [And then figure out why it's called (BT).] Most of the others are special cases of this one.
on Jan 8th, 2008, 2:10pm, Hippo wrote:| just take products of odd number of primes. |
|
on Jan 8th, 2008, 2:32pm, Joe Fendel wrote:| just take products of even numbers of distinct primes instead! |
|
These two posts, taken together, contain a clever solution of (1). Do you see it?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Circular jail cell revisited
« Reply #16 on: Jan 8th, 2008, 5:31pm » |
Quote Modify
|
on Jan 8th, 2008, 4:31pm, Eigenray wrote:
Right, but it can be simplified a bit...
But have you figured out the relevance of the letter Z?
|
|
This one beats me, I see no relevance of 'Z'.
Let me see if I can simplify the formula for M(T) a bit more, but I am not sure if I will be able to do it...
|
|
IP Logged |
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Circular jail cell revisited
« Reply #17 on: Jan 8th, 2008, 9:40pm » |
Quote Modify
|
Yes true:
all numbers that have the prime powers to be either 0 or 1 will be in the set.(in order to get the kth powers closed)
|
|
IP Logged |
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: Circular jail cell revisited
« Reply #18 on: Jan 8th, 2008, 10:55pm » |
Quote Modify
|
My observation is that the set P is
the set of the products of odd number of primes(ie product of 1 prime,3 primes...)+
the set of all numbers N=2^m1 3^m2 5 ^m3...
such that exactly one of m1,m2.. is 2 and the others are either 0 or 1.
In other words if
N=2m1 3m2...pkmk, then
N is included in P iff
atleast one of mi is non-zero and atmost one of mi exceeds 1 and none of mi exceeds 2 and if all of mis are 0 or 1, then odd number of mi's are ones
|
| « Last Edit: Jan 9th, 2008, 6:58pm by balakrishnan » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Circular jail cell revisited
« Reply #19 on: Jan 9th, 2008, 4:19am » |
Quote Modify
|
on Jan 8th, 2008, 4:33pm, Eigenray wrote:
These two posts, taken together, contain a clever solution of (1). Do you see it? |
|
The square-free numbers were cited before and I am not sure Joe added 1 combining these results or modifies slightly the original proof.
(The argument for i even in sums is almost same except k=2 (mod 4) and k=0 (mod 4) cases changes role and for k=0 {0 \choose 0} = 2{-1 \choose -1} cannot be used.)
|
| « Last Edit: Jan 9th, 2008, 4:23am by Hippo » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Circular jail cell revisited
« Reply #20 on: Jan 9th, 2008, 6:20am » |
Quote Modify
|
on Jan 9th, 2008, 4:19am, Hippo wrote:| The square-free numbers were cited before and I am not sure Joe added 1 combining these results or modifies slightly the original proof. |
|
What I mean is, given the following two facts:
Z(products of odd # of distinct primes) = {all prime powers, except 1},
Z(products of even # of distinct primes) = {all prime powers, including 1},
can you derive M({1})?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Circular jail cell revisited
« Reply #21 on: Jan 9th, 2008, 7:05am » |
Quote Modify
|
on Jan 9th, 2008, 6:20am, Eigenray wrote:
What I mean is, given the following two facts:
Z(products of odd # of distinct primes) = {all prime powers, except 1},
Z(products of even # of distinct primes) = {all prime powers, including 1},
can you derive M({1})? |
|
I expect most of us understand that Z(A xor B)=Z(A) xor Z(B) ...
and therefore as well M(A xor B)=M(A) xor M(B)
... but the observation is interesting
|
| « Last Edit: Jan 9th, 2008, 7:18am by Hippo » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Circular jail cell revisited
« Reply #22 on: Jan 9th, 2008, 10:34pm » |
Quote Modify
|
So, M and Z distribute over addition, kind of like how multiplication would...
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Circular jail cell revisited
« Reply #23 on: Jan 10th, 2008, 12:02am » |
Quote Modify
|
on Jan 9th, 2008, 10:34pm, Eigenray wrote:| So, M and Z distribute over addition, kind of like how multiplication would... |
|
Addition ... the symmetric difference of sets.
What multiplication on sets do you mean ?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Circular jail cell revisited
« Reply #24 on: Jan 10th, 2008, 1:35am » |
Quote Modify
|
That's the question
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print