Rearrange the digits in ⟨1263045⟩ to meet the rules below.
⟨6th 5th 4th 3rd 2nd 1st 0th⟩
✅Match
⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩
⟦1,4⟧ ∋ 0
Jump(1,5) ≥ 2
⟦3,4⟧ ∋ 2
Jump(4,6) = 2
⛔Avoid
3rd → a, 0th → b, |a-b|=5
⟨⋯ 0 ⋯ 6 ⋯ 3 ⋯⟩
#125034_v2.1
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
Step 1 │ │ │ 4 │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┤
Step 2 │ │ │ 4 │ │ │ 6 │ │
├───┼───┼───┼───┼───┼───┼───┤
Step 3 │ 3 │ │ 4 │ │ │ 6 │ │
├───┼───┼───┼───┼───┼───┼───┤
Step 4 │ 3 │ 2 │ 4 │ │ │ 6 │ │
├───┼───┼───┼───┼───┼───┼───┤
Step 5 │ 3 │ 2 │ 4 │ 5 │ │ 6 │ │
├───┼───┼───┼───┼───┼───┼───┤
Step 6 │ 3 │ 2 │ 4 │ 5 │ │ 6 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
Step 7 │ 3 │ 2 │ 4 │ 5 │ 0 │ 6 │ 1 │
└───┴───┴───┴───┴───┴───┴───┘
Proof of 2023-11-05 Q1(m=6)
═══════════════════════════
Notation: if nth -> a, then we write [nth] = a.
(1) Firstly, we consider where to put 4. We claim that it is put at the "↓" or "=" positions of ✅【⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩】.
------------------------------
For, suppose on the contrary 4 is put at the "↑" positions, i.e. 5th, 2nd or 0th. If 4 = [5th] or [2nd], then by ✅【Jump(4,6) = 2】, we have
┌───┬───┬───┬───┬───┬───┬───┐
│6th│ 5▲│4th│3rd│ 2▲│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ 4 │ │ │ 6 │ │ │
├───┼───┼───┼───┼───┼───┼───┤
│ │ 6 │ │ │ 4 │ │ │
└───┴───┴───┴───┴───┴───┴───┘
so that 6 is always put at a "↑" position of ✅【⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩】, which is a contradiction. Therefore, we need 4 = [0th] if it is put at a "↑" position. Using ✅【Jump(4,6) = 2】 then, it follows that
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│ 3▲│2nd│1st│ 0▲│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ │ │ 6 │ │ │ 4 │
└───┴───┴───┴───┴───┴───┴───┘
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ │ 3 │ 0 │ │ 5 │
└───┴───┴───┴───┴───┴───┴───┘
To match ✅【⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩】, we need [6th] > [0th] = 4. Therefore, [6th] = 5.
┌───┬───┬───┬───┬───┬───┬───┐
│ 6▲│5th│4th│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 5 │ │ │ 6 │ │ │ 4 │
└───┴───┴───┴───┴───┴───┴───┘
By ✅【Jump(1,5) ≥ 2】, we need 1 = [2nd] or [1st]. As ✅【⟦1,4⟧ ∋ 0】 implies that 1 and 4 are not adjacent, we have 1 = [2nd]. Accordingly
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│3rd│ 2▲│ 1▲│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 5 │ │ │ 6 │ 1 │ │ 4 │
├───┼───┼───┼───┼───┼───┼───┤
│ 5 │ │ │ 6 │ 1 │ 0 │ 4 │
└───┴───┴───┴───┴───┴───┴───┘
But now 0 is at a "↓" position of ✅【⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩】, which is a contradiction.
------------------------------
We have verified our claim in (1). There remain four possible positions for 4:
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
(2) │ │ / │ │ │ / │ │ / │
└───┴───┴───┴───┴───┴───┴───┘
(3) Before proceeding, we make the following observation. By ✅【⟦1,4⟧ ∋ 0】 and ✅【⟦3,4⟧ ∋ 2】, if both 1 and 3 are on the left hand side of 4, then all of 1,3,0,2 are on the left hand side of 4. Similar argument applies for the case both 1 and 3 are on the right hand side of 4.
We now claim that indeed 4 = [4th].
------------------------------
(4) If 4 = [1st], then using ✅【Jump(4,6) = 2】, ✅【⟦1,4⟧ ∋ 0】, ✅【⟦3,4⟧ ∋ 2】, and (3), we have
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│ 4▲│3rd│2nd│ 1▲│ 0▲│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ │ 6 │ │ │ 4 │ │
├───┼───┼───┼───┼───┼───┼───┤
│ - │ - │ 6 │ - │ - │ 4 │ │
├───┼───┼───┼───┼───┼───┼───┤
│ - │ - │ 6 │ - │ - │ 4 │ 5 │
└───┴───┴───┴───┴───┴───┴───┘
where the "-" indicate the positions of 1,3,0,2. But then [0th] = 5 is in a "↑" position of ✅【⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩】, which is a contradiction as 5 can only increase by using 6.
(5) Else, if 4 = [3rd], then using ✅【Jump(4,6) = 2】 and putting 6 at a "↓" position of ✅【⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩】, we have
┌───┬───┬───┬───┬───┬───┬───┐
│ 6▲│5th│4th│ 3▲│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 6 │ │ │ 4 │ │ │ │
└───┴───┴───┴───┴───┴───┴───┘
By (3), we see that ✅【⟦1,4⟧ ∋ 0】 and ✅【⟦3,4⟧ ∋ 2】 can only be satisfied using both sides of 4. Since 0 cannot be put at a "↓" position of ✅【⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩】, we have
┌───┬───┬───┬───┬───┬───┬───┐
│6th│ 5▲│ 4▲│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 6 │ 3 │ 2 │ 4 │ │ │ │
└───┴───┴───┴───┴───┴───┴───┘
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ 1 │ │ │ │ 0 │ │ 5 │
└───┴───┴───┴───┴───┴───┴───┘
But then ✅【Jump(1,5) ≥ 2】 cannot be matched.
(6) Else, if 4 = [6th], then ✅【Jump(4,6) = 2】 gives
┌───┬───┬───┬───┬───┬───┬───┐
│ 6▲│5th│4th│ 3▲│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 4 │ │ │ 6 │ │ │ │
└───┴───┴───┴───┴───┴───┴───┘
If 0 is at the left hand side of 6, then to match ✅【⟦3,4⟧ ∋ 2】 we unavoidably would match ⛔「⟨⋯ 0 ⋯ 6 ⋯ 3 ⋯⟩」. Hence, 0 is at the right hand side of 6. As ✅【⟦1,4⟧ ∋ 0】 implies that 0 is not at corners, and that 0 cannot be put at a "↓" positions of ✅【⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩】, we have 0 = [2nd].
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│3rd│ 2▲│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 4 │ │ │ 6 │ 0 │ │ │
└───┴───┴───┴───┴───┴───┴───┘
To match ✅【⟦1,4⟧ ∋ 0】 and avoid ⛔「3rd → a, 0th → b, |a-b|=5」 at the same time, we have 1 = [1st].
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│3rd│2nd│ 1▲│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 4 │ │ │ 6 │ 0 │ 1 │ │
└───┴───┴───┴───┴───┴───┴───┘
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ │ 2 │ │ 3 │ │ │ 5 │
└───┴───┴───┴───┴───┴───┴───┘
It would contradict ✅【⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩】, however, because 1 can only decrease by using 0.
------------------------------
Combining (2),(4),(5),(6), at last we get our first step that 4 = [4th]. Using ✅【Jump(4,6) = 2】 then, we have
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│ 4■│3rd│2nd│ 1■│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
Step 1 │ │ │ 4 │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┤
Step 2 │ │ │ 4 │ │ │ 6 │ │
└───┴───┴───┴───┴───┴───┴───┘
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ │ 3 │ 0 │ │ 5 │
└───┴───┴───┴───┴───┴───┴───┘
By ✅【⟦1,4⟧ ∋ 0】, ✅【⟦3,4⟧ ∋ 2】, and (3), we see that there are two cases for (a,b) := ([6th], [5th]):
(i) (a,b) = (1,0)
(ii) (a,b) = (3,2)
(7) We claim that case (i) is not possible.
------------------------------
For, if on the contrary case (i) holds, then we have
┌───┬───┬───┬───┬───┬───┬───┐
│ 6▲│ 5▲│4th│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 1 │ 0 │ 4 │ │ │ 6 │ │
└───┴───┴───┴───┴───┴───┴───┘
It would never match ✅【⟨ ⁶ᵗʰ↓ ⁵ᵗʰ↑ ⁴ᵗʰ↓ ³ʳᵈ= ²ⁿᵈ↑ ¹ˢᵗ↓ ⁰ᵗʰ↑ ⟩ after ⟨⇌⟩】, however, as 1 can only decrease by using 0.
------------------------------
We have verified our claim in (7). Consequently, we obtain
┌───┬───┬───┬───┬───┬───┬───┐
│ 6■│ 5■│4th│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ │ 4 │ │ │ 6 │ │
├───┼───┼───┼───┼───┼───┼───┤
Step 3 │ 3 │ │ 4 │ │ │ 6 │ │
├───┼───┼───┼───┼───┼───┼───┤
Step 4 │ 3 │ 2 │ 4 │ │ │ 6 │ │
└───┴───┴───┴───┴───┴───┴───┘
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ 1 │ │ │ │ 0 │ │ 5 │
└───┴───┴───┴───┴───┴───┴───┘
Now, to match ✅【Jump(1,5) ≥ 2】, we need {1,5} = {[3rd], [0th]}. But 1 cannot be adjacent to 4 by ✅【⟦1,4⟧ ∋ 0】. As a result, we reach
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│ 3■│ 2■│1st│ 0■│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 3 │ 2 │ 4 │ │ │ 6 │ │
├───┼───┼───┼───┼───┼───┼───┤
Step 5 │ 3 │ 2 │ 4 │ 5 │ │ 6 │ │
├───┼───┼───┼───┼───┼───┼───┤
Step 6 │ 3 │ 2 │ 4 │ 5 │ │ 6 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
Step 7 │ 3 │ 2 │ 4 │ 5 │ 0 │ 6 │ 1 │
└───┴───┴───┴───┴───┴───┴───┘
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┘
Q.E.D.
#125034_v2.1
No comments:
Post a Comment