wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Circular jail cell revisited
        
(Message started by: Eigenray on Jan 7^th, 2008, 4:51am)

Title: Circular jail cell revisited
Post by Eigenray on Jan 7^th, 2008, 4:51am

This is based on [link=http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#circularJailCell]Circular Jail Cell[/link]. 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? :P
(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 [link=http://en.wikipedia.org/wiki/Square-free_integer]square-free integers[/link]?

(BT) Let S₀ = T₀={1}, and recursively define S_n+1=M(S_n), T_n+1 = Z(T_n). What are S_n and T_n?

And most importantly, why did I call the two functions Z and M?

Title: Re: Circular jail cell revisited
Post by SMQ on Jan 7^th, 2008, 7:13am

I don't have a function, but I have an algorithm. ;)

Based on the simple observation that [hide]no i in S affects any elements of T < i[/hide]:
[hide]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
[/hide]
The obvious results to interpret are:
S: [hide]all integers[/hide] :P
1: [hide]the squarefree integers[/hide]
SF: [hide]the perfect squares[/hide]

--SMQ

Title: Re: Circular jail cell revisited
Post by Eigenray on Jan 7^th, 2008, 8:05am

on 01/07/08 at 07:13:37, SMQ wrote:

The obvious results to interpret are:
S: [hide]all integers[/hide] :P
1: [hide]the squarefree integers[/hide]
SF: [hide]the perfect squares[/hide]

The first two are right. Do you have a proof for the second one?

Title: Re: Circular jail cell revisited
Post by SMQ on Jan 7^th, 2008, 8:33am

Ahh, yes, for SF I missed that it's only the [hide]squares of squarefree numbers[/hide]. :-[

And no, I have no proofs, just lists of numbers. :) I generally start from the empirical and work toward the analytical...

--SMQ

Title: Re: Circular jail cell revisited
Post by Joe Fendel on Jan 7^th, 2008, 12:16pm

on 01/07/08 at 04:51:06, Eigenray wrote:

Let N be a number with prime factorization p₀^n₀*...*p_i^n_i. Then N is in S if and only if all n_i are congruent to 0 or 1 (mod 3).

Proof: Let M be a number with prime factorization q₀^m₀*...*q_i^m_i. Then how many factors of M fit the criteria above? It's the product of:
a) For all m_i = 0 (mod 3): (2*(m_i / 3) + 1)*
b) For all m_i = 1 (mod 3): 2*((m_i + 2) / 3)*
c) For all m_i = 2 (mod 3): 2*((m_i + 1) / 3)*

Thus, the number of factors is even unless all m_i = 0 (mod 3), which is equivalent to M being a cube. Thus, with S defined as above, T is the set of cubes.

Title: Re: Circular jail cell revisited
Post by Aryabhatta on Jan 7^th, 2008, 12:16pm

Cute twist Eigenray!

[hide] Moo! [/hide]

btw, isn't it [hide]Ferdinand[/hide] and not [hide]Bernhard[/hide] ;)?

Title: Re: Circular jail cell revisited
Post by Joe Fendel on Jan 7^th, 2008, 2:30pm

on 01/07/08 at 12:16:26, 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.

Title: Re: Circular jail cell revisited
Post by Eigenray on Jan 7^th, 2008, 4:58pm

on 01/07/08 at 14:30:12, 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 [hide]an allowable set of exponents for each prime[/hide]?

on 01/07/08 at 12:16:39, Aryabhatta wrote:

btw, isn't it [hide]Ferdinand[/hide] and not [hide]Bernhard[/hide] ;)?

No, they're two different people ;D
But I take it you know the formula for M(T)?

Here are two more:

(PO) As before, S_n=Mⁿ({1}), T_n=Zⁿ({1}). Determine the partial order on the sets {S_n} and on {T_n} (I haven't actually worked out the latter but it seems doable.) I realize now it would have been better to call these sets A_n and B_n, 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!

Title: Re: Circular jail cell revisited
Post by Aryabhatta on Jan 7^th, 2008, 7:28pm

on 01/07/08 at 16:58:39, Eigenray wrote:

No, they're two different people ;D
But I take it you know the formula for M(T)?

I guess... ;)

Anyway I think this is the formula for M(T)

