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.
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 |
cardinality of solution set
