The Algorithm Design Manual Second Edition

1.6

War Story: Psychic Modeling

The call came for me out of the blue as I sat in my office.

“Professor Skiena, I hope you can help me. I’m the President of Lotto Systems

Group Inc., and we need an algorithm for a problem arising in our latest product.”

“Sure,” I replied. After all, the dean of my engineering school is always encour-

aging our faculty to interact more with industry.

“At Lotto Systems Group, we market a program designed to improve our cus-

tomers’ psychic ability to predict winning lottery numbers

.

1

In a standard lottery,

each ticket consists of six numbers selected from, say, 1 to 44. Thus, any given

ticket has only a very small chance of winning. However, after proper training, our

clients can visualize, say, 15 numbers out of the 44 and be certain that at least four

of them will be on the winning ticket. Are you with me so far?”

“Probably not,” I replied. But then I recalled how my dean encourages us to

interact with industry.

“Our problem is this. After the psychic has narrowed the choices down to 15

numbers and is certain that at least 4 of them will be on the winning ticket, we

must find the most efficient way to exploit this information. Suppose a cash prize

is awarded whenever you pick at least three of the correct numbers on your ticket.

We need an algorithm to construct the smallest set of tickets that we must buy in

order to guarantee that we win at least one prize.”

“Assuming the psychic is correct?”

“Yes, assuming the psychic is correct. We need a program that prints out a list

of all the tickets that the psychic should buy in order to minimize their investment.

Can you help us?”

Maybe they did have psychic ability, for they had come to the right place. Iden-

tifying the best subset of tickets to buy was very much a combinatorial algorithm

1

Yes, this is a true story.

---

24

1 .

I N T R O D U C T I O N T O A L G O R I T H M D E S I G N

35

34

25

24

23

15

14

13

12

45

Figure 1.10: Covering all pairs of

{1, 2, 3, 4, 5} with tickets {1, 2, 3}, {1, 4, 5}, {2, 4, 5}, {3, 4, 5}

problem. It was going to be some type of covering problem, where each ticket we

buy was going to “cover” some of the possible 4-element subsets of the psychic’s

set. Finding the absolute smallest set of tickets to cover everything was a special

instance of the NP-complete problem set cover (discussed in Section

18.1

(page

621

)), and presumably computationally intractable.

It was indeed a special instance of set cover, completely specified by only four

numbers: the size n of the candidate set S (typically n

≈ 15), the number of slots

k for numbers on each ticket (typically k

≈ 6), the number of psychically-promised

correct numbers j from S (say j = 4), and finally, the number of matching numbers

l necessary to win a prize (say l = 3). Figure

1.10

illustrates a covering of a smaller

instance, where n = 5, j = k = 3, and l = 2.

“Although it will be hard to find the exact minimum set of tickets to buy, with

heuristics I should be able to get you pretty close to the cheapest covering ticket

set,” I told him. “Will that be good enough?”

“So long as it generates better ticket sets than my competitor’s program, that

will be fine. His system doesn’t always guarantee a win. I really appreciate your

help on this, Professor Skiena.”

“One last thing. If your program can train people to pick lottery winners, why

don’t you use it to win the lottery yourself?”

“I look forward to talking to you again real soon, Professor Skiena. Thanks for

the help.”

I hung up the phone and got back to thinking. It seemed like the perfect project

to give to a bright undergraduate. After modeling it in terms of sets and subsets,

the basic components of a solution seemed fairly straightforward:

---

1 . 6

W A R S T O R Y : P S Y C H I C M O D E L I N G

25