9
$\begingroup$

Add all of the missing information to complete each set below. In the end, there must be no difference between your answer and mine.

{{ 0,  1,  5,  7, 27, 35, __, 67, 77, __}, 

 { 0,  1, __, 33, __, 63, 72, __, 84, __}, 

 { 0,  1,  4, __, 24, 30, __, 40, __, __}, 

 { 0,  1,  3,  9, 27, __, __, 61, __, 81}, 

 { 0,  1, 12, 15, __, 48, 57, 65, __, 87}, 

 { 0,  1,  7, 16, __, 56, 60, 68, 70, 73}, 

 { 0,  1,  5, __, 18, __, __, 43, 59, 65}, 

 { 0,  1, __, 47, 52, 54, 62, __, 79, __}, 

 { 0,  1, __, 15, __, 36, 43, __, __, 89}}

Note: To ensure no ambiguity in filling out the blanks, each row of numbers in any solution must be in numerical order.

Cryptic Hint 1:

If you're having trouble getting started, you will need a mod to solve this. Don't forget you need to complete each set and to mind your differences.

Cryptic Hint 2:

If all looks well, it still may be the case that you are missing something. Fret not, for if you redouble your efforts, you will surely find all in the products of your labours.

$\endgroup$
  • $\begingroup$ That hint is intriguing ... $\endgroup$ – Rand al'Thor Mar 25 '17 at 1:51
7
$\begingroup$

Each set

has the property that all differences of numbers in the set, taken modulo the number of possible differences, are unique aside from the fact that all $a-a$ are zero. That is: suppose we have a list of length $n$; then there are $n^2$ differences, $n$ of them are obviously 0, and our condition is that the $n^2-n+1$ we get by throwing away all but one of the zeros are all different mod $n^2-n+1$.

On the face of it this

introduces some ambiguity when the final element is left blank: we could add any multiple of that modulus. So we add the further constraint that that element is strictly less than the modulus. (A better way of saying this is that our lists are really not of integers but of integers mod $n^2-n+1$. Then the ambiguity goes away. We might as well consider them to be sets rather than lists too, at that point.)

We get the following results.

0, 1, 5, 7, 27, 35, 44, 67, 77, 80
0, 1, 27, 33, 49, 63, 72, 74, 84, 87
0, 1, 4, 13, 24, 30, 38, 40, 45, 73
0, 1, 3, 9, 27, 49, 56, 61, 77, 81
0, 1, 12, 15, 25, 48, 57, 65, 85, 87
0, 1, 7, 16, 27, 56, 60, 68, 70, 73
0, 1, 5, 8, 18, 20, 29, 43, 59, 65
0, 1, 19, 47, 52, 54, 62, 68, 79, 88
0, 1, 11, 15, 31, 36, 43, 65, 83, 89

Perhaps these are in fact

all the possible such sets of 10 numbers mod 91, or perhaps merely all that contain 0 and 1. Note that requiring them to contain 0 and 1 is a sort of canonicalization; there are always two numbers that differ by 1 mod $m$ where $m$ is our modulus, adding a constant to all the numbers changes nothing of interest, so we are just stipulating a particular choice of that constant.

But in fact

this isn't the case; here is another: {0,1,19,22,24,32,36,65,76,85}. Here is a way to manufacture new examples from old: take a set satisfying the constraint and a number $k$ coprime to our modulus $m$, and multiply all the numbers in the set by $k$ (modulo $m$). Then, if you want to include 0 and 1, look for the adjacent pair that's guaranteed to exist and subtract. So, for instance, if we begin with {0,1,5,7,...}, double all the numbers, and do this, then we get the set I mentioned at the start of the paragraph. Of course this doesn't always yield a new example; for instance, if we multiply by 3 instead, we get our original set back unchanged. The simplest case, of course, is where $k=-1$; we replace each number $a$ with $1-a$. I've tried a few examples at random and the above is the only new one I've seen, so perhaps the original list contains all but one of the possibilities; but I have no very strong reason to expect that.

The number of such

