The local supermarket offers seasonal deals on their apples and oranges. You want either apples or oranges on any given day, but don't know until you wake up; you want to minimise your cost. You always have the option to buy apples or oranges on a given day for cost 1. Or you get the discount deal — you could buy apples or oranges until the end of the season for a cost of B ≥ 1. Whenever you pay the cost B, you pay for the following day's fruit, even though you don't know what you may want on that day. Note that you can buy a discount deal on day 0 so that you already have it on day 1. If you’ve already gotten a discount deal for the apples and you decide you want a discount deal for oranges now, your discount deal for the apples ends prematurely (and vice versa). Thus, you can only have an active discount deal for one of the two types of fruit at any given moment, and switching from one type to the other costs B. If you feel like buying apples while you’re holding a discount deal for oranges, you still pay 1 to buy the apples for that day (and vice versa). Each day you MUST buy what you feel like having on that day. Show that no deterministic online algorithm for the problem can be (2 − ε)-competitive for any constant ε > 0. Then show that there is an α-competitive deterministic online algorithm where α is an absolute constant, not depending on B or the length of the input sequence.
I have tried all sorts of small examples, and although the first part feels intuitive, I have no idea how to prove it. I don't even really know how to write an algorithm that calculates the offline optimal solution for a given string of days.
