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
(83)
Algebra
(58)
Solved
(44)
Inequality
(33)
Number Theory
(26)
Geometry
(25)
induction
(24)
KBB
(15)
Solution
(14)
polynomial
(14)
probability
(14)
sequence
(14)
prime
(13)
Random
(11)
cauchy
(11)
divisibility
(11)
KBB2
(10)
calculus
(10)
chess board
(10)
expected value
(10)
coloring
(9)
convex
(8)
graph theory
(8)
modulo
(8)
counting
(7)
function
(7)
homogeneous
(7)
probabilistic method
(7)
symmetric
(7)
triangle
(7)
Riddles / Puzzles
(6)
array
(6)
binary
(6)
circle
(6)
game
(6)
generating function
(6)
lattice
(6)
maximum
(6)
recursion
(6)
turn
(6)
functional equation
(5)
invariance
(5)
invariant
(5)
majorization
(5)
parity
(5)
physics
(5)
pigeon hole
(5)
trigonometry
(5)
AM-GM
(4)
KBB3
(4)
card
(4)
factorization
(4)
fermat
(4)
integral
(4)
inverse modulo
(4)
inversion
(4)
mechanics
(4)
minimum
(4)
repetition
(4)
tangent line
(4)
2008
(3)
arbitrarily
(3)
binomial
(3)
catalan
(3)
color
(3)
drawing
(3)
ellipse
(3)
extremal principle
(3)
graph
(3)
group
(3)
harmonic
(3)
jensen
(3)
normalization
(3)
permutation
(3)
projective geometry
(3)
rotation
(3)
steps
(3)
tangent
(3)
tangent circles
(3)
vector
(3)
2 variable recursion
(2)
3 variable
(2)
3D
(2)
Add new tag
(2)
Fibonacci Series
(2)
OSN
(2)
OSN 2009
(2)
XOR
(2)
airplane
(2)
algorithm
(2)
average
(2)
backward induction
(2)
bijection
(2)
binary digit
(2)
change
(2)
circular
(2)
coin
(2)
colored
(2)
combinatorial sum binomial identity sum
(2)
comparing sets
(2)
complex
(2)
composition
(2)
contradiction
(2)
convex hull
(2)
cosine
(2)
cubic number
(2)
cycle
(2)
dandelin sphere
(2)
differential equation
(2)
digit
(2)
distribution
(2)
enumeration
(2)
equilateral lattice
(2)
factorial
(2)
fibonacci
(2)
flea
(2)
floor
(2)
foci
(2)
focus
(2)
fundamental theorem of algebra
(2)
gcd
(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)
karamata
(2)
light
(2)
mapping
(2)
marbles
(2)
match
(2)
matrix
(2)
maximal principle
(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)
schur
(2)
seat
(2)
solid geometry
(2)
step
(2)
string
(2)
subset
(2)
sum
(2)
sum of squares
(2)
table
(2)
taylor series
(2)
telescoping
(2)
tetrahedron
(2)
topology
(2)
transformation
(2)
triangular numbers
(2)
2012
(1)
Bus
(1)
Parameter
(1)
Sprague-Grundy
(1)
abc
(1)
absolute value
(1)
acquaintance
(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)
chebysev
(1)
chinese remainder theorem
(1)
coin toss
(1)
combat
(1)
comic
(1)
commutative
(1)
completable
(1)
cone
(1)
configuration
(1)
consecutive
(1)
constraint
(1)
construction
(1)
convergent
(1)
correlation
(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)
fake
(1)
fermat point
(1)
flip
(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)
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)
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)
rearrangement
(1)
reflection
(1)
reset
(1)
residue system
(1)
roll
(1)
route
(1)
rpg
(1)
saddleback
(1)
scale
(1)
school
(1)
segment
(1)
series
(1)
shuffling
(1)
sine
(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)
strong induction
(1)
student
(1)
subgroup
(1)
sudoku
(1)
summation
(1)
sums of squares
(1)
supersum
(1)
surjective
(1)
switch
(1)
system of equations
(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)
winning-strategy
(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)