ความน่าจะเป็นที่ชิ้นส่วนไม้ก้อนที่หักจะสร้างเป็นรูป N เหลี่ยมได้ใน C++

ได้รับไม้ก้อนหนึ่งยาวเท่าใด แล้วหักสุ่มเป็น n ชิ้น (ความยาวเป็นจำนวนเต็มหรือทศนิยม) งานคือหาความน่าจะเป็นที่ชิ้นส่วนเหล่านี้จะประกอบเป็นรูป n เหลี่ยมได้

เงื่อนไขการสร้างรูป N เหลี่ยม (Polygon Inequality)

ชิ้นส่วน n ชิ้น จะประกอบเป็นรูป n เหลี่ยมได้ ก็ต่อเมื่อ ชิ้นที่ยาวที่สุดสั้นกว่าผลรวมของชิ้นอื่นๆ

max(lengths) < sum(lengths) - max(lengths)
⇔ 2 × max(lengths) < total_length

ความน่าจะเป็น (Probability Formula)

สำหรับการหักสุ่มแบบ Uniform (Uniform random breaks):

P(can form n-gon) = 1 - n / 2^(n-1)

การนำไปใช้ (Derivation Idea)

เหตุการณ์ที่ ไม่สามารถ สร้างรูป n เหลี่ยมได้ คือมีชิ้นหนึ่งยาว ≥ ครึ่งหนึ่งของความยาวรวม

ใช้หลักการ Inclusion-Exclusion และ Symmetry จะได้สูตรข้างต้น

ตัวอย่าง

n = 3 (สามเหลี่ยม)

P = 1 - 3/2² = 1 - 3/4 = 1/4 = 0.25

ตรงกับโจทย์คลาสสิก "Probability that 3 pieces form a triangle = 1/4"

n = 4 (สี่เหลี่ยม)

P = 1 - 4/2³ = 1 - 4/8 = 1/2 = 0.5

n = 5

P = 1 - 5/2⁴ = 1 - 5/16 = 11/16 = 0.6875

ตัวอย่างโค้ด

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

double polygonProbability(int n) {
    if (n < 3) return 0;  // ต้องมีอย่างน้อย 3 ชิ้น
    double denominator = pow(2.0, n - 1);
    return 1.0 - n / denominator;
}

int main() {
    cout << fixed << setprecision(6);
    for (int n = 3; n <= 10; n++) {
        cout << "n=" << n << ": P = " << polygonProbability(n) << endl;
    }
    
    // ตัวอย่างเฉพาะ
    cout << "\nLength=10, pieces=4: " << polygonProbability(4) << endl;  // 0.5
    cout << "Length=5, pieces=3: " << polygonProbability(3) << endl;   // 0.25
    
    return 0;
}

ผลลัพธ์

n=3: P = 0.250000
n=4: P = 0.500000
n=5: P = 0.687500
n=6: P = 0.812500
n=7: P = 0.890625
n=8: P = 0.945312
n=9: P = 0.972656
n=10: P = 0.986328

Length=10, pieces=4: 0.500000
Length=5, pieces=3: 0.250000

ข้อสังเกต

• ความน่าจะเป็นเข้าใกล้ 1 เร็วมากเมื่อ n เพิ่มขึ้น
• ความยาวของไม้ก้อน ไม่ส่งผล ต่อความน่าจะเป็น (Scale invariance)
• สูตรนี้สมมติการหักเป็น Independent Uniform Random Breaks

ข้อผิดพลาดในโค้ดต้นฉบับ

โค้ดต้นฉบับมี (1 < (pieces-1)) ซึ่งเป็น bitwise shift ผิดพลาด ควรเป็น (1 << (pieces-1)) (left shift = 2^(pieces-1))

การจำลอง (Monte Carlo Simulation) เพื่อตรวจสอบ

double simulatePolygon(int n, int trials = 1000000) {
    int success = 0;
    for (int t = 0; t < trials; t++) {
        vector<double> pieces(n);
        // สุ่ม n-1 จุดบน [0,1]
        vector<double> cuts(n - 1);
        for (int i = 0; i < n - 1; i++) cuts[i] = (double)rand() / RAND_MAX;
        sort(cuts.begin(), cuts.end());
        
        // คำนวณความยาวชิ้น
        pieces[0] = cuts[0];
        for (int i = 1; i < n - 1; i++) pieces[i] = cuts[i] - cuts[i-1];
        pieces[n-1] = 1.0 - cuts[n-2];
        
        // เช็ค polygon inequality
        double maxPiece = *max_element(pieces.begin(), pieces.end());
        if (2 * maxPiece < 1.0) success++;
    }
    return (double)success / trials;
}