Le Monde puzzle [#928]

A combinatorics Le Monde mathematical puzzle:

How many distinct integers between 0 and 16 can one pick so that all positive differences are distinct?

If k is the number of distinct integers, the number of positive differences is

1+2+…+(k-1) = k(k-1)/2,

which cannot exceed 16, because it is a subset of {1,2,…,16}, meaning k cannot exceed 6 if all differences are distinct. From there, picking k integers at random makes it easy to check for the condition:

k=6
N=16
x=sort(sample(0:N,k-1))
y=outer(x[-1],x[-k],"-")
while (max(duplicated(y[!upper.tri(y)]))==1){
  x=sort(sample(0:N,k-1))
  y=outer(x[-1],x[-k],"-")}

which quickly returns for k=5

> x
[1] 0 1 7 12 15

as a solution. And is still running for k=6, meaning there is apparently no solution for k=6. (An exhaustive search shows there is indeed no solution for k=6 and N=16, while there are several for k=6 and N=17.) Now, reading the puzzle solution of Le Monde today, on September 09, I discovered that the authors proposed a sequence of length 7, (0,1,2,4,5,7,11,16), which does not work since 1-0=2-1… and proved that 8 is an impossible value by quite a convoluted argument. Did I misread again?!

In the earlier version of the R code posted today, I used

...y[lower.tri]...

which does not include the diagonal, instead of the proper

...y[!upper.tri(y)]..

a mistake that led to a wrong solution for k=6, as pointed out by Stephan.

2 Responses to “Le Monde puzzle [#928]”

  1. Even in your solution, you have 5-1 = 9-5 and 12-9 = 15-12…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s