[Math] 'Two parks' problem and inclusion–exclusion principle using boolean operations

(The following text has been copypasted to the Math Recipes book.)

The problem from the "Discrete Structures, Logic and Computability" book by James L. Hein, 4th ed.

Suppose a survey revealed that 70% of the population visited
an amusement park and 80% visited a national park.
At least what percentage of the population visited both?

The problem is supposed to be solved using finite sets counting and inclusion–exclusion principle... But I'm slothful student and would try simple bruteforce.

Each 1 bit in a variable would reflect 10% of population. Then I enumerate all possible pairs. I check only those pairs, where there are 7 bits in p1 variable and 8 bits in p2 variable.

#!/usr/bin/env python3

_min=10
_max=0

def popcnt(x):
    # https://stackoverflow.com/questions/9829578/fast-way-of-counting-non-zero-bits-in-positive-integer
    return bin(x).count("1")

for p1 in range(2**10): # from 0b0000000000 to 0b1111111111
    if popcnt(p1)!=7:
        continue
    for p2 in range(2**10): # from 0b0000000000 to 0b1111111111
        if popcnt(p2)!=8:
            continue
        # at this point, p1 can take all possible values where sum of bits == 7
        # ... p2 == 8
        x=popcnt (p1 & p2)
        # write down min/max values of x:
        _min=min(_min, x)
        _max=max(_max, x)

print ("min:", _min)
print ("max:", _max)

The result:

min: 5
max: 7

You see, the minimum possible value is 5 (50%), the maximum is 7 (70%). Let's add some debug info:

...
        if x==5 or x==7:
            print ("-")
            print ("park1 {0:010b}".format(p1), "(%d)" % popcnt(p1))
            print ("park2 {0:010b}".format(p2), "(%d)" % popcnt(p2))
            print ("both  {0:010b}".format(p1 & p2), "(%d)" % popcnt(p1 & p2))
...

If maximum:

park1 0001111111 (7)
park2 0011111111 (8)
both  0001111111 (7)

If minimum:

park1 0001111111 (7)
park2 1111111100 (8)
both  0001111100 (5)

I've found such a cases, where "ones" are allocated in such a way, so that the AND of "ones" in "both" would be minimal/maximal.

Observing this, we can deduce the general formula: maximal "both" = min(park1, park2)

What about minimal "both"? We can see that "ones" from park1 must "shift out" or "hide in" to a corresponding empty space of park2. So, minimal both = park2 - (100% - park1)

Variations of the problem from the same book:

Suppose that 100 senators voted on three separate senate bills as follows:
70 percent of the senators voted for the first bill, 65 percent voted for the second bill,
and 60 percent voted for the third bill. At least what percentage of the senators voted for all three bills?
Suppose that 25 people attended a conference with three sessions, where 15 people attended the first session,
18 the second session, and 12 the third session. At least how many people attended all three sessions?
Also, The Abstract Algebra book by I.N. Herstein has exercises like:
19. In his book A Tangled Tale, Lewis Carroll proposed the following riddle
about a group of disabled veterans: "Say that 70% have lost an eye, 75%
an ear, 80% an arm, 85% a leg. What percentage, at least, must have lost
all four?" Solve Lewis Carroll's problem.


List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.