I think you have a misunderstanding about something, but I can't say precisely what. You seem to really be asking for two different sorts of CT, not CT vs something else. Both math and CS require some facility in CT and, thus, CT is a prerequisite, whether taught explicitly or learned on one's own.
So, if a student can provide a "trivial" solution to a programming question then they are already engaged in computational thinking. So no "example" is likely to be very powerful in extending their thinking.
But CT is much broader than that and is a skill that people need in general, not just for computing. You need it at the market to pay for things and check that you get the right change (or, you did before electronic payments became ubiquitous). But thinking in terms of orders of magnitude, at least is useful even when reading the newspaper about scientific discovery and maybe even politics.
Let me suggest a couple of things.
If you students seem to be weak in CT, then teach that prior to getting in to the details of programming, which has its own pitfalls. Use something like CS Unplugged if you want something directly connected to computing, or a more general approach. If they are already strong in such things, there may not be any need.
Second, independent of the strength of the student background, use a lot of metaphor in introducing new concepts rather than being pedantic about the details of programming. Use "real life" examples of the concepts so that students "get an idea" first about some important topic. But, always be aware that metaphors have limits and they can give the wrong idea about things. So, be ready to dispel those misconceptions.
An example is "search for the reddest apple". This might be useful as a metaphor, unless you can see all of the apples at once and use powerful visual cues that don't have an analog in computing, where things need to be looked at one or two at a time.
