Suggest a change

These fields are all optional and need only
be supplied if you would like a direct reply.

Subject
Your email address
Your real name

You must answer this!

If you don't, my spam filtering will
ensure that I never see your email.

What's 8 plus five (in digits only)?

Please make your changes here and then
Editing tips and layout rules.

File: TheLinearFrog

''' <link rel="alternate" type="application/rss+xml"
'''       href="/rss.xml" title="RSS Feed">

********> width="25%"
|>>
''' <a title="Subscribe to my feed"
'''    rel="alternate"
'''    href="https://www.solipsys.co.uk/rss.xml">
'''    <img style="border-width: 0px;"
'''         src="https://www.feedburner.com/fb/images/pub/feed-icon32x32.png"
'''         align="middle"
'''         alt="" />Subscribe!</a>
_
''' <a href="https://twitter.com/ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png"
'''      title="By: TwitterButtons.net"
'''      width="212" height="69"
'''      alt="@ColinTheMathmo"
'''     /></a>
<<|
----
My latest posts can be
found here:
  * ColinsBlog
----
Previous blog posts:
  * SeventyVersusOneHundredRevisited
  * HowTheFarragoWorks
  * SeventyVersusOneHundred
  * PowersOfTwoInLexOrder
  * EmergingEExpanded
  * RageInducingSystemImplementation
  * TheBookIsNotAlwaysRight
  * EmergingE
  * ImpossibleToTranslate
  * WaitingInVain
  * NonRepeatingDecimals
  * RationalRepeats
  * WhyIsItLovely
  * CompilingCryptoConnections
  * ExploringConnectionsBetweenCryptoSystems
  * ElwynBerlekampHasLeftUs
  * RootCauseAnalysisAndThePhotocopierQuestion
  * TheUpDownTides
  * TheForeAftTide
  * TheSidewaysTide
  * WrappingUpWrappingUpTheEarth
  * TheOtherWrappingTheEarthProblem
  * WrappingTheEarth
  * TheRingOfSteel
  * RoundingUpTheRopes
  * OtherOtherOtherRopeAroundTheEarth
  * RopeAroundTheEarthRefined
  * TheOtherRopeAroundTheEarth
  * ElementaryEstimates
  * LatitudeCorrection
  * JustGiveMeTheAnswer
  * MoreMusingOnPollardRho
  * IdleThoughtsAboutPollardRho
  * WhenOptimisingCodeMeasure
  * ADogCalledMixture
  * AnotherPayPalScam
  * WhyTopPostingHasWon
  * UnexpectedInteractionOfFeatures
  * ArchimedesHatBoxTheorem
  * ConsideringASphere
  * ToLinkOrNotToLink
  * GenericAdviceForWritingAThesis
  * JustTeachMyChildTheMaths
  * NotASpectatorSport
  * LeftTruncatablePrime
  * TheDoctorAndTheLawyer
  * FourPointsTwoDistancesProof
  * MeetingRonGraham
  * NapkinRingVersusSphericalCap
  * TheFourPointsPuzzle
  * RadiusOfTheEarthPartTwo
  * GrepTimingAnomaly
  * TheRadiusOfTheEarth
  * ThisWorksToCureMyHiccoughs
  * PerhapsWeSavedOne
  * ThinkingAboutMastodon
  * DisappearingTrainsOnVirgin
  * TheIndependenceGame
  * OneOfMyFavouritePuzzles
  * ThinkingAboutRecursion
  * MemorisingTheTube
  * SpikeySpheres
  * SurprisinglyQuick
  * AnUnexpectedFraction
  * YouHaveToAdmireTheirOptimism
  * RepresentativesMatter
  * PythagorasByIncircle
  * APuzzleAboutPuzzles
  * HowNotToDoTwitter
  * Calculating52FactorialByHand
  * SmallThingsMightNotBeSoSmall
  * NotIfYouHurry
  * FactoringViaGraphThreeColouring
  * AnotherProofOfTheDoodleTheorem
  * WhenObviousIsNotObvious
  * GraphThreeColouring
  * TheDoodleTheorem
  * BeCarefulWhatYouSay
  * TheMutilatedChessboardRevisited
  * AMirrorCopied
  * TheOtherOtherRopeAroundTheEarth
  * PhotocopyAMirror
  * ThePointOfTheBanachTarskiTheorem
  * SieveOfEratosthenesInPython
  * FastPerrinTest
  * RussianPeasantMultiplication
  * FindingPerrinPseudoPrimes_Part2
  * FindingPerrinPseudoPrimes_Part1
  * TheUnwiseUpdate
  * MilesPerGallon
  * TrackingAnItemOnHackerNews
  * HackerNewsUserAges
  * PokingTheDustyCorners
  * ThereIsNoTimeForThis
  * PublicallySharingLinks
  * LearningTimesTables
  * GracefulDegradation
  * DiagrammingMathsTopics
  * OnTheRack
  * SquareRootByLongDivision
  * BeyondTheBoundary
  * FillInTheGaps
  * SoftwareChecklist
  * NASASpaceCrews
  * TheBirthdayParadox
  * TheTrapeziumConundrum
  * RevisitingTheAnt
  * TheAntAndTheRubberBand
  * IrrationalsExist
  * MultipleChoiceProbabilityPuzzle
  * RandomEratosthenes
  * WrappingUpSquareDissection
  * DissectingASquarePart2
  * DissectingACircle
  * DissectingASquare
  * AnOddityInTennis
  * DecisionTreeForTennis
  * DecisionTreesInGames
  * AMatterOfConvention
  * DoYouNourishOrTarnish
  * BinarySearchReconsidered
  * TwoEqualsFour
  * TheLostPropertyOffice
  * TheForgivingUserInterface
  * SettingUpRSS
  * WithdrawingFromHackerNews
