a finite sets problem

Question

I was given the next riddle in one of the lectures: A jet plane with m ( a natural number) seats which is filled up to the maximum is about to take off. each passenger holds a card with a natural number in his hand which he cannot see nor can he see the cards that his fellow passengers hold. The plane will take off only if each of the passengers will guess what number it is that they hold. The captain decides to display a single number (a natural number) which will help the passengers figure out each of their own numbers. The question is, what is that number? P.S- the seats are numbered and each passenger knows the number of his seat. I'd really like some hints with this one! Thank you so much! *The captain can see each and every one of the numbers

Answer 1

Suppose that passenger $k$ has number $f(k)$.

Then the pilot can show the number $\prod\limits_{n=1}^N p_n^{f(n)}$. Where $p_n$ is the $n$'th prime and $N$ is the number of passengers.

By the fundamental theorem of arithmetic every passenger can determine every person's number.

Answer 2

Edit: here's a second answer, probably shortest so far and easiest to decode.

Suppose the longest number has $d$ digits. The captain pads each number with zeroes on the left so that it's $d$ digits long, then concatenates them in seat order. Since the passengers know the number of seats they can compute $d$ from the length of the number they're told, then count off to their seat number. If the number of seats is unknown too then the caption uses $d$ as a prefix, padded the same way.

---

First solution:

Since the captain knows the numbers that correspond to seats he can tell the passengers the product of the numbers $(p_n)^{c}$ where $p_n$ is the $n$th prime and $c$ is the number held by the passenger in seat $n$.

The passengers will have to be pretty good at arithmetic. Maybe their cell phones can factor big numbers.

Answer 3

Suppose the numbers (positive integers) are $N_1,N_2,\dots,N_m.$ The pilot displays the number $10^{N_1}+10^{N_1+N_2}+\cdots+10^{N_1+N_2+\cdots+N_m}.$

Answer 4

Suppose the plane has just 4 seats. The captain could display the number $13243241$ to show that seat 1 was assigned number 3, seat 2 was assigned number 4, seat 3 was assigned number 2 and seat 4 was assigned number 1. More seats can be dealt with in an analogous way that requires no computations.

Answer 5

Because $\mathbb{N}$ can be bijectively mapped to $\mathbb{N}^m$ the captain can encode all $m$ numbers $k_i$, ordered by the number of the seat into one natural number: $$ N = \langle k_1, \dotsc, k_m\rangle $$

However this leaves the passengers to guess what encoding scheme (Cantor pairing, prime number factorization, ..) he might have used.

So can we infer from $N$ what encoding was used?

Answer 6

Another idea is to order these numbers according to seats and describe them for example in a binary representations (using $0$s and $1$s) while separating individual numbers by digit that is not present in that representation (e.g. $2$). So for example numbers $1$,$5$ and $7$, which have binary representations $1$,$101$ and $111$, could be encoded into number $121012111$.

Answer 7

The pilot displays the number of digits of number held by passenger 1. Eg: if passenger 1 holds the number 403, then pilot displays 000403 and passenger 1 counts 403 after 3 zeros. The same logic is continued after 403 for second passenger. It works only if the passengers donot have additional 0 in front of the number they hold. The only problem is pilot should a huge display and passengers should keep the count.

Edit: the same logic modified by using 1s to indicate initial zeros in a number, can used to tell the exact sequence and not just the number.

Answer 8

Simplest answer would be to come up with a n-digit mapping scheme between seat numbers and card numbers.

For example, suppose the seats were 1-100 and the numbers were 1-1000. Then the pilot would write a number with ordered groupings starting from 100 (to prevent leading zeroes) and descending, using 0's to preserve space.

So it would look something like this:

10010000990878098...

Or in formatted fashion

100 1000 099 0878 098 ...