Gilbreath Principle

Gilbreath Principle

Gilbreath Principle in Action

Note

THEOREM. The Ultimate Gilbreath Principle. For a permutation \(\pi\) of \(\{1,2,3, \ldots, N\}\), the following four properties are equivalent:

1. \(\pi\) is a Gilbreath permutation.
2. For each \(j\), the top \(j\) cards \(\{\pi(1), \pi(2), \pi(3), \ldots, \pi(j)\}\) are distinct modulo \(j\).
3. For each \(j\) and \(k\) with \(k j \leq N\), the \(j\) cards \((\pi((k-1) j+1)\), \(\pi((k-1) j+2), \ldots, \pi(k j)\}\) are distinct modulo \(j\).
4. For each \(j\), the top \(j\) cards are consecutive in \(1,2,3, \ldots, N\).

The Gilbreath Principle is a fascinating mathematical property that works with sequences of numbers. Let’s explore it interactively.

viewof numCards = Inputs.range([0, 3], {
  step: 1,
  value: 4,
  label: "Number of cards to deal off:"
})

deck = {
  let numbers = [1, 2, 3]
  let dealt = numbers.slice(0, numCards).reverse();
  let remaining = numbers.slice(numCards);
  return {dealt, remaining}
}

viewof shuffle = Inputs.button("Riffle Shuffle", {
  value: "Shuffle"
})

result = {
  if (shuffle === undefined) return [];
  let shuffled = [];
  let i = 0, j = 0;
  
  while (i < deck.dealt.length && j < deck.remaining.length) {
    if (Math.random() < 0.5) {
      shuffled.push(deck.dealt[i++]);
    } else {
      shuffled.push(deck.remaining[j++]);
    }
  }
  
  while (i < deck.dealt.length) shuffled.push(deck.dealt[i++]);
  while (j < deck.remaining.length) shuffled.push(deck.remaining[j++]);
  
  return shuffled;
}

display = {
  const cardStyle = `
    display: inline-block;
    width: 40px;
    height: 40px;
    margin: 5px;
    line-height: 40px;
    text-align: center;
    font-family: monospace;
    font-size: 16px;
    border-radius: 5px;
  `;
  
  return html`
    <div style="margin: 20px 0;">
      <div style="margin-bottom: 20px;">
        <div style="margin-bottom: 10px; font-weight: bold;">Dealt Cards:</div>
        <div>
          ${deck.dealt.map(n => 
            `<span style="${cardStyle} background: #ffcccc; border: 2px solid #ff9999;">${n}</span>`
          ).join('')}
        </div>
      </div>
      
      <div style="margin-bottom: 20px;">
        <div style="margin-bottom: 10px; font-weight: bold;">Remaining Cards:</div>
        <div>
          ${deck.remaining.map(n => 
            `<span style="${cardStyle} background: #cce6ff; border: 2px solid #99ccff;">${n}</span>`
          ).join('')}
        </div>
      </div>
      
      ${result.length > 0 ? html`
        <div>
          <div style="margin-bottom: 10px; font-weight: bold;">After Shuffle:</div>
          <div>
            ${result.map(n => 
              `<span style="${cardStyle} background: #e6e6e6; border: 2px solid #cccccc;">${n}</span>`
            ).join('')}
          </div>
        </div>
      ` : ''}
    </div>
  `
}

Try dealing different numbers of cards and observe what happens when you riffle shuffle them! The Gilbreath Principle states that after the riffle shuffle, adjacent pairs of cards will always contain one card from each of the original piles.