Assume that the colonists are drawn from high altitude populations, as making use of an existing trait will take much less time than depending on a random mutation randomly showing up just in time.
Even with pre-existing traits, it is not guaranteed that humans would ever be able to exist without supplemental O2. If the traits from these three populations did combine in a beneficial manner, it may still only result in just needing much less additional O2 rather than removing the need for an emergency bottle.
For your story, assume that these traits did optimally combine into humans that could breath unaided. It will take quite a few generations for the individual traits to be spread among the entire population, even if breeding was deliberately controlled. Perhaps between 100 and 200 years after initial colonization?
Here is a bit of background on high altitude populations.
O2 availability similar to that at 5,000 meters would still require supplemental O2, but traits existing in the Tibetan, Andean, and/or Ethiopian populations should give your population a jump start on evolutionany processes to reduce the need for O2 bottles.
Andeans have higher hemoglobin concentrations which allows for more O2 to be carried (though it does thicken the blood a bit).
Tibetans increase their O2 intake with quicker breathing, along with expansion of the blood vessels to allow increased flow.
Ethiopian highlanders also successfully deal with high altitudes with minimal hypoxia, but do not have any of the adaptations shown by the Andeans or the Tibetans. So what adaptations have the Ethiopeans evolved to do this?
To quote Cynthia Beall, a physical anthropologist, "Right now we have no clue how they do it."
Three High-Altitude Peoples; Three Adaptations to Thin Air