2024-10-11 Q3

Rearrange the digits in ⟨125034⟩ to meet the rules below.

⟨5th 4th 3rd 2nd 1st 0th⟩

✅Match

median {p5, p4, p0} = 2

{p4, p3, p2} = ? + {0,2,3}

Sim⟨ ⁵ᵗʰ3 ⁴ᵗʰ5 ³ʳᵈ2 ²ⁿᵈ4 ¹ˢᵗ1 ⁰ᵗʰ0 ⟩ ≥ 2

⛔Avoid

min ⊢4⊣ = 1

max {p5, p2, p1} = 5

----- Information -----

🔲 「median {p5, p4, p0} = 2」

The median of { [5th], [4th], [0th] } is 2.

There are 216 permutations matching this pattern.

Examples: ⟨523140⟩, ⟨420531⟩, ⟨410352⟩.

🔲 「{p4, p3, p2} = ? + {0,2,3}」

{ [4th], [3rd], [2nd] } = { ?, ?+2, ?+3 }.

There are 108 permutations matching this pattern.

Examples: ⟨354210⟩, ⟨052431⟩, ⟨213405⟩.

🔲 「Sim⟨ ⁵ᵗʰ3 ⁴ᵗʰ5 ³ʳᵈ2 ²ⁿᵈ4 ¹ˢᵗ1 ⁰ᵗʰ0 ⟩ ≥ 2」

⟨pᵢ⟩ matches this pattern if and only if #{ i: pᵢ = qᵢ } ≥ 2, where ⟨qᵢ⟩ ∶= ⟨352410⟩.

There are 191 permutations matching this pattern.

Examples: ⟨054213⟩, ⟨350241⟩, ⟨243510⟩.

🔳 「min ⊢4⊣ = 1」

The least element of ⊢4⊣ is 1. Also written as B(x=4, r=1), ⊢4⊣ denotes the neighborhood of 4 with radius one.

There are 528 permutations avoiding this pattern.

Examples: ⟨452130⟩, ⟨325401⟩, ⟨105432⟩.

🔳 「max {p5, p2, p1} = 5」

The greatest element of { [5th], [2nd], [1st] } is 5.

There are 360 permutations avoiding this pattern.

Examples: ⟨025134⟩, ⟨153402⟩, ⟨140235⟩.

#125034_v2.7

       ┌───┬───┬───┬───┬───┬───┐
       │5th│4th│3rd│2nd│1st│0th│▒
       ╞═══╪═══╪═══╪═══╪═══╪═══╡▒
Step 1 │   │ 2 │   │   │   │   │▒
       ├───┼───┼───┼───┼───┼───┤▒
Step 2 │   │ 2 │ 5 │   │   │   │▒
       ├───┼───┼───┼───┼───┼───┤▒
Step 3 │   │ 2 │ 5 │ 4 │   │   │▒
       ├───┼───┼───┼───┼───┼───┤▒
Step 4 │ 3 │ 2 │ 5 │ 4 │   │   │▒
       ├───┼───┼───┼───┼───┼───┤▒
Step 5 │ 3 │ 2 │ 5 │ 4 │   │ 1 │▒
       ├───┼───┼───┼───┼───┼───┤▒
Step 6 │ 3 │ 2 │ 5 │ 4 │ 0 │ 1 │▒
       └───┴───┴───┴───┴───┴───┘▒
        ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒

Proof of 2024-10-11 Q3
══════════════════════

By ✅「median {p5, p4, p0} = 2」, we have 

(1) 2 ∈ {p5, p4, p0}.

On the other hand, by ✅「{p4, p3, p2} = ? + {0,2,3}」, there are three possibilities for {p4, p3, p2}:

┌───┬───┬───┬───┬───┬───┐
│5th│4th│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╡
│   │ ▬ │ ▬ │ ▬ │   │   │
└───┴───┴───┴───┴───┴───┘

(A) {0,2,3};
(B) {1,3,4};
(C) {2,4,5}.

(2) We show that case (C) holds actually.

------------------------------

(2.1) If case (A) holds, then by (1), we have 2 = p4:

┌───┬───┬───┬───┬───┬───┐
│5th│ 4▲│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╡
│   │ 2 │0 3│0 3│   │   │
└───┴───┴───┴───┴───┴───┘

Comparing with ⟨352410⟩, there will be at most one agreed positional digit (at 1st). So, we cannot match ✅「Sim⟨ ⁵ᵗʰ3 ⁴ᵗʰ5 ³ʳᵈ2 ²ⁿᵈ4 ¹ˢᵗ1 ⁰ᵗʰ0 ⟩ ≥ 2」, which is a contradiction.

(2.2) Else, suppose case (B) holds:

┌───┬───┬───┬───┬───┬───┐
│5th│4th│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╡
│   │134│134│134│   │   │
└───┴───┴───┴───┴───┴───┘

Let us consider where to place 5. As it is the maximum digit, we need 5 ∉ {p5, p2, p1} in order to avoid ⛔「max {p5, p2, p1} = 5」. It implies 5 = p0:

