Dog race tracks often employ Automatic Betting Machines (ABMs), which are some what analogous to ATM machines. An ABM is a terminal where Alice can place her own bets and scan her winning tickets. An ABM does not accept or dispense cash. Instead, an ABM only accepts and dispenses vouchers . A voucher can also be purchased from a special voucher machine for cash, but a voucher can only be converted into cash by a human teller. A voucher includes 15 hexadecimal digits, which can be read by a human or scanned by a machine that reads a bar code on the voucher. When a voucher is redeemed, the information is recorded in the voucher database and a paper receipt is printed. For security reasons, the teller must submit the paper receipt which serves as the physical record that the voucher was cashed. A voucher is valid for one year from its date of issue. However, the older that a voucher is, the more likely that it has been lost and will never be redeemed. Since vouchers are printed on cheap paper, they are often damaged to the point where they fail to scan, and they can even be dif?cult for human tellers to process manually .A list of all outstanding vouchers is kept in a database. Any human teller can read the ?rst 10 hex digits from this database for any outstanding voucher. But, for security reasons, the last ?ve hex digits are not available to a teller. If Ted the teller is given a valid voucher that doesn't scan, he must manually enter the hex digits in order to cash the voucher. Using the database, it's easy for Ted to match the ?rst 10 hex digits. However, the last ?ve hex digits must be determined from the voucher itself. Determining these last ?ve hex digits can be dif?cult, particularly if the voucher is in poor condition.

In order to help overworked tellers, Carl, a clever programmer, added a wildcard feature to the manual voucher entry routine. Using this feature, Ted (or any other teller) can enter any of the last ?ve hex digits that are readable and "*" for any unreadable digits. Carl's program will then inform Ted whether an outstanding voucher exists that matches in the digits that were entered, ignoring any position with a "*." Note that this routine does not give Ted the missing digits, but instead, it simply returns a yes or no answer .Suppose that Ted is given a voucher for which none of the last ?ve hex digits can be read.

a. Without the wildcard feature, how many guesses must Ted make, on average, in order to recover the last ?ve hex digits of this voucher?

b. Using the wildcard feature, how many guesses, on average, must Ted make to recover the last ?ve hex digits of this voucher?

c. How could Dave, a dishonest teller, exploit the wildcard feature in order to cheat the system? Hint: Dave would want to concentrate on vouchers that are nearly one year old since such vouchers are likely to have been lost. Dave would need to use the wildcard feature in order to cash such a voucher, since the voucher is not in his possession?

d. What is the risk for Dave? That is, how might Dave get caught under the current system?

e. Modify the system so that it allows tellers to securely and ef?ciently deal with vouchers that fail to scan automatically, but also makes it impossible (or at least very dif?cult) for Dave to cheat the system.?