Teaser 3022: Sporty set
From The Sunday Times, 23rd August 2020 [link]
There are 100 members of my sports club where we can play tennis, badminton, squash and table tennis (with table tennis being the least popular). Last week I reported to the secretary the numbers who participate in each of the four sports. The digits used overall in the four numbers were different and not zero.
The secretary wondered how many of the members were keen enough to play all four sports, but of course he was unable to work out that number from the four numbers I had given him. However, he used the four numbers to work out the minimum and the maximum possible numbers playing all four sports. His two answers were two-figure numbers, one being a multiple of the other.
How many played table tennis?
[teaser3022]
Frits, 
John Crabtree, and 1 other are discussing. 
Jim Randell 11:26 pm on 21 August 2020 Permalink |
If the numbers that participate in each sport are A, B, C, D (in increasing order), and the sum of these values is T.
Then the maximum size of their intersection is easily determined – it is the size of the smallest set, in this case A; (or as John points out below, if all 100 members participate in at least one of the available sports, the maximum is: floor((T – 100) / 3), if this is smaller than A).
So our maximum is: min(A, floor((T – 100) / 3).
The minimum size of the intersection is trickier to determine. But if we have a family of subsets S[i] of some universal set U, then the minimum size of the intersection is given by:
So in this case the minimum size is: max(0, T – 300).
The following Python program runs in 138ms.
Run: [ @repl.it ]
from enigma import subsets, irange, diff, nconcat, divf, div, multiset, printf # generate k increasing 2-digit numbers from the supplied (increasing) digits def generate(k, ds, ns=[]): # choose the tens digits for d10s in subsets(ds, size=k, select="C"): # choose the units digits for d1s in subsets(diff(ds, d10s), size=k, select="P"): # construct the numbers yield tuple(nconcat(z) for z in zip(d10s, d1s)) # collect solutions (size of the smallest set) ss = multiset() # choose increasing numbers of participants for each of the 4 sports for ns in generate(4, irange(1, 9)): T =sum(ns) # maximum size of intersection M = min(ns[0], divf(T - 100, 3)) # minimum size of intersection m = max(0, T - 300) # min is a 2-digit numbers if m < 10: continue # M is a multiple of m k = div(M, m) if k is None or not(k > 1): continue printf("[ns={ns}; min={m} max={M} k={k}]") ss.add(ns[0]) # output solutions for (k, v) in ss.most_common(): printf("min(ns) = {k} [{v} solutions]")Solution: 65 played table tennis.
The other three sports are represented by the numbers (70, 80, 90) + (1, 3, 4) assembled in some order.
The minimum size of the intersection is 13, and the maximum size is 65 (= 5×13).
LikeLike
Jim Randell 8:54 am on 23 August 2020 Permalink |
We don’t need to work out the actual sizes of the 3 larger sets, to calculate the sum of their sizes. We only need to know what the tens and units digits are.
So here is a faster version of my program. You can also pass a command line argument to specify if members playing zero sports are allowed (1) or not (0). It runs in 54ms.
Run: [ @repl.it ]
from enigma import irange, subsets, diff, divf, div, arg, printf # set z to: # 0 - if members playing 0 sports are not allowed # 1 - if members playing 0 sports are allowed z = arg(0, 0, int) # allowable digits digits = irange(1, 9) # choose the 10s digits for the sets for d10s in subsets(digits, size=4): t10 = sum(d10s) * 10 if t10 < 280: continue # choose the units digits for d1s in subsets(diff(digits, d10s), size=4): # size of the union of the sets T = t10 + sum(d1s) # minimum size of intersection m = T - 300 # is a 2 digit number if not(9 < m < 100): continue # choose a units digit for the smallest set for d1 in d1s: # maximum size of intersection A = 10 * d10s[0] + d1 M = (A if z else min(A, divf(T - 100, 3))) # is a multiple of m k = div(M, m) if k is None or not(k > 1): continue # output solution printf("min(ns) = {A} [min={m} max={M} k={k}; ns = {d10s} x {d1s}] [z={z}]")LikeLike
Frits 10:11 pm on 24 August 2020 Permalink |
Very nice solution.
“if t10 Don’t we already know d10s must always be equal to (6, 7, 8, 9)?
if it is (5, 7, 8, 9) then t10 = 290 and sum(d1s) <= 15 (fi 2,3,4,6)
So T <= 305 which is not acceptable.
LikeLike
Frits 12:12 pm on 25 August 2020 Permalink |
from enigma import irange, diff, div, printf # minimum A + B + C + D - 300 > 9 # so 10s digits must be (6,7,8,9) # (A + B + C + D - 100) / 3 >= 70 # which is bigger than A, so maximum M equals A # allowable digits for units digits = irange(1, 5) # d is the units digit which is not used in A, B, C and D for d in digits: # sum of A, B, C and D T = 315 - d # minimum size of intersection m = T - 300 # choose a units digit for the smallest set d1s = diff(digits, (d,)) for d1 in d1s: # maximum size of intersection (is A) M = 60 + d1 # is a multiple of m k = div(M, m) if k is None or not(k > 1): continue # output solution printf("min(ns) = {M} [min={m} max={M} k={k}; ns = (6,7,8,9) x {d1s}]")LikeLike
Jim Randell 12:51 pm on 25 August 2020 Permalink |
@Frits: It looks like your comment didn’t make it through WordPress unscathed. Usually this happens when you use < and > in a comment. WordPress sees everything in between as an HTML tag, and then doesn’t recognise it, so it throws it away. You can use < and > to make < and > appear correctly. (If you want to send me a corrected version, I’ll fix it up).
It looks like you are asking about line 9 of my code. It’s really just a quick bit of early rejection so the code doesn’t go on to evaluate cases that can’t possibly work, and the program works just as well (and not much slower) without it.
I reasoned that if (T – 300) is to be a 2-digit number, then (T – 300) > 9, so: T > 309. The maximum possible value of the units digits of the four numbers that make up T is 6+7+8+9 = 30, so the sum of the tens parts of the numbers must be more than 309 – 30 = 279, which is what that test does, and it cuts the number of cases considered drastically.
With a bit more work we can see that there is only one possible set of values for the tens digits, and we are half way towards a manual solution.
When programming a solution there is always an amount of choice on how much analysis is necessary to get a program that runs in a reasonable time. But normally if it doesn’t make much difference to the run time I let the computer do the checks.
LikeLike
Frits 6:26 pm on 25 August 2020 Permalink |
@Jim, Thanks.
I like to make use of –> which WordPress doesn’t like.
Yes, I was trying to understand line 9 of your code and wondered why you had chosen this (for me suboptimal) limit.
I still need to verify for myself that the minimum and maximum formula are indeed correct.
Is there not an easy way of allowing us to edit our own posts (as it is linked to an email address)?
Many times directly after posting I see errors/improvements.
LikeLike
Jim Randell 10:37 am on 26 August 2020 Permalink |
@Frits: Sadly WordPress doesn’t treat comments at the same level as posts. Even for logged-in users. So the only way they can be edited is by a site administrator (who can make changes to any aspect of the site).
It is the main reason I sometimes think about moving away from WordPress, but I have not yet found a suitable alternative.
At one point I had hoped that WordPress would implement some level of editing (or even just the basic courtesy of previewing a comment before it is posted), but it has become clear that they really have no interest in this.
On the upside the system does make it relatively easy to manage a site, and has remained (mostly) problem free for the last 8 years.
In the meantime, the best I can offer as site administrator is to make amendments to comments if you send me any revisions.
LikeLike
Frits 2:38 pm on 22 August 2020 Permalink |
Making use of Jim’s analysis (and Brian’s at https://brg.a2hosted.com/?page_id=7024#comment-2431) .
from enigma import SubstitutedExpression, irange # AB = table tennis # minimum played is AB + CD + EF + GH - 300 # maximum played is AB # maximum = X * minimum p = SubstitutedExpression([ "GH > EF", "EF > CD", "CD > AB", "AB % (AB + CD + EF + GH - 300) == 0", "(AB + CD + EF + GH - 300) > 10", ], verbose=0, answer="AB,CD,EF,GH", digits=irange(1, 9)) # Print answers for (_, ans) in p.solve(verbose=0): print(f"{ans} minimum={sum(ans)-300} maximum={ans[0]}") # Output: # # (65, 74, 83, 91) minimum=13 maximum=65 # (65, 73, 84, 91) minimum=13 maximum=65 # (65, 74, 81, 93) minimum=13 maximum=65 # (65, 71, 84, 93) minimum=13 maximum=65 # (65, 73, 81, 94) minimum=13 maximum=65 # (65, 71, 83, 94) minimum=13 maximum=65LikeLike
GeoffR 3:25 pm on 22 August 2020 Permalink |
@Frits: You probably don’t know, but there is a sort of convention in Brian/Jim’s groups for programmed solutions with the answer not to be published early. This helps to minimise people entering the Sunday Times Prize Draw competition if they are just looking for the answer to take part in the draw, without attempting the puzzle.
LikeLike
Frits 4:46 pm on 22 August 2020 Permalink |
@GeoffR.
Thanks. I keep that in mind.
LikeLike
John Crabtree 6:22 pm on 23 August 2020 Permalink |
The maximum is not A, but min(A, (A + B + C + D – 100) / 3)
LikeLike
Jim Randell 8:45 pm on 23 August 2020 Permalink |
@John: You are, of course, quite right. Thanks.
I originally came up with the maximum without making the assumption that every member participated in at least one sport. But then I used that assumption to determine the minimum, and I neglected to revisit the maximum.
I have provided code above that allows you to select whether participation in zero sports is allowed or not.
LikeLike
Jim Randell 10:08 pm on 26 August 2020 Permalink |
Actually, it looks like it doesn’t matter if we allow members who participate in 0 sports or not. The possible numbers presented to the secretary are the same in both cases, and so is the answer to the puzzle.
The minimum intersection size is given by: max(0, T – 300).
And we require this to be a 2 digit number.
So we must have:
And T is the sum of four 2-digit numbers, all with different non-zero digits.
The largest we can make the units digits of our four numbers is 6 + 7 + 8 + 9 = 30.
So the tens digits have to sum to at least 28, so the numbers are of the form:
In the first case the maximum value of (a + b + c + d) is (6 + 5 + 3 + 2) = 16, giving a maximum possible total of 296, so this is not feasible.
In the second case the maximum value of(a + b + c + d) is (7 + 4 + 3 + 2) = 16, giving a maximum possible total of 296, so this is not feasible.
In the third case the maximum value of(a + b + c + d) is (6 + 4 + 3 + 2) = 15, giving a maximum possible total of 305, so this is not feasible.
In the fourth case the maximum value of (a + b + c + d) is (5 + 4 + 3 + 2) = 14, giving a maximum possible total of 314, so this is feasible.
So the four numbers must be of the form: 6a, 7b, 8c, 9d
The size of the smallest set is thus: 61, 62, 63, 64, or 65.
And the smallest possible value of floor((T – 100) / 3) = floor((310 – 100) / 3) = 70.
So, in this case, the maximum intersection size is always the same as the size of the smallest set, whether we allow participants of zero sports or not.
LikeLike