[hide]

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.

[/hide]

Title: Re: Circular jail cell revisited
Post by Joe Fendel on Jan 8^th, 2008, 8:13am

on 01/07/08 at 16:58:39, Eigenray wrote:

Yes, exactly! More generally, what happens if T is defined by [hide]an allowable set of exponents for each prime[/hide]?

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 = p₀^n₀*...*p_i^n_i, then all the n_k are in A. (So in the case of T = perfect k^th 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 k^th 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 = p₀^m₀*...*p_i^m_i, we have all m_i in B.

Title: Re: Circular jail cell revisited
Post by balakrishnan on Jan 8^th, 2008, 8:46am

[hide]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(p₁^m1p₂^m2...p_n^mn)
=1 if m_i==1(mod)k where i is the smallest index such that mi%k!=0

f(p₁^m1p₂^m2...p_n^mn)
=1 if m_i==0(mod)k for all i

f(p₁^m1p₂^m2...p_n^mn)
=0 if m_i==r(mod)k and 2<=r<=k-1 where i is the smallest index such that mi%k!=0

[/hide]
This is just 1 solution. Note that many solutions can be obtained by permuting the order of primes.

Title: Re: Circular jail cell revisited
Post by Joe Fendel on Jan 8^th, 2008, 11:00am

on 01/07/08 at 04:51:06, Eigenray wrote:

(P) T is the set of primes?

This turned out to be a pretty tricky one, so I'll hide my answer:

[hideb]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 p² divides N, there is a divisor for every squarefree divisor of N relatively prime to p, which is equal to 2^i-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 p² 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 2ⁱ/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 = pⁱ. 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 p² are the only divisors of N which are in S, so N is not in T.

Thus T contains all, and only, prime numbers.
[/hideb]

Title: Re: Circular jail cell revisited
Post by Hippo on Jan 8^th, 2008, 2:10pm

on 01/07/08 at 16:58:39, 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 ...

Title: Re: Circular jail cell revisited
Post by Joe Fendel on Jan 8^th, 2008, 2:32pm

on 01/08/08 at 14:10:11, Hippo wrote:

Is 1 considered a "prime power"? I would think so (it's 2⁰, for example), but this method misses them. If we decide that it is, then just take products of even numbers of distinct primes instead!

Title: Re: Circular jail cell revisited
Post by Eigenray on Jan 8^th, 2008, 4:31pm

on 01/07/08 at 19:28:24, Aryabhatta wrote:

Anyway I think this is the formula for M(T)

Right, but it can be simplified a bit...

Quote:

Basically, this is [hide]the mobius inversion formula[/hide].

But have you figured out the relevance of the letter Z?

on 01/08/08 at 08:46:16, 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 pq² would be in it for K>2.

on 01/08/08 at 11:00:44, 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.)

Title: Re: Circular jail cell revisited
Post by Eigenray on Jan 8^th, 2008, 4:33pm

on 01/08/08 at 08:13:35, 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 01/08/08 at 14:10:11, Hippo wrote:

just take products of odd number of primes.

on 01/08/08 at 14:32:44, 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?

Title: Re: Circular jail cell revisited
Post by Aryabhatta on Jan 8^th, 2008, 5:31pm

on 01/08/08 at 16:31:41, 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...

Title: Re: Circular jail cell revisited
Post by balakrishnan on Jan 8^th, 2008, 9:40pm

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)

Title: Re: Circular jail cell revisited
Post by balakrishnan on Jan 8^th, 2008, 10:55pm

[hide]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=2^m1 3^m2...p_k^mk, 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

[/hide]

Title: Re: Circular jail cell revisited
Post by Hippo on Jan 9^th, 2008, 4:19am

on 01/08/08 at 16:33:01, 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.)

Title: Re: Circular jail cell revisited
Post by Eigenray on Jan 9^th, 2008, 6:20am

on 01/09/08 at 04:19:31, 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})?

Title: Re: Circular jail cell revisited
Post by Hippo on Jan 9^th, 2008, 7:05am

on 01/09/08 at 06:20:23, Eigenray wrote:

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 ;)

Title: Re: Circular jail cell revisited
Post by Eigenray on Jan 9^th, 2008, 10:34pm

