# a finite sets problem

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

• I suppose the Captain could, given his knowledge of the mapping from seat numbers to card numbers, express that mapping as encoded in a single natural number. Of course the corresponding "mapping" number will be much larger than the card numbers, and nothing might have prepared the passengers to be able to "decode" that number in order to deduce their individual card numbers. – hardmath Dec 25 '16 at 0:58

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.

• The OP says that no one can see any of the cards, not their own and not others'. – Erick Wong Dec 25 '16 at 0:48
• A sum with really help. As stated above, no one can see any of the cards. D: – Lola Dec 25 '16 at 0:51
• will not * my mistake – Lola Dec 25 '16 at 0:51
• But how do the passengers know that prime factorization was used for encoding, there are other methods as well that result in a single natural number. – mvw Dec 25 '16 at 1:22
• I guess they decide on a strategy beforehand, otherwise there isn't a strategy. its possible some of them don't know what a number is. – Jorge Fernández Hidalgo Dec 25 '16 at 1:23

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}.$

• nice!${}{}{}{}{}$ – Jorge Fernández Hidalgo Dec 25 '16 at 1:06
• @JorgeFernándezHidalgo Thanks for catching my "typo"! – bof Dec 25 '16 at 1:07
• Assuming this gives a proper bijection, how do all passengers know this encoding was used? – mvw Dec 25 '16 at 1:27

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.

• factoring will be easier, since they know exactly which primes are being used. This can be done in time $N\log(N)n$. (where $N$ is the number of passengers and n is the size of numbers.) – Jorge Fernández Hidalgo Dec 25 '16 at 0:53
• But passengers with even seat numbers might decode using Cantor pairing functions, the passengers with odd seat numbers try prime factorization, How to sync them to the proper encoding? – mvw Dec 25 '16 at 1:24
• @mvw The captain and passengers must have agreed on a coding scheme in advance, else the problem is unsolvable. Several other comments address this question. It should be made explicit in the question. – Ethan Bolker Dec 25 '16 at 23:52

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$.

• nice, this reminds me of the conway $13$ function. – Jorge Fernández Hidalgo Dec 25 '16 at 1:09
• But where is the hint that all passengers agree on that encoding? – mvw Dec 25 '16 at 1:20
• @mvw Well that is a required assumption, without that the riddle seems to be pointless... But it would be nice to have this clarified by OP – Sil Dec 25 '16 at 1:23

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.

• but what happens when numbers larger than $9$ appear? – Jorge Fernández Hidalgo Dec 25 '16 at 1:03
• Does $12222$ mean seat $1$ was assigned number $2$ and seat $2$ was assigned number $22$ or is it the other way around? – bof Dec 25 '16 at 1:04
• $3421$ would suffice. – mvw Dec 25 '16 at 1:18
• I was assuming that the assigned numbers are all $\leq m$, or even $\leq N$ where $N$ is known. If no upper bound for the assigned numbers is known I guess the simple method I described is not applicable – Andrea Mori Dec 25 '16 at 9:08

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?

• One can definitely not infer from $N$ how it was encoded. An encoding, after all, is just an injective map $\mathbb N^k\rightarrow \mathbb N$ and, for any $x\in \mathbb N^k$ and $y\in \mathbb N$ there is such a map $f$ with $f(x)=y$. – Milo Brandt Dec 25 '16 at 2:30

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 ...

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.