┌───┬───┬───┬───┬───┬───┐
│5th│4th│3rd│2nd│1st│ 0▲│
╞═══╪═══╪═══╪═══╪═══╪═══╡
│   │134│134│134│   │ 5 │
└───┴───┴───┴───┴───┴───┘

Then, using (1), we get 2 = p5:

┌───┬───┬───┬───┬───┬───┐
│ 5▲│4th│3rd│2nd│1st│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╡
│ 2 │134│134│134│   │ 5 │
└───┴───┴───┴───┴───┴───┘

and p1 = 0 follows:

┌───┬───┬───┬───┬───┬───┐
│5th│4th│3rd│2nd│ 1▲│0th│
╞═══╪═══╪═══╪═══╪═══╪═══╡
│ 2 │134│134│134│ 0 │ 5 │
└───┴───┴───┴───┴───┴───┘

Again we cannot match ✅「Sim⟨ ⁵ᵗʰ3 ⁴ᵗʰ5 ³ʳᵈ2 ²ⁿᵈ4 ¹ˢᵗ1 ⁰ᵗʰ0 ⟩ ≥ 2」, which is a contradiction.

------------------------------

We have verified (2). Now

(3) {p4, p3, p2} = {2,4,5}.

By (1), we get 2 = p4, which is our first step:

       ┌───┬───┬───┬───┬───┬───┐
       │5th│ 4■│3rd│2nd│1st│0th│▒
       ╞═══╪═══╪═══╪═══╪═══╪═══╡▒
Step 1 │   │ 2 │4 5│4 5│   │   │▒
       └───┴───┴───┴───┴───┴───┘▒
        ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒

--- Idle ---
┌───┬───┬───┬───┬───┬───┐
│ 1 │   │   │ 0 │ 3 │   │
└───┴───┴───┴───┴───┴───┘

As 5 != p2 by ⛔「max {p5, p2, p1} = 5」, we get 5 = p3 and 4 = p2 as well:

       ┌───┬───┬───┬───┬───┬───┐
       │5th│4th│ 3■│ 2■│1st│0th│▒
       ╞═══╪═══╪═══╪═══╪═══╪═══╡▒
       │   │ 2 │   │   │   │   │▒
       ├───┼───┼───┼───┼───┼───┤▒
Step 2 │   │ 2 │ 5 │   │   │   │▒
       ├───┼───┼───┼───┼───┼───┤▒
Step 3 │   │ 2 │ 5 │ 4 │   │   │▒
       └───┴───┴───┴───┴───┴───┘▒
        ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒

--- Idle ---
┌───┬───┬───┬───┬───┬───┐
│ 1 │   │   │ 0 │ 3 │   │
└───┴───┴───┴───┴───┴───┘

Next, note that to match ✅「Sim⟨ ⁵ᵗʰ3 ⁴ᵗʰ5 ³ʳᵈ2 ²ⁿᵈ4 ¹ˢᵗ1 ⁰ᵗʰ0 ⟩ ≥ 2」, we need one more agreed positional digit. Since p1 != 1 by ⛔「min ⊢4⊣ = 1」, we need

(4) 3 = p5 or 0 = p0.

On the other hand, to match ✅「median {p5, p4, p0} = 2」, we need a digit greater than 2 in {p5, p0}. The only idle digit satisfying this is 3, so

(5) 3 = p5|p0.

It follows that 3 = p5, for otherwise 3 = p0 and we cannot match (4). Accordingly, we get

       ┌───┬───┬───┬───┬───┬───┐
       │ 5■│4th│3rd│2nd│1st│0th│▒
       ╞═══╪═══╪═══╪═══╪═══╪═══╡▒
       │   │ 2 │ 5 │ 4 │   │   │▒
       ├───┼───┼───┼───┼───┼───┤▒
Step 4 │ 3 │ 2 │ 5 │ 4 │   │   │▒
       └───┴───┴───┴───┴───┴───┘▒
        ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒

--- Idle ---
┌───┬───┬───┬───┬───┬───┐
│ 1 │   │   │ 0 │   │   │
└───┴───┴───┴───┴───┴───┘

Finally, to avoid ⛔「min ⊢4⊣ = 1」, we finish by

       ┌───┬───┬───┬───┬───┬───┐
       │5th│4th│3rd│2nd│ 1■│ 0■│▒
       ╞═══╪═══╪═══╪═══╪═══╪═══╡▒
       │ 3 │ 2 │ 5 │ 4 │   │   │▒
       ├───┼───┼───┼───┼───┼───┤▒
Step 5 │ 3 │ 2 │ 5 │ 4 │   │ 1 │▒
       ├───┼───┼───┼───┼───┼───┤▒
Step 6 │ 3 │ 2 │ 5 │ 4 │ 0 │ 1 │▒
       └───┴───┴───┴───┴───┴───┘▒
        ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒

--- Idle ---
┌───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┘

Q.E.D.

#125034_v2.7