A magician told his friend(X) that he will do a magic trick and gave X 3 cards with 5 distinct non-negative integers written on each card. X was asked to choose a number from each card and tell the sum of the 3 chosen numbers to him. For every possible sum X told him, he answered all the 3 chosen numbers correctly. If you sum all these possible sums, what is the minimum value it can take?
Note: The integers on a card are distinct but integers on two different cards may not be distinct.
I believe the minimum sum of sums is 1029,
which comes from 1, 2, 5, 16, 25 written on each card.
Some caveats are in order: allowing the three cards to have identical
lists is most likely the optimum arrangement (although I did not prove this).
While there is more freedom given in choosing the cards' number lists allowing
them each to be somewhat or completely different, this results in many more possible sums
than making them identical (up to 125 sums vs 35 sums), and recall that we are asked to
minimize the sum of sums.
Similarly, less information is required from the magician having only to
identify numbers from a list of 5 rather than 15, so the single list may be simpler
(having lower individual values). This is all hand waving, but I am
pretty sure correct.
Added later: I made a code that varied
three cards independently for the range of values for the 5 numbers as:
(1,2)(2,3)(4-13),(20-28) and the least sum of sums were obtained with all
cards having the same 5 numbers - the sets found here.
the code is here.
Likewise, there is no proof that there is not a lower sum of sums that I have missed.
But, if I raise the maximum value allowed on the card, things don't improve at all.
Seen below, setting the maximum to 24 allows the first solution, and 25 finds the best.
Raising far further does not find any lower sums. Raising the maximum finds more solutions,
but all have higher sum of sums.
Finally Ritesh's posted solution from yesteryear works, but as shown in a sort below, it ranks
150th, well below many others.
Below I incrementally raise the maximum number allowed on the card and optiize showing
the top 4 solutions. Max=24 allowed the first actual solution.
Max = 25 immediately following, finds the best... Raising the max finds
the same 4 best.
lord@rabbit 6500 % ert
Top is the maximum value allowed on the card.
top= 22
Num solns 0
Rank Sum(sums) Numbers on card
--------------------------------
1 0 0 0 0 0 0
2 0 0 0 0 0 0
3 0 0 0 0 0 0
4 0 0 0 0 0 0
top= 23
0
1 0 0 0 0 0 0
2 0 0 0 0 0 0
3 0 0 0 0 0 0
4 0 0 0 0 0 0
top= 24
4
1 1281 1 4 9 23 24
2 1302 1 2 16 19 24
3 1323 1 6 9 23 24
4 1344 1 2 16 21 24
top= 25
10
1 1029 1 2 5 16 25
2 1281 1 4 9 23 24
3 1302 1 2 16 19 24
4 1323 1 6 9 23 24
top= 26
24
1 1029 1 2 5 16 25
2 1134 1 2 6 19 26
3 1134 2 3 6 17 26
4 1260 1 4 8 21 26
top= 27
62
1 1029 1 2 5 16 25
2 1092 1 2 5 17 27
3 1134 1 2 6 19 26
4 1134 2 3 6 17 26
top= 28
136
1 1029 1 2 5 16 25
2 1092 1 2 5 17 27
3 1113 1 3 6 15 28
4 1134 1 2 6 19 26
top= 29
292
1 1029 1 2 5 16 25
2 1092 1 2 5 17 27
3 1113 1 3 6 15 28
4 1113 1 4 5 14 29
top= 30
552
1 1029 1 2 5 16 25
2 1092 1 2 5 17 27
3 1113 1 3 6 15 28
4 1113 1 4 5 14 29
top= 31
920
1 1029 1 2 5 16 25
2 1092 1 2 5 17 27
3 1113 1 3 6 15 28
4 1113 1 4 5 14 29
top= 32
1478
1 1029 1 2 5 16 25
2 1092 1 2 5 17 27
3 1113 1 3 6 15 28
4 1113 1 4 5 14 29
lord@rabbit 6500 %
Ranked lowest sum solutions setting
maximum value at 42.
42
Total solutiopns: 38326
Rank Sum(Sums) Numbers on card
-------------------------------
1 1029 1 2 5 16 25
2 1092 1 2 5 17 27
3 1113 1 3 6 15 28
4 1113 1 4 5 14 29
5 1134 1 2 6 19 26
6 1134 1 2 8 12 31
7 1134 2 3 6 17 26
8 1155 1 2 6 13 33
9 1155 1 2 5 14 33
10 1155 1 2 5 18 29
11 1176 1 2 8 17 28
12 1176 1 2 6 17 30
13 1176 1 2 5 14 34
14 1176 1 4 5 15 31
15 1176 1 4 6 15 30
16 1176 1 2 6 13 34
17 1197 1 2 5 15 34
18 1197 1 3 6 18 29
19 1197 1 4 6 17 29
20 1197 1 2 7 15 32
21 1197 2 3 6 18 28
22 1218 1 2 8 12 35
23 1218 1 2 6 19 30
24 1218 1 2 6 21 28
25 1218 1 2 5 19 31
26 1218 1 2 5 20 30
27 1218 2 4 7 16 29
28 1218 2 5 6 15 30
29 1239 1 2 5 15 36
30 1239 1 4 5 14 35
31 1239 1 2 5 14 37
32 1239 1 4 5 15 34
33 1239 1 4 5 16 33
34 1239 1 4 5 20 29
35 1239 1 2 8 12 36
36 1239 1 2 5 21 30
37 1239 1 4 8 13 33
38 1239 1 2 9 12 35
39 1239 1 2 6 18 32
40 1239 2 3 7 20 27
41 1239 2 3 9 13 32
42 1239 1 3 6 17 32
43 1239 1 2 7 16 33
44 1239 3 4 7 18 27
45 1260 1 4 5 20 30
46 1260 1 2 5 15 37
47 1260 1 2 6 22 29
48 1260 1 4 6 18 31
49 1260 1 3 6 19 31
50 1260 1 4 8 21 26
51 1260 1 5 6 17 31
52 1260 1 6 8 14 31
53 1260 2 3 6 15 34
54 1260 1 3 9 20 27
55 1260 1 2 8 12 37
56 1260 2 3 6 19 30
57 1260 2 3 7 14 34
58 1260 1 2 6 13 38
59 1260 1 2 5 16 36
60 1260 1 2 9 12 36
61 1260 1 2 6 20 31
62 1260 1 3 6 15 35
63 1281 1 2 5 22 31
64 1281 1 2 8 12 38
65 1281 1 4 8 13 35
66 1281 1 3 8 14 35
67 1281 1 4 9 23 24
68 1281 1 3 9 14 34
69 1281 1 5 6 19 30
70 1281 1 5 6 21 28
71 1281 1 5 8 21 26
72 1281 1 2 6 17 35
73 1281 1 2 8 23 27
74 1281 2 3 6 15 35
75 1281 1 2 5 20 33
76 1281 1 2 5 16 37
77 1281 1 2 9 12 37
78 1281 1 2 12 20 26
79 1281 2 3 7 14 35
80 1281 2 3 7 18 31
81 1281 1 2 13 18 27
82 1281 1 2 5 21 32
83 1281 2 3 9 18 29
84 1281 1 4 5 21 30
85 1281 1 2 6 13 39
86 1281 2 5 6 16 32
87 1281 2 5 7 16 31
88 1281 1 2 6 20 32
89 1302 1 4 5 14 38
90 1302 1 2 6 23 30
91 1302 1 3 6 15 37
92 1302 1 2 8 12 39
93 1302 1 4 5 16 36
94 1302 1 7 9 14 31
95 1302 1 4 5 17 35
96 1302 1 2 9 12 38
97 1302 2 3 6 16 35
98 1302 1 3 6 18 34
99 1302 1 2 9 14 36
100 1302 1 2 9 19 31
101 1302 1 4 6 15 36
102 1302 1 2 6 13 40
103 1302 1 4 6 17 34
104 1302 1 2 6 19 34
105 1302 2 3 8 16 33
106 1302 1 4 6 21 30
107 1302 1 3 10 18 30
108 1302 1 3 12 18 28
109 1302 2 4 7 19 30
110 1302 1 4 8 13 36
111 1302 1 4 8 17 32
112 1302 1 2 16 19 24
113 1302 2 5 7 18 30
114 1302 1 2 7 22 30
115 1302 3 4 7 19 29
116 1323 1 2 8 24 28
117 1323 1 5 6 18 33
118 1323 1 4 5 14 39
119 1323 1 2 5 16 39
120 1323 1 5 6 22 29
121 1323 1 2 6 21 33
122 1323 1 4 5 15 38
123 1323 1 6 9 23 24
124 1323 1 6 10 13 33
125 1323 1 2 5 15 40
126 1323 1 2 5 22 33
127 1323 1 4 5 16 37
128 1323 1 2 9 12 39
129 1323 1 2 6 13 41
130 1323 1 3 6 20 33
131 1323 1 3 6 21 32
132 1323 2 3 6 20 32
133 1323 2 3 6 21 31
134 1323 1 4 5 21 32
135 1323 1 3 6 22 31
136 1323 1 2 9 14 37
137 1323 1 3 8 14 37
138 1323 2 3 7 20 31
139 1323 2 3 7 22 29
140 1323 1 3 8 16 35
141 1323 1 2 7 15 38
142 1323 2 3 9 13 36
143 1323 1 4 6 19 33
144 1323 1 3 9 16 34
145 1323 1 2 9 19 32
146 1323 1 3 10 13 36
147 1323 1 2 10 15 35
148 1323 1 2 8 12 40
149 1323 1 2 5 17 38
150 1323 1 2 5 14 41 ***** Ritesh's solution
151 1323 1 4 11 12 35
152 1323 3 5 8 17 30
153 1323 3 6 7 16 31
154 1344 1 2 6 18 37
155 1344 1 2 5 16 40
156 1344 1 2 6 24 31
157 1344 1 2 5 22 34
The code:
program ert
implicit none
integer top,i1,i2,i3,i4,i5,j1,j2,j3,k,a(5),sss,s(35),cnt,sum,
1 k1,k2,k3,k4,gcnt,good(6,76000),duma(6)
do top=22,32
print*,'top= ',top
gcnt=0
do i1=1,top-4
a(1)=i1
do i2=i1+1,top-3
a(2)=i2
do i3=i2+1,top-2
a(3)=i3
do i4=i3+1,top-1
a(4)=i4
do 1 i5=i4+1,top
a(5)=i5
cnt=0
sum=0
do j1=1,5
do j2=j1,5
do j3=j2,5
sss=a(j1)+a(j2)+a(j3)
do k=1,cnt
if(sss.eq.s(k))go to 1
enddo
cnt=cnt+1
s(cnt)=sss
sum=sum+sss
enddo
enddo
enddo
gcnt=gcnt+1
do k=1,5
good(k,gcnt)=a(k)
enddo
good(6,gcnt)=sum
1 enddo
enddo
enddo
enddo
enddo
print*,gcnt
do k1=1,gcnt-1
do k2=k1+1,gcnt
if(good(6,k2).lt.good(6,k1))then
do k3=1,6
duma(k3)=good(k3,k2)
good(k3,k2)=good(k3,k1)
good(k3,k1)=duma(k3)
enddo
endif
enddo
enddo
do k3=1,4
print 2,k3, good(6,k3),(good(k,k3),k=1,5)
2 format(i3,2x,i4,3x,5(x,i2))
enddo
enddo
end
Edited on December 23, 2022, 8:02 pm
soln