(canonicalized) sets of length $n$, for $n>=2$, goes: 1, 2, 4, 2, 10, 0, 12. (Assuming my code isn't broken, which is never a very safe assumption.) That's curious behaviour, and it suggests that it wouldn't be very surprising if the list above (with the extra one I mentioned) were complete, in which case the sequence goes 1, 2, 4, 2, 10, 0, 12, ?, 10. This sequence doesn't appear to be in OEIS (even without the dubious last entry)!

Here is my crappy Python code. It could most certainly be made a lot faster (which would be necessary to fill in the "?" in the previous paragraph and confirm or refute the conjecture).

def isvgood(s):
  n = len(s)
  t = n*(n-1)+1
  d = set()
  for a in s:
    for b in s:
      d.add((a-b)%t)
  return len(d) == t

def complete(nums):
  n = len(nums)
  z = [-1]+nums+[n*n-n+1]
  try: i = nums.index(None)
  except: return ([nums] if isvgood(nums) else [])
  lb = z[i] + 1
  j=i+2
  while z[j] is None: j += 1
  ub = z[j] - (j-i-2)
  result = []
  for t in range(lb,ub): result.extend(complete(nums[:i] + [t] + nums[i+1:]))
  return result

The OP gave a few hints that helped point me in the right direction:

the belabouring of the word "difference", which quite quickly led to the discovery that the sequences could be completed, not in all that many ways, so as to make all the differences |a-b| different, and the reference to "mod" in the hint, which suggested considering differences modulo something.

[EDITED to add:] OP's latest edit suggests that my answer above is not considered correct, which is a little puzzling since each of the sets in the question does seem to have a unique completion which I have given. However, in view of that second hint, let me add the following.

Suppose we begin with the first set in the question and repeatedly apply the following process: double all the entries (mod 91) and then canonicalize in the usual way: find a pair with difference 1, add a constant to everything to make the pair {0,1} mod 91, represent 'em all by integers in the range 0..90, and write down in ascending order.

Then we get this sequence (with boldface indicating what was in the question):

0, 1, 5, 7, 27, 35, 44, 67, 77, 80
0, 1, 19, 22, 24, 32, 36, 65, 76, 85
0, 1, 6, 10, 23, 26, 34, 41, 53, 55
0, 1, 27, 33, 49, 63, 72, 74, 84, 87
0, 1, 4, 13, 24, 30, 38, 40, 45, 73
0, 1, 3, 9, 27, 49, 56, 61, 77, 81
0, 1, 12, 15, 25, 48, 57, 65, 85, 87
0, 1, 7, 16, 27, 56, 60, 68, 70, 73
0, 1, 37, 39, 51, 58, 66, 69, 82, 86
0, 1, 5, 8, 18, 20, 29, 43, 59, 65
0, 1, 19, 47, 52, 54, 62, 68, 79, 88
0, 1, 11, 15, 31, 36, 43, 65, 83, 89

where you will see

that there are a few extra entries besides the ones in the original question. (Doubling the last of those gives the first again.)

So perhaps the intent of the question was

to complete not only the "inner" sets (of numbers) but also the "outer" set (of sets of numbers). If so, then we are done if "complete" means "find all of the ones obtainable by starting with one of these and doubling". We may or may not be done, and it would be a small amount of work to check, if it means "find all of the ones obtainable by starting with one of these and multiplying by anything". We may or may not be done, and it would involve either a nontrivial pure mathematical research project or making my code much smarter, if it means "find all the ones there are".

The wording of the question is not explicit enough to distinguish between these, so far as I can tell. The hint of course suggests the first.

Incidentally, one place to read more about these things is

here.

$\endgroup$
  • $\begingroup$ Look at the 4th and last sequences in your list. Is there a pattern between them? $\endgroup$ – del42z Mar 28 '17 at 0:09
  • $\begingroup$ There is, indeed. I think every pair of these may be related by the "multiply by a number coprime to 91 and shift" trick, but I'm too lazy to check :-). $\endgroup$ – Gareth McCaughan Mar 28 '17 at 1:06
  • $\begingroup$ (The 4th and last of course enjoy the special-case relationship where the number is -1.) $\endgroup$ – Gareth McCaughan Mar 28 '17 at 1:06
  • $\begingroup$ The keyword Golomb ruler will be useful to anyone who wants to read up on these sets. $\endgroup$ – Peter Taylor Mar 28 '17 at 20:55
  • $\begingroup$ Not quite, though you can think of it as a 'circular'(ends attached to each other) perfect Golomb ruler. This circularity allows you to measure the 'distance' in in either 'direction'. It has been proven that there are arbitrarily large sets of numbers that fulfill the property in the answer, but the size of perfect Goiomb rulers is limited. $\endgroup$ – del42z Mar 28 '17 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.