So, M and Z distribute over addition, kind of like how multiplication would...

Title: Re: Circular jail cell revisited
Post by Hippo on Jan 10^th, 2008, 12:02am

on 01/09/08 at 22:34:30, 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 :)?

Title: Re: Circular jail cell revisited
Post by Eigenray on Jan 10^th, 2008, 1:35am

That's the question ;)

Title: Re: Circular jail cell revisited
Post by Aryabhatta on Jan 11^th, 2008, 2:20pm

Not sure what you are aiming at Eigenray.

Do you mean that we can treat them as vectors over F₂ and that Z(v) is just a linear transformation? (Multiplication by a suitable matrix)?

Mutiplication would probably be the dot product :-/

Title: Re: Circular jail cell revisited
Post by Eigenray on Jan 11^th, 2008, 9:43pm

Suppose that for any set X there is a jailor who, when told to open door n, instead toggles all doors { nx : x in X }. Then there is a multiplication · on http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/scrp.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif) such that the effect jailor X has, given instructions Y, is X(Y) = X·Y.

Can you think of some way to associate an object L_X to each set, with a natural multiplication such that L_XL_Y = L_X·Y?

Title: Re: Circular jail cell revisited
Post by Aryabhatta on Jan 12^th, 2008, 2:47pm

Do you mean [hide] Dirichlet Convolution [/hide]? In that case I still don't see the significance of the letter 'Z'.

Title: Re: Circular jail cell revisited
Post by Eigenray on Jan 12^th, 2008, 4:15pm

Indeed I do. Big hint: [hide]generating function[/hide]

Title: Re: Circular jail cell revisited
Post by Aryabhatta on Jan 14^th, 2008, 11:21am

Oh, so are you talking in reference to Mⁿ({1}), in which case [hide] Bell series [/hide] seems to make a lot of sense ;)

Title: Re: Circular jail cell revisited
Post by Eigenray on Jan 15^th, 2008, 4:06am

I hadn't actually heard of those, but they can be used just as well. What I was actually going for uses a word from each of your last two suggestions...

Title: Re: Circular jail cell revisited
Post by Aryabhatta on Jan 18^th, 2008, 12:23pm

Err.. a web search for Convolution Bell revealed nothing relevant :P

Currently busy with work, will have to think about this later. Perhaps Z stands for Zeta. Only have to figure out why.

Title: Re: Circular jail cell revisited
Post by Eigenray on Feb 21^st, 2008, 7:57am

on 01/18/08 at 12:23:52, Aryabhatta wrote:

Err.. a web search for Convolution Bell revealed nothing relevant :P

Are you joking, or do you really not know which element of {Dirichlet, Bell} x {convolution, series} I mean?

As for part (BT), let A_n be the set of allowable exponents for the set S_n; i.e., n = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gifp^a_p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif S_n iff a_p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif A_n for all p. So A₀ = {0}, A₁ = {0,1}. Find the first few A_n. What's the pattern?

Title: Re: Circular jail cell revisited
Post by Aryabhatta on Jun 4^th, 2008, 10:45am

Strange! I missed your reply Eigenray...

Yes, I was joking.

I believe you have been referring to

Z(f,s) = \sum f(n) n^-s

so that

Z(f,s) Z(g,s) = Z(h,s)

where the dirichlet convolution of f and g is h.

For f = \mu we get the reciprocal of the Riemann zeta function in the half plane Re s > 1.

Title: Re: Circular jail cell revisited
Post by Eigenray on Jun 4^th, 2008, 11:59am

Correct. So if we have a set X, which corresponds to a certain Dirichlet series L_X(s) (to avoid using Z again), then what are L_Z(X) and L_M(X)?

Title: Re: Circular jail cell revisited
Post by Aryabhatta on Jun 8^th, 2008, 10:45am

One multiplies with Zeta and other divides by it, but I have the feeling that you have gone even further and obtained some nice result... (we are only interested in the evenness/oddness and not the actual values of the coefficients)

Title: Re: Circular jail cell revisited
Post by Eigenray on Jun 8^th, 2008, 11:22pm

So you understand the names now, right?

The interesting thing now is to describe the sets S_n and T_n, and the partial order on them.