Why not just publish some Signed text message here, anyone can get the public key from it. And the first user to solve it can redeem without worrying.
if you still wan to send the TX, please use 1 sat/vB for that TX get stuck on mempool fees.
The challenge involves correctly extracting pubkey from the raw TX, otherwise it's a no brainer.
What is a good way to set sat/vB such that it's both not stuck but also not urgent, e.g. mined in the block after next one? The challenge is not about "let's see if a 80 bit key can be cracked in less than 6 hours", we already have an answer to that.