# Problem of the Month(November 2008)

1. Let's play a game. There are 2 spinners in front of you, A and B. Both spinners are equally divided into regions labeled with positive integers. You will repeatedly choose a spinner, spin it, and add the number indicated to your running total. If your total hits exactly T you win, otherwise you lose. Obviously, your best choice of spinner depends on how the spinners are labeled, and what your goal T is.

For example, consider the case if spinner A is labeled with 1 and 4, and spinner B is labeled with 2 and 3. If T = 1, you should choose spinner A first (and your probability of winning is 1/2 ). If T = 2, you should choose spinner B first (and your probability of winning is 1/2 ). If T = 3, you should choose spinner B first (and your probability of winning is 3/4 ). If T = 4, you should choose spinner A first (and your probability of winning is 7/8 ). Which spinner should you choose for larger T?

The spinners above yield the preference sequence ABBA.... Given a finite sequence of A's and B's, is there some way to label the spinners to give that preference sequence? What spinners use as few numbers as possible? What spinners make the sum of the numbers as small as possible? What spinners make the winning probabilities as large as possible? What if we allow A's, B's, and E's (for equal probabilities of winning either way)? What if there are 3 or more spinners?

2. We have several players, each with their own spinners equally divided into regions labeled with positive integers. For each pair of players, we know who is favored to spin the largest number. Can we design spinners with small numbers to meet these conditions?

For example, for the tournament , we want P(A>B)>½, P(A>C)>½, and P(B>C)>½. The labeling A=3, B=2, and C=1 will suffice.

For the non-transitive tournament , we want P(A>B)>½, P(B>C)>½, and P(C>A)>½. The labeling A=5/2/2, B=4/4/1, and C=3 works. Is this the smallest one?

What are the smallest labelings of the possible tournaments of 4 players? How about larger numbers of players? In particular, what is the smallest labeling of spinners for n players in a non-transitive loop?

1. Here are spinner labelings for each of the preference sequences of length 1-4 that contain one or more E's. When the labelings that minimize the sum and minimize the number of digits used differ, both are given.

preference
sequence
AB
A12
E11

preference
sequence
AB
AA13
AB1, 22
AE12
EA23
EE11

preference
sequence
AB
AAA14
AAB1, 23
AAE13
ABA1, 22
ABB1, 4
1, 1, 4
2, 3
1, 2
ABE1, 42
AEA1, 22, 2, 2, 4
AEB1, 1, 2, 32, 3
AEE12
EAA2, 3
1, 2
4
1, 4
EAB23
EAE24
EEA34
EEE11

preference
sequence
AB
AAAA15
AAAB1, 24
AAAE14
AABA1, 23
AABB1, 5
1, 1, 5
3, 4
1, 3
AABE1, 53
AAEA1, 22, 3, 3, 5
AAEB1, 1, 2, 31, 3, 3, 4
AAEE13
ABAA1, 3
1, 3
2, 5
1, 2, 3
ABAB1, 22
ABAE1, 2, 32, 2, 3
ABBA1, 4
1, 1, 4
2, 3
1, 2
ABBB1, 5
1, 1, 5
2, 3
1, 2
ABBE1, 1, 3, 5
1, 1, 1, 1, 1, 4
2, 3
1, 2
ABEA1, 32, 3
ABEB1, 42
ABEE1, 2, 41, 2, 2, 2, 4
AEAA1, 22, 2, 2, 5
AEAB1, 22, 2, 2, 4
AEAE1, 32, 4, 4, 5
AEBA1, 1, 2, 32, 3
AEBB1, 5
1, 1, 2, 5
2, 3, 3, 4
1, 2, 3
AEBE1, 1, 2, 52, 3
AEEA1, 32, 3, 3, 5
AEEB1, 42, 4, 4, 4
AEEE12
EAAA2, 3
1, 2
5
1, 5
EAAB2
1, 2
3, 4
1, 4
EAAE2, 2, 3, 4
1, 1, 2, 3
4, 5
1, 1, 4, 5
EABA23
EABB2, 5
1, 1, 2, 5
3, 4
1, 3
EABE1, 1, 2, 31, 3
EAEA25
EAEB2, 44
EAEE24
EEAA3, 4
1, 3
5
1, 5
EEAB34
EEAE35
EEEA45
EEEE11

And here are spinner labelings for each of the preference sequences of length 5 that contain no E's:

preference
sequence
AB
AAAAA16
AAAAB1, 25
AAABA1, 24
AAABB1, 6
1, 1, 3
4, 5
1, 4
AABAA1, 23
AABAB1, 22, 2, 3
AABBA1, 5
1, 1, 5
3, 4
1, 3
AABBB1, 1, 61, 3
preference
sequence
AB
ABAAA1, 32, 6
ABAAB1, 3
1, 3
2, 5
1, 2, 3
ABABA1, 22
ABABB1, 1, 31, 2
ABBAA1, 42, 3
ABBAB1, 1, 41, 2
ABBBA1, 5
1, 1, 5
2, 3
1, 2
ABBBB1, 6
1, 1, 6
2, 3
1, 2

Jeremy Galvagni and Trevor Green both showed that the spinner sequence with A = {1,4} and B = {2,3} is eventually periodic with period 8: (ABBAA BEABEBAE BEABEBAE ...) and that the probability of winning converges to 49/60.

2. Here are the possible tournaments for 3 or 4 players, and the smallest known labelings for spinners that represent them in head-to-head competitions:

TournamentSpinner Labels
A = 3
B = 2
C = 1
A = 5/2/2
B = 4/4/1
C = 3
A = 4
B = 3
C = 2
D = 1
A = 5/2/2
B = 4/4/1
C = 3
D = 1
A = 5
B = 5/2/2
C = 4/4/1
D = 3
A = 6/2/2
B = 5/5/1
C = 4
D = 3

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 11/17/08.