All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Rational Value Validation (Posted on 2016-03-20) Difficulty: 3 of 5
The 97 rational numbers 49/1, 49/2, 49/3, ..., 49/97 are written on a blackboard.
Two of the above numbers X and Y are chosen and replaced by X*Y-X-Y+1.
The procedure is repeated until a single number Z(say) remains on the board.

Determine the possible values of Z.

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
cardinality of solution set | Comment 5 of 11 |
The cardinality of the solution set is obviously great, but finite.  It's a puzzle in itself as to what the cardinality of this set is, or even the maximum cardinality assuming that every way of combining these elements under the given operation that is commutative but not associative.

If there were only one element, clearly there'd be only one answer. The same holds for two elements.  For three elements there'd be 3: (ab)c, (ac)b and (cb)a.

For four, things start to get complicated. The final operation may be either between an individual element and a combinaltion of three elements, or between a combination of two and another combination of two:

a((bc)d), a((bd)c), a((dc)b)
b((ac)d), a((ad)c), a((dc)a)
c((ba)d), a((bd)a), a((dc)a)
d((ab)c), d((ac)b), d((cb)a)

(ab)(cd), (ac)(bd), (ad)(bc)

That's 15, which is also the first result from the following program which calculates the cardinality for various cardinalities of elements:

   10   dim solSetSize(97)
   20   open "ratval.txt" for output as #2
   30   solSetSize(1)=1
   40   solSetSize(2)=1
   50   solSetSize(3)=3
   60   for sz=4 to 97
   70     for subsetsz=1 to int(sz/2)
   80       howmany=combi(sz,subsetsz)
   90       if subsetsz*2=sz then howmany=howmany//2
  100       solSetSize(sz)=solSetSize(sz)+howmany*(solSetSize(subsetsz)*solSetSize(sz-subsetsz))
  110     next
  120     print #2, sz,solSetSize(sz)
  130   next  
  140   close #2
  
The list of cardinalities begins:

 4   15 
 5   105 
 6   945 
 7   10395 
 8   135135 
 9   2027025 
 10   34459425 
 11   654729075 
 12   13749310575 
 13   316234143225 
 14   7905853580625 
 15   213458046676875 
 16   6190283353629375 
 17   191898783962510625 
 18   6332659870762850625 
 19   221643095476699771875 
 20   8200794532637891559375 
 
With 97 elements the cardinality becomes

451829097726427427351626908596663108106210978719390168786458314963099723365559538953452639855709875411
4874192930907257294120188664593857092677665187721767563371717929840087890625 

a 178-digit number.

The cardinality of the solution set may be smaller than this if some final results happen to match others, but the solution set can't be larger than this.

Edited on March 21, 2016, 8:01 am
  Posted by Charlie on 2016-03-21 08:00:01

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information