Ubuntu has done this for many years:

    $ gem install dummystuff
    The program 'gem' can be found in the following packages:
     * rubygems1.8
     * rubygems1.9.1
    Ask your administrator to install one of them

It's occasionally useful.