Skip to main content
TeX
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Dealing cards numbered 1$1$ to n$n$ into piles

Is anything known about the following?

I hold in my hand a shuffled pack of cards numbered 1$1$ to n$n$. One by one, I place them all, face up, on a table in piles. For each card I deal from my hand, say card numbered k$k$, I open a new pile only if the top card of an existing pile is not k + 1;$k + 1$; otherwise I place that card on top of that pile. If at any stage (before dealing a new card) the bottom card of an existing pile is one less than the top card of another pile, I combine the two into a new pile in the obvious way.

  1. What is the most likely maximum number of piles that will be formed at some stage while so dealing the n$n$ cards?

  2. What is the expected maximum number of piles that will be formed at some stage while so dealing the n$n$ cards?

In both cases, count piles only if no two piles can be combined into one.

Dealing cards numbered 1 to n into piles

Is anything known about the following?

I hold in my hand a shuffled pack of cards numbered 1 to n. One by one, I place them all, face up, on a table in piles. For each card I deal from my hand, say card numbered k, I open a new pile only if the top card of an existing pile is not k + 1; otherwise I place that card on top of that pile. If at any stage (before dealing a new card) the bottom card of an existing pile is one less than the top card of another pile, I combine the two into a new pile in the obvious way.

  1. What is the most likely maximum number of piles that will be formed at some stage while so dealing the n cards?

  2. What is the expected maximum number of piles that will be formed at some stage while so dealing the n cards?

In both cases, count piles only if no two piles can be combined into one.

Dealing cards numbered $1$ to $n$ into piles

Is anything known about the following?

I hold in my hand a shuffled pack of cards numbered $1$ to $n$. One by one, I place them all, face up, on a table in piles. For each card I deal from my hand, say card numbered $k$, I open a new pile only if the top card of an existing pile is not $k + 1$; otherwise I place that card on top of that pile. If at any stage (before dealing a new card) the bottom card of an existing pile is one less than the top card of another pile, I combine the two into a new pile in the obvious way.

  1. What is the most likely maximum number of piles that will be formed at some stage while so dealing the $n$ cards?

  2. What is the expected maximum number of piles that will be formed at some stage while so dealing the $n$ cards?

In both cases, count piles only if no two piles can be combined into one.

Source Link

Dealing cards numbered 1 to n into piles

Is anything known about the following?

I hold in my hand a shuffled pack of cards numbered 1 to n. One by one, I place them all, face up, on a table in piles. For each card I deal from my hand, say card numbered k, I open a new pile only if the top card of an existing pile is not k + 1; otherwise I place that card on top of that pile. If at any stage (before dealing a new card) the bottom card of an existing pile is one less than the top card of another pile, I combine the two into a new pile in the obvious way.

  1. What is the most likely maximum number of piles that will be formed at some stage while so dealing the n cards?

  2. What is the expected maximum number of piles that will be formed at some stage while so dealing the n cards?

In both cases, count piles only if no two piles can be combined into one.