What is the probability that everyone's actual seat number and their assigned seat number differ by at most 1? That is, no one sits more than 1 seat away from their assigned seat.

#### Solution

Zeke's solution in the comment is correct.

skip to main |
skip to sidebar
## Pages

## Tuesday, October 27, 2009

###
Passengers Boarding Airplane, Part Deux

## Links

## Labels

Math is evil...

2009 passengers are waiting in a line to board an airplane with 2009 seats. The seats are numbered from 1 to 2009. Each passenger has a boarding pass that has his/her seat number on it. However, these passengers are oblivious to their boarding pass and choose their seats at random, each with a uniform probability from the available empty seats.

What is the probability that everyone's actual seat number and their assigned seat number differ by at most 1? That is, no one sits more than 1 seat away from their assigned seat.

#### Solution

Zeke's solution in the comment is correct.

What is the probability that everyone's actual seat number and their assigned seat number differ by at most 1? That is, no one sits more than 1 seat away from their assigned seat.

Zeke's solution in the comment is correct.

Subscribe to:
Post Comments (Atom)

Combinatorics
(71)
Algebra
(45)
Solved
(44)
Number Theory
(26)
Inequality
(25)
Geometry
(24)
induction
(20)
KBB
(15)
Solution
(14)
probability
(14)
sequence
(14)
prime
(13)
Random
(11)
divisibility
(11)
polynomial
(11)
KBB2
(10)
expected value
(9)
calculus
(8)
coloring
(8)
modulo
(8)
chess board
(7)
graph theory
(7)
homogeneous
(7)
symmetric
(7)
Riddles / Puzzles
(6)
array
(6)
binary
(6)
cauchy
(6)
circle
(6)
convex
(6)
counting
(6)
function
(6)
generating function
(6)
lattice
(6)
triangle
(6)
functional equation
(5)
invariance
(5)
parity
(5)
physics
(5)
probabilistic method
(5)
recursion
(5)
KBB3
(4)
card
(4)
fermat
(4)
invariant
(4)
inverse modulo
(4)
inversion
(4)
maximum
(4)
mechanics
(4)
pigeon hole
(4)
repetition
(4)
tangent line
(4)
2008
(3)
arbitrarily
(3)
catalan
(3)
drawing
(3)
ellipse
(3)
factorization
(3)
game
(3)
group
(3)
harmonic
(3)
integral
(3)
majorization
(3)
minimum
(3)
normalization
(3)
permutation
(3)
projective geometry
(3)
rotation
(3)
steps
(3)
tangent
(3)
tangent circles
(3)
trigonometry
(3)
turn
(3)
vector
(3)
3D
(2)
AM-GM
(2)
Add new tag
(2)
OSN
(2)
OSN 2009
(2)
XOR
(2)
airplane
(2)
average
(2)
backward induction
(2)
bijection
(2)
binary digit
(2)
binomial
(2)
change
(2)
circular
(2)
coin
(2)
color
(2)
colored
(2)
comparing sets
(2)
complex
(2)
composition
(2)
contradiction
(2)
convex hull
(2)
cubic number
(2)
cycle
(2)
dandelin sphere
(2)
differential equation
(2)
digit
(2)
distribution
(2)
enumeration
(2)
equilateral lattice
(2)
extremal principle
(2)
flea
(2)
floor
(2)
foci
(2)
focus
(2)
gcd
(2)
graph
(2)
guess
(2)
hat
(2)
holder
(2)
incenter
(2)
infimum
(2)
infinite chess
(2)
infinite series
(2)
infinite sum
(2)
injective
(2)
inradius
(2)
integers
(2)
inverse
(2)
iterative
(2)
light
(2)
mapping
(2)
match
(2)
muirhead
(2)
painted sphere
(2)
passenger
(2)
path
(2)
power mean
(2)
prime field
(2)
prisoner
(2)
random walk
(2)
replacement
(2)
reversible
(2)
seat
(2)
solid geometry
(2)
step
(2)
string
(2)
sum
(2)
sum of squares
(2)
taylor series
(2)
telescoping
(2)
tetrahedron
(2)
topology
(2)
transformation
(2)
triangular numbers
(2)
2 variable recursion
(1)
2012
(1)
3 variable
(1)
Bus
(1)
Fibonacci Series
(1)
abc
(1)
absolute value
(1)
acquaintance
(1)
algorithm
(1)
analytic
(1)
arithmetic
(1)
ball
(1)
balls
(1)
banach tarski paradox
(1)
binomial theorem
(1)
bipartite
(1)
black cells
(1)
boarding
(1)
boat
(1)
boxes
(1)
boy
(1)
break
(1)
brilliant
(1)
building
(1)
car
(1)
ceiling
(1)
center of mass
(1)
chinese remainder theorem
(1)
coin toss
(1)
combat
(1)
combinatorial sum binomial identity sum
(1)
comic
(1)
commutative
(1)
completable
(1)
cone
(1)
configuration
(1)
consecutive
(1)
constraint
(1)
construction
(1)
convergent
(1)
correlation
(1)
cosine
(1)
cosine theorem
(1)
counterfeit
(1)
coupons
(1)
covariance
(1)
cross section
(1)
crystal ball
(1)
cube
(1)
cumulative sum
(1)
cyclic quadrilateral
(1)
deduction
(1)
definite positive
(1)
degree
(1)
differential geometry
(1)
diophantine
(1)
discriminant
(1)
dot product
(1)
dps
(1)
eddyhermanto
(1)
eisenstein's criterion
(1)
elementary
(1)
enumerative
(1)
equilateral
(1)
eucledian
(1)
excircle
(1)
expressible
(1)
eye color
(1)
factorial
(1)
fake
(1)
fermat point
(1)
fibonacci
(1)
flip
(1)
fundamental theorem of algebra
(1)
gambler's ruin
(1)
gas stations
(1)
geometric mean
(1)
girl
(1)
gravity
(1)
grid
(1)
healer
(1)
hypercube
(1)
imo
(1)
indefinite
(1)
infinite prime
(1)
inner product
(1)
integer inequality
(1)
integration by parts
(1)
interpretation
(1)
intersect
(1)
island
(1)
jensen
(1)
johan gunardi
(1)
jug
(1)
jump
(1)
lagrange identity
(1)
lemma
(1)
liar
(1)
limit
(1)
line
(1)
linear combination
(1)
linear time
(1)
loci
(1)
locker
(1)
logic
(1)
mafia
(1)
marbles
(1)
matrix
(1)
mean
(1)
minkowski
(1)
mixing
(1)
modular equation
(1)
moment of inertia
(1)
monotonic
(1)
monotonic function
(1)
movie
(1)
multivariable recursion
(1)
musings
(1)
natural numbers
(1)
operation
(1)
optically congruent
(1)
optimization
(1)
oracle
(1)
ordering
(1)
osculating circle
(1)
paint
(1)
pair
(1)
parabola
(1)
parallelogram
(1)
perimeter
(1)
piecewise
(1)
poison
(1)
positive definite
(1)
positive integers
(1)
power of two
(1)
power sum
(1)
precision
(1)
prime set
(1)
product
(1)
proposal
(1)
propose
(1)
pyramidal numbers
(1)
quaternary
(1)
radio
(1)
ramsey
(1)
random variables
(1)
rank
(1)
rat
(1)
ravi's substitution
(1)
reflection
(1)
reset
(1)
residue system
(1)
roll
(1)
route
(1)
rpg
(1)
saddleback
(1)
scale
(1)
school
(1)
schur
(1)
segment
(1)
series
(1)
shuffling
(1)
skew
(1)
sorted
(1)
spaceship
(1)
span
(1)
speed
(1)
spiked math
(1)
spy
(1)
square
(1)
statistics
(1)
stone
(1)
stones
(1)
strict inequality
(1)
strings
(1)
student
(1)
subgroup
(1)
subset
(1)
sudoku
(1)
summation
(1)
sums of squares
(1)
supersum
(1)
surjective
(1)
switch
(1)
system of equations
(1)
table
(1)
tank
(1)
technology review
(1)
tennis
(1)
ternary
(1)
tesselation
(1)
tiling
(1)
tournament
(1)
translation
(1)
triangular lattice
(1)
triangulation
(1)
tuple
(1)
turkevici
(1)
tuymaada
(1)
uniform
(1)
unity
(1)
weighings
(1)
wilso
(1)
wilson
(1)
wine
(1)
yakut
(1)
year
(1)

lol nice.

ReplyDeleteLet f(n) be the number of permutations where among n passengers no one sits more than 1 seat away from their assigned seat. We can obtain f(n+1) as follows. Observe that the (n+1)th passenger must be in either his seat or the nth seat. If he sits in his seat then all passengers in front of him must sit in a valid configuration - there are f(n) of these. If he does not sit in his seat, then he must sit in the nth seat, and the nth passenger must sit in the (n+1)th seat. (Note that it must be the nth passenger in the (n+1)th). Now, all passengers before the (n+1)th passenger must be in a valid configuration - there are f(n-1) of these.

Hence, f(n+1) = f(n) + f(n-1). Note that f(1) = 1, f(2) = 2. This is the Fibonacci series (fudging indices but whatever)

So, the probability is f(n)/(n!). For n=2009, that's pretty much 0. (as was apparent from the start)