Le Monde puzzle [#809]

Another number theory puzzle, completed in the plane to Hamburg:

Integers n are called noble if they can be decomposed as a sum n=a+b+… of distinct integers such that 1/a+1/b+…=1. They are called bourgeois if they are not noble but can be decomposed as a sum n=a+b+… of integers, some of them identical, such that 1/a+1/b+…=1. If neither noble nor bourgeois, they are called villeins. Find all nobles less than 60. And characterise villeins.

Again a case where writing a brute-force R code seems harder than solving the problem on a piece of paper… However, a mix could make the best of both worlds. It is rather straightforward to see that if n is not a villein, then 2n+2 is not a villein (moving from 1/2+1/2=1 to 1/2(1/n)+1/2=1). Similarly for 3n+6 (9=3+3+3), 4n+6 (10=4+4+2), 6n+5 (2+3+6=11). Each new decomposition brings a whole series of non-villeins. Another path is to remark that products keep the property: if a and b are non-villeins, so is ab, a², b², 2(a+b), and actually all products of the form m(m+a-1) for any integer m.  Starting with the most basic solutions (1,4,9,10,11), we can then repeat the application of all those rules until no new non-villein is exposed.

Here is my R code for finding some decompositions with 4 and 5 terms (since there are only one or two decompositions with one (1), two (2+2) and three (2+3+6, 3+3+3): I first define a function checking for a decomposition with no numerical error [(sum(1/deco)==1) does not work!]:

inva=function(deco){
  numerat=0
  for (i in 1:length(deco))
    numerat=numerat+prod(deco[-i])
  return((numerat==prod(deco)))}

then check for 4

reve4=NULL
a=c(2,2,2,2)
while ((a[1]<5)&&(sum(a)<626)){
 while ((sum(1/a[-4])>=1)&&(sum(a)<626))
 a[3:4]=rep(a[3]+1,2)
 a[4]=max(a[3],trunc(1/(1-sum(1/a[-4])))-1)
 while ((sum(1/a)>1)&&(sum(a)<626)) a[4]=a[4]+1
 if (inva(a)) reve4=rbind(reve4,a)
 if ((sum(1/a[-4])+1/a[3]>1)&&(sum(a)<625)){
  a[3:4]=rep(a[3]+1,2)}else{
  b=rep(a[2]+1,3)
  if (a[1]+sum(b)<625){
   a=c(a[1],b)}else{a=rep(a[1]+1,4)
   }}
 }

and 5 term decompositions:

reve5=NULL
a=rep(2,5)
while ((a[1]<5)&&(sum(a)<626)){
 while ((sum(1/a[-5])>=1)&&(sum(a)<626)) a[4:5]=rep(a[4]+1,2)
 a[5]=max(a[4],trunc(1/(1-sum(1/a[-5])))-1)
 while ((sum(1/a)>1)&&(sum(a)<626)) a[5]=a[5]+1
  if (inva(a)) reve5=rbind(a,reve5)
  if ((sum(1/a[-5])+1/a[4]>1)&&(sum(a)<624)){
   a[4:5]=rep(a[4]+1,2)}else{
   b=rep(a[3]+1,3)
   if (sum(a[1:2])+sum(b)<625){a=c(a[1:2],b)}else{
    b=rep(a[2]+1,4)
    if (a[1]+sum(b)<625){a=c(a[1],b)}else{
       a=rep(a[1]+1,5)
   }}}
}

From there, we have a basis on which we can fill a 25×25 table of further non-villeins, applying the above rules:

nob=rep(0,25^2)
nob[c(1,4,9,10,11,16,24)]=1
nob[apply(reve4,1,sum)]=1
nob[apply(reve5,1,sum)]=1
ref=1
newref=sum(nob)
while (newref>ref){
 for (i in (1:25^2)[nob==1]){
 if (i<26) nob[i^2]=1
 if (2*i+2<625) nob[2*i+2]=1
 if (2*i+9<626) nob[2*i+9]=1
 if (3*i+6<626) nob[3*i+6]=1
 if (4*i+6<626) nob[4*i+6]=1
 if (6*i+5<626) nob[6*i+5]=1
 for (m in 2:25)
   if (m*(m+i-1)<626) nob[m*(m+i-1)]=1}
 ref=newref;newref=sum(nob)
 image(1:25,1:25,matrix(nob,25))}

This produces two false villeins, namely 47 and 103, since all numbers larger than 24 are non-villeins: Since both 47 and 103 are prime numbers, using other product rules would not change anything to the result. An extra R code looking at all possible decompositions of those numbers into sums would show them as false villeins. Or moving to 6 term decompositions since 47 = 3+4+8+8+12+12. Here is a small random search:

a=c(3,rep(2,23))
N=47
while (!inva(a)){
  b=sample(2:N,1)
  a0=c(b,N-sum(b))
  while (sum(1/a0)<1){
    b=sample(2:(N-sum(a0[-length(a0)])),1)
    a0=c(a0[-length(a0)],b)
    a0=c(a0,N-sum(a0))}
  a=a0}

which returns 47 =4+6+20+6+5. And 103=40+35+8+14+2+4

Interesting features of this problem are that (a) it appears fairly frequently in the mathematical games literature, like the Olympiads, see e.g. this resolution incl. the proof about 24 as the upper limit to the existence of villeins, (b) the name of those integers varies from case to case, like good integers, and (c) the denomination of noble integers is used in mathematics for “irrational numbers having a continued fraction representation that becomes an infinite sequence of 1s at some point“. (There was also a very similar question on stack exchange a few weeks ago but I cannot trace it…)

3 Responses to “Le Monde puzzle [#809]”

  1. The solution published in Le Monde of yesterday evening was disappointing, with no higher mathematical principle or notion than the enumeration by the rule 2n+2, 3n+6, &tc. No novelty when compared with this earlier resolution.

  2. Jean Louis FOULLEY Says:

    Christian/Thanks a lot for reminding us the good old days we were struggling with a couple of colleagues at inra and elsewhere with “Le Monde” logic games.

    Here is the simple way I found to generate noble integers < or = to 60.

    Start with 1/2 + 1/2 =1
    Now use the equality 1/m=[1/(m+1)]+[1/m(m+1)] and apply it to 1/2
    You get 1/2 + 1/3 + 1/6 =1 and n=2+3+6=11

    In 1/2 + 1/3 + 1/6 replace 1/3 by 1/4 + 1/12 so that you get 1/2 + 1/4 + 1/6 +1/12 =1
    and n=2+4+6+12=24

    In 1/2 + 1/3 + 1/6 replace 1/6 by 1/7 + 1/42 so that you get 1/2 + 1/3 + 1/7 +1/42 =1
    and n=2+3+7+42=54

    In 1/2 + 1/4 + 1/6 +1/12 replace 1/4 by 1/5 by 1/20 so that you get 1/2 + 1/5 + 1/6 +1/12 + 1/20=1
    and n=2+5+6+12+20=45

    But, I do not know if this is an exhaustive list of these numbers.

    JL Foulley

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

Follow

Get every new post delivered to your Inbox.

Join 598 other followers