Rearrange the digits in ⟨1263045⟩ to meet the rules below.
⟨6th 5th 4th 3rd 2nd 1st 0th⟩
✅Match
⟨ ⁵ᵗʰd ³ʳᵈa ¹ˢᵗc ⁰ᵗʰb ⟩, a > b > c > d
⟨? ⋯ 1 ⋯ (?−2) ⋯⟩ (?≠3)
⟦0,4⟧ ∋ 3
⟨⋯ 1 ⋯ 2 ⋯ 3 ⋯⟩
⛔Avoid
⟨? ⋯ 1 (?−6) ⋯ 0 ⋯⟩
0 ∾ 3 ∾ 6
⟨⋯ Perm(0,6) ⋯⟩
----- Information -----
🔲 「⟨ ⁵ᵗʰd ³ʳᵈa ¹ˢᵗc ⁰ᵗʰb ⟩, a > b > c > d」
210 permutations match this pattern.
Examples: ⟨5016234⟩, ⟨3026415⟩, ⟨6024513⟩.
🔲 「⟨? ⋯ 1 ⋯ (?−2) ⋯⟩ (?≠3)」
?, 1, (?−2) are three different numbers.
1440 permutations match this pattern.
Examples: ⟨4035162⟩, ⟨4503126⟩, ⟨5130642⟩.
🔲 「⟦0,4⟧ ∋ 3」
The closed interval given by 0 and 4 contains 3.
1680 permutations match this pattern.
Examples: ⟨6013254⟩, ⟨6013542⟩, ⟨4361205⟩.
🔲 「⟨⋯ 1 ⋯ 2 ⋯ 3 ⋯⟩」
840 permutations match this pattern.
Examples: ⟨4126305⟩, ⟨1462035⟩, ⟨4015623⟩.
🔳 「⟨? ⋯ 1 (?−6) ⋯ 0 ⋯⟩」
?, 1, (?−6) are three different numbers.
120 permutations match this pattern.
Examples: ⟨6254103⟩, ⟨6253410⟩, ⟨6510324⟩.
🔳 「0 ∾ 3 ∾ 6」
0,3,6 are in the same cycle.
A permutation can be decomposed into cycles. For example, ⟨125034⟩ has two cycles: (135) and (420), as (1st→3, 3rd→5, 5th→1) and (4th→2, 2nd→0, 0th→4).
1680 permutations match this pattern.
Examples: ⟨3125604⟩, ⟨2051463⟩, ⟨5432061⟩.
🔳 「⟨⋯ Perm(0,6) ⋯⟩」
0,6 are adjacent.
1440 permutations match this pattern.
Examples: ⟨2351064⟩, ⟨5241063⟩, ⟨4135260⟩.
#125034_v2.3
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│3rd│2nd│1st│0th│▒
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡▒
Step 1 │ │ │ │ │ │ 3 │ │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 2 │ │ │ │ │ │ 3 │ 4 │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 3 │ │ 1 │ │ │ │ 3 │ 4 │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 4 │ 6 │ 1 │ │ │ │ 3 │ 4 │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 5 │ 6 │ 1 │ │ 5 │ │ 3 │ 4 │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 6 │ 6 │ 1 │ │ 5 │ 0 │ 3 │ 4 │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 7 │ 6 │ 1 │ 2 │ 5 │ 0 │ 3 │ 4 │▒
└───┴───┴───┴───┴───┴───┴───┘▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
Proof of 2024-02-13 Q1(m=6)
═══════════════════════════
Notation: if nth -> a, then we write [nth] = a.
We begin with considering where to place 3. By ✅「⟨⋯ 1 ⋯ 2 ⋯ 3 ⋯⟩」, there are at least 2 digits at the left of it, and by ✅「⟦0,4⟧ ∋ 3」, it is not in the right corner. Therefore, the possible positions are:
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│*4 │*3 │*2 │*1 │0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ │ ▬ │ ▬ │ ▬ │ ▬ │ │
└───┴───┴───┴───┴───┴───┴───┘
(1) We claim that 3 = [1st] actually.
------------------------------
(1.1) If 3 = [4th], then by ✅「⟨⋯ 1 ⋯ 2 ⋯ 3 ⋯⟩」 we have:
┌───┬───┬───┬───┬───┬───┬───┐
│ 6▲│ 5▲│ 4▲│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 1 │ 2 │ 3 │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┘
Observe that ✅「⟨? ⋯ 1 ⋯ (?−2) ⋯⟩ (?≠3)」 implies 1 != [6th]. Hence, the above is a contradiction.
(1.2) Else if 3 = [3rd], then to match ✅「⟨ ⁵ᵗʰd ³ʳᵈa ¹ˢᵗc ⁰ᵗʰb ⟩, a > b > c > d」, we need
┌───┬───┬───┬───┬───┬───┬───┐
│6th│ 5▲│4th│ 3▲│2nd│ 1▲│ 0▲│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ 0 │ │ 3 │ │ 1 │ 2 │
└───┴───┴───┴───┴───┴───┴───┘
Then, to match ✅「⟨? ⋯ 1 ⋯ (?−2) ⋯⟩ (?≠3)」 we need [6th] = 4:
┌───┬───┬───┬───┬───┬───┬───┐
│ 6▲│5th│4th│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 4 │ 0 │ │ 3 │ │ 1 │ 2 │
└───┴───┴───┴───┴───┴───┴───┘
But then we could not match ✅「⟦0,4⟧ ∋ 3」.
(1.3) Else, suppose 3 = [2nd]:
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│3rd│ 2▲│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ │ │ │ 3 │ │ │
└───┴───┴───┴───┴───┴───┴───┘
By ✅「⟦0,4⟧ ∋ 3」, one of the following holds:
(i) ⟨⋯ 0 ⋯ 3 ⋯ 4 ⋯⟩
(ii) ⟨⋯ 4 ⋯ 3 ⋯ 0 ⋯⟩
In view of ✅「⟨ ⁵ᵗʰd ³ʳᵈa ¹ˢᵗc ⁰ᵗʰb ⟩, a > b > c > d」, we cannot place 0 at 1st or 0th. Therefore, case (i) holds and 4 = [1st] | [0th]. The same pattern then implies that
4 <= max{ [1st], [0th] } < [3rd].
We now consider how to place 2. The above indicates that [3rd] != 2. By ✅「⟨⋯ 1 ⋯ 2 ⋯ 3 ⋯⟩」, it is at the left of 3, and 1 is at the left of it. There are only two possible positions:
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│3rd│ 2▲│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ * │ * │ │ 3 │ │ │
└───┴───┴───┴───┴───┴───┴───┘
To match both ✅「⟨⋯ 1 ⋯ 2 ⋯ 3 ⋯⟩」 and ✅「⟨? ⋯ 1 ⋯ (?−2) ⋯⟩ (?≠3)」, we cannot have [5th] = 2. So, [4th] = 2. It then follows from these two patterns that [5th] = 1:
┌───┬───┬───┬───┬───┬───┬───┐
│6th│ 5▲│ 4▲│3rd│ 2▲│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ │ 2 │ │ 3 │ │ │
├───┼───┼───┼───┼───┼───┼───┤
│ │ 1 │ 2 │ │ 3 │ │ │
└───┴───┴───┴───┴───┴───┴───┘
However, it results in a contradiction wherever 0 is placed:
● If 0 = [6th], then we could not match ✅「⟨? ⋯ 1 ⋯ (?−2) ⋯⟩ (?≠3)」;
● Else if 0 = [3rd] | [1st] | [0th], then we could not match ✅「⟨ ⁵ᵗʰd ³ʳᵈa ¹ˢᵗc ⁰ᵗʰb ⟩, a > b > c > d」.
------------------------------
Using (1.1), (1.2), and (1.3), our claim in (1) is verified. Accordingly, we have
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│3rd│2nd│ 1■│0th│▒
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡▒
Step 1 │ │ │ │ │ │ 3 │ │▒
└───┴───┴───┴───┴───┴───┴───┘▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 6 │ │ 0 │ 4 │ 5 │
└───┴───┴───┴───┴───┴───┴───┘
Here, to match ✅「⟦0,4⟧ ∋ 3」, in view of ✅「⟨ ⁵ᵗʰd ³ʳᵈa ¹ˢᵗc ⁰ᵗʰb ⟩, a > b > c > d」, we need 4 = [0th]:
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│4th│3rd│2nd│1st│ 0■│▒
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡▒
│ │ │ │ │ │ 3 │ │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 2 │ │ │ │ │ │ 3 │ 4 │▒
└───┴───┴───┴───┴───┴───┴───┘▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 6 │ │ 0 │ │ 5 │
└───┴───┴───┴───┴───┴───┴───┘
We continue by considering where to place 1.
● We have 1 != [6th] by ✅「⟨? ⋯ 1 ⋯ (?−2) ⋯⟩ (?≠3)」.
● We have 1 != [3rd] by ✅「⟨ ⁵ᵗʰd ³ʳᵈa ¹ˢᵗc ⁰ᵗʰb ⟩, a > b > c > d」.
● We have 1 != [2nd] by ✅「⟨⋯ 1 ⋯ 2 ⋯ 3 ⋯⟩」.
Therefore, 1 = [5th] | [4th] :
┌───┬───┬───┬───┬───┬───┬───┐
│6th│*5 │*4 │3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ ▬ │ ▬ │ │ │ 3 │ 4 │
└───┴───┴───┴───┴───┴───┴───┘
(2) We show that 1 = [5th] indeed.
------------------------------
If on the contrary 1 = [4th], then to match ✅「⟨⋯ 1 ⋯ 2 ⋯ 3 ⋯⟩」, in view of ✅「⟨ ⁵ᵗʰd ³ʳᵈa ¹ˢᵗc ⁰ᵗʰb ⟩, a > b > c > d」, we have 2 = [2nd]:
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│ 4▲│3rd│ 2▲│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ │ 1 │ │ │ 3 │ 4 │
├───┼───┼───┼───┼───┼───┼───┤
│ │ │ 1 │ │ 2 │ 3 │ 4 │
└───┴───┴───┴───┴───┴───┴───┘
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ │ │ 6 │ │ 0 │ │ 5 │
└───┴───┴───┴───┴───┴───┴───┘
Then, we have to place 0 at 5th in view of ✅「⟨ ⁵ᵗʰd ³ʳᵈa ¹ˢᵗc ⁰ᵗʰb ⟩, a > b > c > d」 and ✅「⟨? ⋯ 1 ⋯ (?−2) ⋯⟩ (?≠3)」:
┌───┬───┬───┬───┬───┬───┬───┐
│6th│ 5▲│4th│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ │ 0 │ 1 │ │ 2 │ 3 │ 4 │
└───┴───┴───┴───┴───┴───┴───┘
It is a contradiction however, as we could not avoid matching ⛔「⟨⋯ Perm(0,6) ⋯⟩」 or ⛔「0 ∾ 3 ∾ 6」.
------------------------------
We have verified our claim in (2). Accordingly, we have
┌───┬───┬───┬───┬───┬───┬───┐
│6th│ 5■│4th│3rd│2nd│1st│0th│▒
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡▒
│ │ │ │ │ │ 3 │ 4 │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 3 │ │ 1 │ │ │ │ 3 │ 4 │▒
└───┴───┴───┴───┴───┴───┴───┘▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ │ 2 │ 6 │ │ 0 │ │ 5 │
└───┴───┴───┴───┴───┴───┴───┘
Next, we consider the value of [6th] and [3rd].
● By ✅「⟨? ⋯ 1 ⋯ (?−2) ⋯⟩ (?≠3)」, we have [6th] != 0.
● By ✅「⟨⋯ 1 ⋯ 2 ⋯ 3 ⋯⟩」, we have [6th] != 2.
● By ✅「⟨ ⁵ᵗʰd ³ʳᵈa ¹ˢᵗc ⁰ᵗʰb ⟩, a > b > c > d」, we have [3rd] > 4.
It follows that { [6th], [3rd] } = {5,6}.
(3) We proceed to show that ([6th], [3rd]) = (6, 5).
------------------------------
If on the contrary ([6th], [3rd]) = (5, 6):
┌───┬───┬───┬───┬───┬───┬───┐
│ 6▲│5th│4th│ 3▲│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡
│ 5 │ 1 │ │ 6 │ │ 3 │ 4 │
└───┴───┴───┴───┴───┴───┴───┘
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ │ 2 │ │ │ 0 │ │ │
└───┴───┴───┴───┴───┴───┴───┘
Then we would match ⛔「⟨⋯ Perm(0,6) ⋯⟩」, which is a contradiction.
------------------------------
Therefore, back to (3), we get
┌───┬───┬───┬───┬───┬───┬───┐
│ 6■│5th│4th│ 3■│2nd│1st│0th│▒
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡▒
│ │ 1 │ │ │ │ 3 │ 4 │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 4 │ 6 │ 1 │ │ │ │ 3 │ 4 │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 5 │ 6 │ 1 │ │ 5 │ │ 3 │ 4 │▒
└───┴───┴───┴───┴───┴───┴───┘▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ │ 2 │ │ │ 0 │ │ │
└───┴───┴───┴───┴───┴───┴───┘
Finally, to avoid ⛔「⟨? ⋯ 1 (?−6) ⋯ 0 ⋯⟩」, we finish by
┌───┬───┬───┬───┬───┬───┬───┐
│6th│5th│ 4■│3rd│ 2■│1st│0th│▒
╞═══╪═══╪═══╪═══╪═══╪═══╪═══╡▒
│ 6 │ 1 │ │ 5 │ │ 3 │ 4 │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 6 │ 6 │ 1 │ │ 5 │ 0 │ 3 │ 4 │▒
├───┼───┼───┼───┼───┼───┼───┤▒
Step 7 │ 6 │ 1 │ 2 │ 5 │ 0 │ 3 │ 4 │▒
└───┴───┴───┴───┴───┴───┴───┘▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
--- Idle ---
┌───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┘
Q.E.D.
#125034_v2.3
No comments:
Post a Comment