2 to the aleph naught 2 to the aleph naught

Mathy Stuff

Stuff That's Mathy

Workshops

Workshop #5

Problem 1 taken from Mathematical puzzles: A Connoisseur’s Collectiion, Peter Winkler. Problem 2 is taken from the 2000 William Lowell Putnam Mathematics Competition.

  1. Prove that every set A of ten distinct integers from 1 to 100 has two disjoint subsets that have the same sum.

    2. Due to lack of time in week 4, this problem was given in week 5 again.

  2. 2) C(n,m) are the combination numbers equal to the number of teams of size m you can have if the selection group of people has n members. Prove that gcd(n,m) C(n,m)/n is an integer for all integers m and n such that, m is less than or equal to n and greater than or equal to 1.

  3. Subtraction Games again. (If you were in the single group that attempted this problem last week, than you may give or re-derive the solution, and explain it to your fellow group members. They must fully understand it. Then you may move on to problem 4. If you think that there is nothing more to learn about these games than what you learned in week one, think again, and see part c.)

    Find who wins and a winning strategy for a game with pile size n for the following subtraction sets, and answer the question that follows. (IMPORTANT: remember the strategies you find for problem 4.)(If you do not remember the rules of the game, or weren’t here week one, ask me.)

    1. {2,4,7} At what pile size does the win loss pattern become periodic?

    2. {2,5,7} What is the period of the win loss pattern for this game?

    3. What is the period for an arbitrary subtraction set?

  4. Now what if you take multiple games, and play them simultaneously, in other words you have two piles and each move consists of moving in only one pile, then the other player moves. The objective is still the same, leave the other player without a valid move. For example if you can take {2,4,7} from any single pile on your turn, and the board has one pile of size 4, and the other pile of size 2, you would want to take 2 beads from the pile with size 4, and that is the only winning move.

    1. Find an optimum strategy given two piles and the subtraction set is {1,2,3}

    2. What about 3 or n piles?

    3. Do parts a) and b) for the sets {1,3,4} and then {2,5,7}

    4. What about 2 piles but the subtraction set is the positive integers? What about n piles?

    5. If you are done come and ask me about the rules to the game of Kayles and the class of Octal games.