Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In reference to a question on work of Westzynthius and another question relating to Jacobsthal's function, I have formed a game which I immodestly call Paseman's Ring Toss. I hope that it has been studied before, in which case I am willing to change the name to accommodate historical precedent.

The game has things I call rings, other things I call prizes, and something I call a peg. The peg is a slotted numberline, with slots to hold (parts of) rings, and the slots are placed at positive and negative integer coordinates. (The coordinate 0 contains a "peg-shaped" object and will not hold any ring.) I am only concerned with finite versions of the game at present, so bound the size of the coordinates by your favorite positive integer M, and then increase M as needed "until it feels good".

Although I am interested in variations on this game which are in the literature, in this version I have a set of rings R which has a set (not multiset, that may be handled later) of associated lengths. Since the lengths are important, I identify R with the set of lengths. Each ring thus has its own length I will call $w$, (and for each $w$ in the set there is exactly one ring). Those who chose M above may guess that the largest length will be 2M, and that R is a finite set; this is a good guess, although having M+1 as the largest length is a slightly better guess.

The rings are arranged on the peg according to the following rules: a) Each ring must be placed so as to occupy a positive (-ly numbered) slot $p$, and a negative (-ly numbered) slot $n$, such that $p-n=w$, the length of the ring. (No rings of length smaller than 2 are used.) b) all rings in R must be used. However, a slot has room for several rings, so some overlap may be allowed, and for some configurations overlap is expected.

The prizes are ... , well they are virtual. I will not be giving out any actual prizes unless some significant results are achieved, and even then the prizes might not get you more than a cup of coffee (but moderately fancy coffee at that). However, the prizes are my way of determining how good is a placement of rings.

Now to the action. You are given a set of $k$-many rings (lengths) R. If you place the $k$ rings so as to occupy $2k - d$ slots total, you get the $d$th place prize, where $d=0$ is the Grand Prize. Smaller $d$ gets you better prizes. A ring set R is a $d$-set if it wins a $d$th prize and nothing better.

There are a number of combinatorial questions to ask here, even if the set of lengths becomes a multiset. One is to ask how many ways, given R, to arrange the rings (easy); another is to ask how good a prize you can get (not so easy); another is to ask for a characterization of the 0-sets R, or sets which will get you a Grand Prize (possibly hard), and how many ways to arrange the rings in R that get the Grand Prize (likely to be hard). Similar questions can be made for $d$-sets.

There are also asymptotic and approximation questions to be asked; I am interested in something like if the lengths in R fill certain intervals, or a certain percentage of an interval, then R cannot achieve better than the $d$th prize.

I also have a variation involving a notion I call centered rings. When you start playing the game, you see it is easy to get a Grand Prize if R has only even lengths or only odd lengths, and there are simple configurations that win the prize. However, these configurations often involve multiply centered rings, where two rings are centered if their slot positions satisfy $p_1 + n_1 = p_2 + n_2$ for rings $r_1$ and $r_2$. To discourage this, I alter the scoring and add some amount to $d$ depending on the number of centered pairs of rings there are in an arrangement. However, I am happy if I get answers to MY questions for just the standard version.

Here are MY questions: has anyone seen a combinatorial object like Paseman's Ring Toss, and can they point me to a reference or two in the literature? At some point I may generate sequences and looking up things in Sloane's Integer Sequence Encyclopedia, but I am still scratching my head about which sequence to start computing.

I know this is reminiscent of Langford's problem (and I may have to study that), but the peg and the fact the R does not always have a consecutive set of lengths give this game a different character. If one knows of a Langford variant that is real close to this, I would be interested. I also don't mind suggestions on solving some of the (or even raising new) combinatorial questions related to this game.

Gerhard "Ask Me About System Design" Paseman, 2011.04.14

share|improve this question
    
So far, the closest hit seems to be generalized multi-Skolem sequences. (For example, see this paper . ) However, that darned peg gets in the way of an exact match, and overlaps do not seem to be considered. I'll keep looking. Gerhard "Ask Me About System Design" Paseman, 2011.04.14 –  Gerhard Paseman Apr 14 '11 at 22:21
    
It's not a million miles away from the topic of my paper with Poon and Simpson, Incongruent restricted disjoint covering systems, Disc Math 309 (2009) 4428-4434. Given $n$, we want a bunch of congruences with distinct moduli such that each number from $1$ to $n$ satisfies exactly one congruence, and each congruence is satisfied by at least two numbers. We prove it's impossible for each congruence to be satisfied by exactly two numbers. Shift our interval left to be symmetric wrt zero, insist zero satisfy no congruence, and I think we have an approximation to what you're asking. –  Gerry Myerson Apr 15 '11 at 2:26
    
Thank you for the reference, Gerry. It turns out I am dealing with restricted incongruent covering systems for [1...n] in the problems above. For bounding j(m) from above I look at the endpoints and see what clashes occur. I decided to map n to -1, n-1 to -2, etc, to form the game. You have a nice collection of 0-sets as a result. Now I have something more to play with. I hope to find out more about d-sets as well for my application. Gerhard "Ask Me About System Design" Paseman, 2011.04.14 –  Gerhard Paseman Apr 15 '11 at 5:37
    
By the way, I've stopped (for now) tweaking my writeup on a new upper bound for Jacobsthal's function. It's wordy, has a couple of minor errors, and needs polish, but the core result seems to hold (exponent like loglogn instead of like logn) and Will and Aaron haven't told me different yet. If you are interested, let me know and I will email you a PDF. Gerhard "Ask And You Shall Receive" Paseman, 2011.04.14 –  Gerhard Paseman Apr 15 '11 at 5:44
    
Please do. You should be able to find my email address by way of the Macquarie Math Dept website, maths.mq.edu.au –  Gerry Myerson Apr 15 '11 at 5:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.