2
$\begingroup$

In Infinityland, people have mastered full control over Infinity. They have built registers which are capable of holding as much data as needed. There are two types of registers in infinityland which are called infinity registers:

  • The integer infinity register: Can hold any integer value from -inf to + inf. Costs $\$100$ .

  • The real infinity register: Can hold any real value from -inf to + inf with infinite precision. Costs $\$200$.

Rather expensive, are they not? Well, not actually, because the people over at Infinityland have really good compression algorithms which allow them to stash huge amounts of data in those tiny registers.

What is the lowest cost you must incur to save a list of real numbers if

  • The list can hold a maximum of $100$ real numbers.

  • The list can hold infinitely many real numbers.

Note

In the second case, the information must be decompressible without the knowledge of the size of the list.

$\endgroup$
  • 2
    $\begingroup$ Is "infinitely many real numbers" countably infinite or any cardinality? $\endgroup$ – Ben Frankel Oct 4 '15 at 19:54
  • $\begingroup$ @BenFrankel Yeah, countably. $\endgroup$ – Rohcana Oct 4 '15 at 19:58
6
$\begingroup$

For both, I can do it with

$200.

I'm just going to describe the second case here. First, take the inverse tangent of all of your numbers and divide by 2pi to convert everything to a real number between -1/2and 1/2; then add 1/2 to get all of your numbers between 0 and 1.
Next, split all of your numbers up into digits. Start with "0.". Take the first digit of the first, then the next unused digit of the first and second, then the next unused digit of the first through third, then the next unused digit of the first through fourth, et cetera. This gives you one real number!

To encode the number of items:

Start with that number instead of 0 (thanks, Ben) or write it in unary (or base-9 but efficiency doesn't really matter here) at the beginning and add a 0 in between the unary and the compressed string.

Proof that this is the best possible:

The only cheaper possibility is that you could do it with an integer register. That would mean countably infinite compressed numbers would decompress into uncountably infinite original numbers. This would require one input to give multiple outputs, which is not possible.

$\endgroup$
  • $\begingroup$ Perhaps a explanation is required, In the second case the the number of items is variable and must be saved in the registers as well. In other words, it must be decompressible without the knowledge of the size of the list. $\endgroup$ – Rohcana Oct 4 '15 at 19:42
  • $\begingroup$ @Anachor: Set all the others to 0 then. Problem solved. Or denote how many there are in unary (if there aren't infinitely many), then add a 0, then add the actual string to decompress. $\endgroup$ – Deusovi Oct 4 '15 at 19:44
  • 1
    $\begingroup$ @f" That doesn't work, you can't decompress it without knowing how many numbers there are in the list. $\endgroup$ – Rohcana Oct 4 '15 at 19:46
  • 1
    $\begingroup$ @f'': So what's the difference beteeen 13 and 130 items? What do you do with the other digits? $\endgroup$ – Deusovi Oct 4 '15 at 19:51
  • 2
    $\begingroup$ The variable size of the list is an easy fix. Instead of starting with "0." we may start with "size of list." (this of course is only a fix for the case of a finite size list) $\endgroup$ – Ben Frankel Oct 4 '15 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.