Puzzles

Differences

Differences

By Stephen Meskin

When I was a kid, I delivered a daily newspaper in Levittown, a planned community on Long Island. Part of my job was keeping track of who paid their bill. I had a small notebook with the pages divided into columns. At the top of each page I put the names of the streets; in the first column I put house numbers; I used the remaining columns for payment status. Because it was a planned community, the house numbers were perfectly sequenced, with odd numbers on one side of the street and even numbers on the other.

There was one problem: When I went to collect the weekly bills, I would go down one side of the street and up the other. So, the most efficient order for me to record house numbers was 1, 3, 5, 7, 9, 10, 8, 6, 4, 2, (for a street with 10 houses). The manager didn’t like that.

The set of numbers from the even side of the street {2, 4, 6, 8, 10} has an interesting property. The absolute value of the difference between any two distinct numbers in this set is again in this set. The set of numbers from the odd side {1, 3, 5, 7, 9} is just the opposite: The absolute value of the difference between any two distinct numbers in this set is not in this set.

Let’s give these two properties names. We’ll say that the first is a difference set,[1] which is a set with at least two positive integers that contains the absolute value of the difference of every pair of distinct integers of the set. {2, 4, 6, 8, 10, 12} is another example of a difference set. We’ll call the second a non-difference set, which is a set with at least two positive integers that does not contain the absolute value of the difference of any pair of distinct elements of the set. {1, 3, 5, 7, 9, 20} is another example of a non-difference set.

There are sets of positive integers that are neither difference sets nor non-difference sets; for example, the empty set and one-element sets. These are trivial for our purposes, so we will ignore them. However, the set {2, 4, 8, 10} contains the difference of 10 and 8 but not of 10 and 4. So it is neither a difference set nor a non-difference set. We call such sets indifferent. Thus, every set containing at least two positive integers is either: a difference set, a non-difference set, or indifferent.

Non-difference sets are nice in the sense that every non-trivial subset of a non-difference set is also a non-difference set. The subsets of difference sets are not as nice (hence more interesting).

Problem 1. Show that {2, 4, 6, 8, 10} cannot be partitioned[2] into

Two difference sets;

Two non-difference sets;

Two indifferent sets.

Problem 2.

Show that {2, 4, 6, 8, 10} can be partitioned into two sets, one of which is a difference set and one of which is a non-difference set.

Show that a) can be done in three ways.

Problem 3. Find a difference set that can be partitioned into two non-difference sets.

Problem 4. Show that no difference set can be partitioned into two difference sets.

Solutions may be emailed to cont.puzzles@gmail.com.

In order to make the solver list, your solutions must be received by Jan. 31, 2020.

Solution to Previous Puzzle—The Election

What is the probability of each contestant winning the election assuming a fair coin? It appears that a variant of this problem has appeared as a puzzle in the past. This is a variant of the gambler’s ruin problem, where unfortunately Andrea and Jeremy get the short end of the straw. Andrea and Jeremy both have a 50% chance of losing on the first flip of the coin. If they survive, their probability of winning is P. For the remaining eight contestants, they have a chance to be president regardless of the outcome of the first flip. Further, for each of these eight contestants, they have probability P of being president regardless of the first flip of the coin. This is a product of the gambler’s ruin theory, which states that when X number of players have equal bankrolls and have an equal chance of winning a bet, then each player has a 1/X chance to be the sole survivor. So as 8 contestants have a 2*P chance of winning the election (they can win if the first flip is either heads or tails), and 2 contestants have a 1*P chance of winning, this sums to 18*P. Hence Andrea and Jeremy have a 1 in 18 chance of being victorious, while the remaining 8 people vying for the presidency have a 1 in 9 chance.

Bonus: What are the odds using an unfair coin? This can be computed by further delving into random walks, or via simulation. After some computations, it turns out that Jeremy has a 20.5% chance, Ingrid 27.4%, Howard 18.3%, Grace 12.2%, Frank 8.1%, Edith 5.4%, Dan 3.6%, Courtney 2.4%, Bob 1.6%, and Andrea 0.5%.

Solvers

Steve Alpert, Robert Bartholomew, Geoff Bridges, Bob Byrne, Samantha Casanova, Bob Conger, Bill Feldman, Michael Gordy, Rui Guo, Clive Keatinge, Chi Kwok, Lincoln Financial Group Team, Philip Morse, Paul Navratil, David Promislow, Tomasz Serbinowski, John Snyder, Al Spooner, Daniel Wade.

Endnotes

[1] This definition is not the standard mathematical definition of the term “difference set.” It is only valid for this problem.

[2] The partition of a set, A, is a division of the set into two non-overlapping subsets, say B and C, such that A = B C and ∅ = B C.

Errata To Solutions To Sum Of Cubes Equals Square Of Sum

The formulas were harder to understand due to five missing inequality symbols.

  1. Problem 1, Case A, Line 1 should end: … + c2 ≥ (a + b)2 +
  2. Problem 1, Case A, Line 2 should begin: 4c2 + c2 ≥ (a + b)2 + …
  3. Problem 3, Case A, Line 1 should begin: Case A. c≥ 5: …
  4. Problem 3, Case A, Line 2 should begin: d2 ≥ (a + b + c)2 + …
  5. Problem 3, Case B, Line 1 should begin: Case B. c ≤ 4: …
print
Next article Sometimes You Don’t Have a Clue
Previous article Fancy Meeting You Here!

Related posts