Welcome to Gaia! ::

This site

http://lightforce.freestuff.gr/

has some interesting mathsy puzzles.

I also thought it might be fun to resurrect the puzzle topic from the old mathematics guild, so here's my question:

Are there sets of nonnegative integers, H and C, such that for every integer t there are unique integers h in H and c in C such that t=h-c?

Extra challenge problem: For H and C as above let

H={h(n): n is a positive integer}, and

C={c(n): n is a positive integer}

such that if nh(n) and p(n)>c(n)? How low can you get the degree of p? (I have an upper bound and a lower bound, and there's not much between them, but I'm not sure what the answer is.)

Yeah, its a maths puzzle sort of site.

Regarding the puzzle, here's my solution in white.

This was obviously a profoundly boring problem, so I'll just provide the non optimal solution I have. I'll describe something like an algorithm that produces the elements of H and C and then prove that it works.

So, to begin with, a description of the algorithm in question.

1. Let h1=0 and c1=0 and N=1.

2. Let

DN = {hi-cj: 1≤i≤N, 1≤j≤N}

3. Increment N, that is N:= N+1

4. Let kN be such that

|kN| = min{ |t| : t∉DN-1}

If both kN and -kN are not in DN-1, we require that kN be positive. (Though this doesn't effect the algorithm in any significant way it makes its operation completely certain).

5. Let

hN = (|kN| +kN)/2 +hN-1 +cN-1 +1, and,

cN = (|kN| -kN)/2 +hN-1 +cN-1 +1.

6. Return to step 2.

After doing this a countable number of times we let

H={hi | i is natural} and C={ci | i is natural}.

Note that the algorithm involves a countable number of steps so it is not strictly speaking an algorithm, though we can make it stop between step 5 and step 6 after as many iterations as we might like, or terminate when we have any selection of numbers that we want in the difference set. The first few entries in H and C that we generate are

H={0, 2, 4, 11...} and C={0, 1, 6, 14...}.

To prove that the algorithm works, I will prove two facts about DN which will imply the 'uniqueness' and 'covering' facts respectively. Firstly,

|DN| = N*N.

I'll show this by induction. It is true for N=1, where

D0={0},

for N=2, where

D2= {-1,0,1,2)

and for N=3, where

D3={-6,-4,-2,-1,0,1,2,3,4}.

Now, assume that it is true for N>2. It is clear that

DN+1 = DN ∪ {hN+1 - ci: 1≤i≤N} ∪ {hi - cN+1: 1≤i≤N} ∪ {kN+1}.

Now, I claim that for 1≤i≤N,

hi - cN+1 < min(DN) < kN+1 < max(DN) < hN+1 - ci,

and also that kN+1∉DN.

Therefore,

|DN+1|= N2 +2N +1= (N+1)2.

This establishes that no two pairs in H×C have the same number as their difference.

Furthermore, as kN is chosen to be minimal in absolute value, I claim that

{-N,...,N}⊆D2N+1

and this shows that for any integer, there is an N such that DN contains that integer.

Therefore, there is at least one pair of sets with the requisite properties.

My answer in white
If you choose an n:
If n is unpair: 0
If n is pair: n! / ((n/2)!)^2 / 2^n

If you look at all n: 1
This is because: if you look at the unbound process (until infinity) there will always be such a moment since this process is an example of a discrete random walk. (which is by the way, a very easy martingale)

Apologies for any lack of clarity with the question. The answers you guys have are correct.

@The_Bartner: You're using a sledge hammer to crack a walnut, but whatever floats your boat is fine by me. (ps if a whole number can be written as twice another whole number we say it is "even" and otherwise it is "odd", though your meaning was clear).

@Vorpal Neko: You're very close to using Borel-Cantelli. I find it to be a very useful theorem in probability theory, though you're no doubt already aware of it.

Some other approaches to the problem include, but are not limited to, (in white for spoiler value)

1) letting p(n) be the probability that there will be an equalisation when the absolute value of the difference between the number of heads and tails is n. We want to calculate p(1). Note that
i) p(0)=1,
ii) 0≤p(n)≤1 and
iii) p(n) = (p(n-1) + p(n+1))/2
which leaves a fairly easy recurrence relation to solve.

2) an artless meandering approach utilising the Kolmogorov 0-1 law which is too boring to write out.

3) Without loss of generality, assume that the first coin toss is a head. Let the probability that the sequence of heads and tails 'equalise' after 2n+1 further tosses and not before be a(n) for n≥0. If you have a look at Catalan Numbers and have a bit of a think (particularly about Dyck words), you'll realise that

a(n)= C(n)/(2^(2n+1))

where C(n) is the nth Catalan number. We need to calculate

A = Sum(n≥0, a(n)).

If you have a look at the generating function for the Catalan numbers at the link, you can see that A=1, though the calculation isn't too hard to do yourself in this case, so long as you have a look at A^2 and use the fact that

C(n+1)= Sum(0≤i≤n, C(i)C(n-i)).

This is the method I was alluding to with my hint.

It has the advantage of allowing you to calculate relativly easily that
to get a 50% chance for equality you need to toss the coin twice,
to get a 75% chance for equality you need to toss 10 times,
to get a 90% chance for equality you need to toss 64 times,
to get a 99% chance you need to toss 6366 times,
to get a 99.5% chance you need to toss 25466 times,
to get a 99.75% chance you need to toss 101860 times, and
to get a 99.9% chance you need to toss 636620 times.
You can see that your odds of getting an equal number of heads and tails at some time don't increase very fast at all, leading to the following question:

What is the expected number of tosses required to observe an equal number of heads and tails?

Hint: methods 1 and 3 provide good starting points to tackle this from, though of course the theory of 1d random walks gives you the answer straight up.

Rereading this it seems that you've assumed that the equality of the number of heads and tails at n is independent of the equality of the number of heads and tails at m, which is false. The conclusion is right, but the argument is suspect.

thank you! I'm so addicted to "box up." te he.