4
$\begingroup$

In a game, your opponent is given an ordered pair of integers (X, Y), and at each step, they can either double X and add one to Y or double Y and add one to X. Here's an example sequence of steps that they could take:

(0, 1) => (1, 2) => (2, 3) => (4, 4) => (8, 5)

You want to prevent making X and Y equal. Choose X and Y for them so that they can never be equal.

$\endgroup$
2
  • 2
    $\begingroup$ @Penguin You aren't the one manipulating the numbers, your opponent is. The goal is to choose an ordered pair so that no matter how your opponent applies the given operations, they cannot make the two numbers equal $\endgroup$ – HTM Apr 2 at 3:05
  • 1
    $\begingroup$ This seems to be based on Project Euler problem 736. $\endgroup$ – Jaap Scherphuis Apr 2 at 7:33
9
$\begingroup$

(UPDATE: Looking through this proof, it looks like we don't have to have $ X, Y $ non-negative after all - they can be any integers, positive or negative)

I believe that

we cannot prevent our opponent from eventually making the two numbers equal. In particular, there always exists a sequence of steps that produces a pair of equal multiples of 4, no matter which two numbers we start with.

Note: I'm pretty sure there's a much more elegant and/or intuitive way of proving this than what I'm about to do, but hopefully this method can provide some inspiration for those looking for such a proof.

WLOG, we let $ X \leq Y. $ (We can do this because the two operations are symmetric with respect to the order of the pair: doubling the first coordinate and adding one to the second coordinate of $ (X, Y) $ is the same as doubling the second coordinate and adding one to the first coordinate of $ (Y, X), $ and vice versa.) Obviously,

if we begin with a pair of the form $ (X, X), $ then our opponent has already won.

We can also show that

there exists sequences that eventually produce a pair of equal values when we start with pairs of the form $ (X, X + 1) $ and $ (X, X + 2). $ If we start with $ (X, X + 2), $ we have the sequence $$ (X, X + 2) \to (X + 1, 2X + 4) \to (X + 2, 4X + 8) \to (2X + 4, 4X + 9) \to (2X + 5, 8X + 18) \to (4X + 10, 8X + 19) \to (8X + 20, 8X + 20). $$ (Note that $ 8X + 20 $ is a multiple of 4.) If we start with $ (X, X + 1), $ we have $$ (X, X + 1) \to (X + 1, 2X + 2) \to (X + 2, 4X + 4 \to (2X + 4, 4X + 5) \to (4X + 8, 4X + 6), $$ which reduces to the $ (X, X + 2) $ case as $ 4X + 8 = (4X + 6) + 2. $

Now, we will prove the following crucial lemma, which will allow us to provide a proof by induction of the statement:

Lemma: There exists sequences starting with pairs of the form $ (X, X + 2k) $ and $ (X, X + 2k + 1), $ where $ k $ is a positive integer, that eventually produce pairs of the form $ (X, X + k + 1). $

Essentially, what this lemma says is that if we start with a pair of numbers whose difference is some value greater than 2, then we can eventually get to a pair of numbers whose difference is smaller than the difference we originally started with. We can then apply this lemma several times until we reach the $ (X, X + 2) $ case. (We'll formalize this a bit later when we get to the actual induction proof.)

Proof of this lemma:

To simplify the explanation a bit, we let $ f(x, y) = (2x, y + 1) $ ("double X and add one to Y") and $ g(x, y) = (x + 1, 2y) $ ("double Y and add one to X"). We let $ k $ be a positive integer, and we'll start by finding a sequence that takes us from $ (X, X + 2k + 1) $ to $ (N, N + k + 1) $ for some integer $ N $:

1. Apply $ g $ $ 2k + 1 $ times: $$ (X, X + 2k + 1) \to (X + 2k + 1, 2^{2k + 1}(X + 2k + 1)). $$ 2. Let $ A = X + 2k + 1 $ and apply $ f $ $ 2k $ times: $$ (X + 2k + 1, 2^{2k + 1}(X + 2k + 1)) = (A, 2^{2k + 1}A) \to (2^{2k}A, 2^{2k + 1}A + 2k) $$ 3. Let $ B = 2^{2k}A $ and apply $ g $ $ k $ times: $$ (2^{2k}A, 2^{2k + 1}A + 2k) = (B, 2B + 2k) \to (B + k, 2^{k + 1}(B + k)) $$ 4. Apply $ f $ $ k + 1 $ times and let $ N = 2^{k + 1}(B + k) $: $$ (B + k, 2^{k + 1}(B + k)) \to (2^{k + 1}(B + k), 2^{k + 1}(B + k) + k + 1) = (N, N + k + 1) $$
Since $ N $ is composed of the sums and products of integers, it is itself an integer as well, as desired.

Now, the proof for the $ (X, X + 2k) $ case is a little trickier. For this, we will show that there exists a sequence from $ (X, X + 2k) $ to $ (N, N + 4k + 1) $ instead of directly to $ (N, N + k + 1) $ - since $ 4k + 1 = 2(2k) + 1, $ we could then find a sequence going from $ (N, N + 4k + 1) \to (M, M + 2k + 1) \to (P, P + k + 1) $ by our previous result, thus establishing the reduction:

1. Apply $ g $ $ 2k $ times: $$ (X, X + 2k) \to (X + 2k, 2^{2k}(X + 2k)) $$ 2. Let $ A = X + 2k $ and apply $ f $ $ 2k - 1 $ times: $$ (X + 2k, 2^{2k}(X + 2k)) = (A, 2^{2k}A) \to (2^{2k - 1}A, 2^{2k}A + 2k - 1) $$ 3. Let $ B = 2^{2k - 1}A $ and apply $ f $ twice: $$ (2^{2k - 1}A, 2^{2k}A + 2k - 1) = (B, 2B + 2k - 1) \to (4B, 2B + 2k + 1) $$ 4. Apply $ g $ once and let $ N = 4B + 1 $: $$ (4B, 2B + 2k + 1) \to (4B + 1, 4B + 4k + 2) = (N, N + 4k + 1) $$
Again, since $ N $ is derived from the sums and products of integers, it is also an integer. Thus, we have shown that starting from either $ (X, X + 2k + 1) $ or $ (X, X + 2k), $ we can eventually reach $ (N, N + k + 1) $ for some integer $ N. $

For concreteness, I'll demonstrate a couple of possible sequences using this lemma:

For $ (3, 12), $ we have $ X = 3, k = (12 - 3 - 1)/2 = 4, $ so the sequence would go: $$ (3, 12) \to (12, 2^9 \cdot 12) \to (2^8 \cdot 12, 2^9 \cdot 12 + 8) \to (2^8 \cdot 12 + 4, 2^4 (2^9 \cdot 12 + 8)) \to (2^5(2^8 \cdot 12 + 4), 2^4(2^9 \cdot 12 + 8) + 5), $$ and the difference between these two values is $(2^4 \cdot 8 + 5) - (2^5 \cdot 4) = 5 = k + 1. $

For $ (6, 10), $ we have $ X = 6, k = (10 - 6)/2 = 2, $ so the sequence would go: $$ (6, 10) \to (10, 2^4 \cdot 10) \to (2^3 \cdot 10, 2^4 \cdot 10 + 3) \to (2^5 \cdot 10, 2^4 \cdot 8 + 5) \to (2^5 \cdot 10 + 1, 2(2^4 \cdot 10 + 5)), $$ and the difference between the two values is $ (2 \cdot 5) - 1 = 9 = 4(2) + 1 = 4k + 1. $ We can then apply the lemma procedure two more times until we get a pair of values whose difference is $ k + 1 = 3. $

(Obviously, these aren't the most efficient ways of getting to a pair of equal values, but we don't have to find them for this problem, so it is enough to show that there exists at least one way of getting there.)

Having proven our lemma, the induction comes pretty immediately:

Let $ P(n) $ be the statement: "There exists sequences starting with pairs of the form $ (X, X + n) $ that eventually produce a pair of equal values." We will prove $ P(n) $ is true for all non-negative $ n $ by strong induction. We have already proven our base cases of $ P(0), P(1), $ and $ P(2), $ so now let's assume that the statement is true for all non-negative integers $ n \leq k, $ where $ k \geq 2. $ We will show that the statement is true for $ n = k + 1 $ as well. Notice that there exists $ m \geq 1 $ such that either $ k = 2m $ or $ k = 2m + 1. $ Thus, by our lemma, $ P(k) $ is equivalent to $ P(m + 1), $ and since $ m + 1 \leq k, $ we know that $ P(m + 1) $ is true by our inductive hypothesis. This completes the inductive step, so we conclude that for all non-negative $ n, $ given any integer $ X, $ there exists a sequence starting from $ (X, X + n) $ that eventually produces a pair of equal values.

This is equivalent to saying that all pairs $ (X, Y) $ will eventually lead to a pair of equal values (more specifically, we will always reach a pair of equal multiples of 4 with this method, since we must arrive at a pair of the form $ (X, X + 2) $), so there is no way we can prevent our opponent from winning this game.

$\endgroup$
1
3
$\begingroup$

Maybe I am missing something here but it seems like there are any number of solutions like

1 and pi for example. Adding 1 or doubling will never make the irrational rational?

$\endgroup$
2
  • 1
    $\begingroup$ The original formulation of the question required that X and Y be positive integers, but that requirement was removed in an edit, so we'd have to ask the OP to clarify $\endgroup$ – HTM Apr 2 at 4:34
  • $\begingroup$ It is supposed to be an integer. $\endgroup$ – shril Apr 2 at 8:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.