 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Rational Value Validation (Posted on 2016-03-20) 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)
c((ba)d), a((bd)a), a((dc)a)
d((ab)c), d((ac)b), d((cb)a)

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:

 Search: Search body:
Forums (4)