18
1
Can Alice win the game?
The game's rules are as follows. First, a finite non empty set of positive integers \$X\$ is defined. Then, Alice and Bob take turns choosing positive integers, with Alice going first. Each integer must be strictly less than the previous one, and the game ends when one of the players chooses \$1\$.
Alice wins if the numbers she and Bob chose sum to a number in \$X\$, otherwise Bob wins.
Example games
Define \$X=\{20, 47\}\$. Alice chooses \$19\$, Bob chooses \$2\$, Alice chooses \$1\$. We have \$19+2+1=22\$ which is not in \$X\$ so Bob wins.
Define \$X=\{5, 6, 7, 8\}\$. Alice chooses \$4\$, Bob chooses \$3\$, Alice chooses \$1\$. We have \$4+3+1=8\$ which is in \$X\$ so Alice wins.
Challenge
Your challenge is to write a program or function without standard loopholes which, when given a collection of positive integers \$X\$, will output or produce some consistent value if Alice has a winning strategy, and a different consistent value if Alice does not have a winning strategy.
A winning strategy is a strategy which will let Alice win no matter how Bob plays.
Note that in the first example game Alice did not have a winning strategy: If her first choice was any number other than \$19\$ or \$46\$ then Bob could choose \$1\$ and win. On the other hand if her first choice was \$19\$ or \$46\$ then Bob could choose \$2\$ and win.
In the second example, Alice did have a winning strategy: After choosing \$4\$, she could choose \$1\$ after any of Bob's possible choices and win (or Bob could choose \$1\$ and she would win immediately).
Input and output
The input will be a collection of positive integers in ascending order, in any convenient format, given with any convenient input method. This collection represents the set \$X\$. The output will be one of two distinct values chosen by you, depending on whether or not Alice has a winning strategy with the given collection. Example IO:
Input -> Possible Output
20 47 -> false
5 6 7 8 -> true
5 6 7 10 -> true (Alice chooses 4. If Bob chooses 3, Alice chooses 2; otherwise she chooses 1.)
5 6 7 11 -> false (A chooses n>6, B chooses n-1. A chooses 6 or 5, B chooses 2. A chooses 4, B chooses 3. A chooses n<4, B chooses 1.)
Rules
- No standard loopholes
- Shortest code in bytes wins
Note
This was the result of trying to make a finite version of the Banach Game.
Can we assume that X will be in ascending/descending order? – frank – 2019-11-29T18:52:22.647
1@frank Good question. Yes, you may assume it will be in ascending order. – 79037662 – 2019-11-29T19:12:13.823
How should we handle 1 being in X? – frank – 2019-11-29T19:42:10.033
@frank It is valid, and Alice can obviously win by choosing 1. – 79037662 – 2019-11-29T19:42:40.280