----
Additionally, some earlier writings:
  * RandomWritings.
  * ColinsBlog2010
  * ColinsBlog2009
  * ColinsBlog2008
  * ColinsBlog2007
  * ColinsBlogBefore2007
********
[[[> This page has been _ TaggedAsMaths and _ TaggedAsPuzzles ]]]
!! The Linear Frog

I was given a problem recently, and I was *really* pleased to get the
solution.  I wonder if you can (a) solve it, and (b) tell me where it
comes from.  I've not been able to track it down at all.

[[[>50 I'm still gestating the post about
Puzzle World vs Crypto World.  Not long now.

I hope. ]]]
So here it is.  I'm going to present it in two forms, to account for
the difference between Puzzle World and Crypto World.

!! The "Puzzle World" version ...

There's a set of lilypads stretching off beyond where the eye can see,
and we number them with the non-negative integers.  So we label them,
starting with 0.

There's a frog who, one day, for no obvious reason, decides to hop on
the pads, starting somewhere random, and then hopping the same distance
each time, off into the distance.  No, I have no idea why, but it seems
that it just wants to keep going.

But its plans were overheard by an unnamed predator.  Our predator is
very, *very* short-sighted, and when close to one lilypad is unable to
see any others, but it's lightning fast.  Sort of.  So it decides to
visit lilypads, one at a time, in an attempt to catch the frog. There's
no limit to how far the predator can travel between lilypads, but it
needs to spend a unit of time at each one to detect whether or not the
frog is there.

So for every time step the predator moves to a lilypad, and the frog
jumps to the next in their sequence.

The question is:

* Can the predator catch the frog?

!! The "Crypto world" version

So here is the formulation in more precise and strictly mathematical
terms.

* Can you find a sequence $s(t)$ such that
    for every arithmetic sequence $a+dt$ there
    is a $t$ with $s(t)=a+dt$?

We are, of course, working in integers, and assume that $a$ and $d$
are non-negative.

!! Extension

Once you solve the problem for the frog moving in a linear pattern,
what if it moves in a Cubic?  Or Quintic?  Or Exponential?  What if
$a$ and $d$ are allowed to be any integer (breaking the original idea
of the lilypads going off in one direction).

!! Problem source ...

So over to you.  Firstly, can such a sequence be found?  If so, what
is it, and if not, can you prove it?

Secondly, do you know a source for the problem?  If so, let me know.

Enjoy!
----

|>>
| |>> <<<< Prev <<<< ---- SeventyVersusOneHundredRevisited <<| | : | |>> >>>> Next >>>> ---- IntroducingTimeComplexity ... <<| |
----
********>
''' <a href="https://mathstodon.xyz/@ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/images/Mastodon_Mascot.png"
'''      width="256" height="280"
'''      alt="https://mathstodon.xyz/@ColinTheMathmo"
'''     /></a>
********
''' <a href="https://mathstodon.xyz/@ColinTheMathmo/">You can follow me on Mathstodon.</a>
_ _ _ _
[[[>
''' <a href="https://twitter.com/ColinTheMathmo">Of course, you can also<br>follow me on twitter:</a>

''' <a href="https://twitter.com/ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png"
'''      title="By: TwitterButtons.net"
'''      width="212" height="69"
'''      alt="@ColinTheMathmo"
'''     /></a>
''' <img src="/cgi-bin/CountHits.py?TheLinearFrog" alt="" />
]]]
********<

----

!! Send us a comment ...

''' <form action="https://www.solipsys.co.uk/cgi-bin/FormMail.pl" method=post>
''' <input type=hidden name="recipient"               value="colinsblogcomment@solipsys.co.uk" >
''' <input type=hidden name="subject"                 value="Blog comment : TheLinearFrog"         >
''' <input type=hidden name="redirect"                value="https://www.solipsys.co.uk/new/ThankYouForYourComment.html" >
''' <input type=hidden name="missing_fields_redirect" value="https://www.solipsys.co.uk/RequestError.html">
''' <input type=hidden name="env_report"              value="REMOTE_HOST, REMOTE_ADDR, HTTP_USER_AGENT"  >
''' <input type=hidden name="print_blank_fields"      value="1"                                          >

********> width="47%"
You can send us a message here. It doesn't get published,
it just sends us an email, and is an easy way to ask any
questions, or make any comments, without having to send a
separate email. So just fill in the boxes and then
''' <font size="+4"><INPUT TYPE="submit" VALUE="CLICK HERE TO SEND"></font>
******** width="53%"
********<

''' <table cellpadding="5">
'''   <tr>
'''     <td valign="top">Your name </td> <td valign="top">:</td>
'''     <td> <input type=text name="realname" size="48"> </td>
'''   <tr>
'''     <td valign="top">Email </td> <td valign="top">:</td>
'''     <td> <input type=text name="email" size="48"> </td>
'''     </tr>
'''   <tr>
'''     <td valign="top">Message </td> <td valign="top">:</td>
'''     <td> <TEXTAREA NAME="Message" ROWS=10 COLS=64></TEXTAREA> </td>
'''     </tr>
'''   </table>

''' <center>
'''   <font size="+4">
'''     <INPUT TYPE="submit" VALUE="CLICK HERE TO SEND">
'''     </font>
'''   </center>
''' </form>

********<