You are given a deck of cards, all face down, numbered from 1 to n, where n=2^{100} \approx 1.27 \cdot 10^{30}. You are not allowed to look at the numbers on any of the cards, but, on each step, you may place the cards (face down) in a row from left to right, and you will be told the number of triples of cards whose values are ordered from least to greatest, going from left to right. For instance, if n=6, and we laid down cards with values 4,1,5,2,3,6, from left to right, we would get a result of 6 triples (corresponding to 456,156,123,126,136,236).
Find an algorithm that, in at most k steps, will always allow you to determine the number written on every card. You do not have to be told that all triples in a placement are in order, but you need to have enough information to be certain that you know the number on each card.
Scoring:
An algorithm that completes in at most k steps will be awarded:
- 1 \text{ pt for } k > 10^{100}
- 10 \text{ pts for } k = 10^{100}
- 30 \text{ pts for } k = 10^{61}
- 50 \text{ pts for } k = 10^{33}
- 80 \text{ pts for } k = 2.6 \cdot 10^{30}
- 100 \text{ pts for } k = 1.3 \cdot 10^{30}
You are allowed to prove multiple bounds, and will receive points for the best bound that is correctly proven. Please state which bound you are trying to prove above any proof, or you may not be awarded points for that bound.
Partial points may be awarded for progress towards the next bound, and partial points may be deducted for logical flaws or lack of rigor in proofs. To get full points, you must demonstrate that your algorithm always produces a correct result, and always runs in at most the stated number of moves.