Author Topic: [Solved] The Toothfairy Problem  (Read 7029 times)

0 Members and 1 Guest are viewing this topic.

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
[Solved] The Toothfairy Problem
« on: October 23, 2006, 08:18:47 pm »
Show that 7^n - 1 is divisible by 6 for any positive integer n.

I'll post the solution on Wednesday.
« Last Edit: November 22, 2006, 03:10:36 pm by Ender »

Offline Rule

  • x86
  • Hero Member
  • *****
  • Posts: 1588
    • View Profile
Re: The Toothfairy Problem
« Reply #1 on: October 23, 2006, 09:47:43 pm »
Simple induction...  is this a homework assignment question?
« Last Edit: October 23, 2006, 09:49:40 pm by Rule »

Offline Sidoh

  • Moderator
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: The Toothfairy Problem
« Reply #2 on: October 24, 2006, 12:24:43 am »

Offline Rule

  • x86
  • Hero Member
  • *****
  • Posts: 1588
    • View Profile
Re: The Toothfairy Problem
« Reply #3 on: October 24, 2006, 04:58:55 pm »

You need to specify that you are assuming 7k-1 is divisible by 6 for some k>=1, then you have shown the formula holds for all n>=1. 

A picky detail, but one that is notable in rigorous math courses.


Offline rabbit

  • x86
  • Hero Member
  • *****
  • Posts: 8092
  • I speak for the entire clan (except Joe)
    • View Profile
Re: The Toothfairy Problem
« Reply #4 on: October 24, 2006, 05:06:10 pm »




Done.

Offline Sidoh

  • Moderator
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: The Toothfairy Problem
« Reply #5 on: October 24, 2006, 05:30:35 pm »
You need to specify that you are assuming 7k-1 is divisible by 6 for some k>=1, then you have shown the formula holds for all n>=1. 

A picky detail, but one that is notable in rigorous math courses.

Oops, yeah.  I should have said "Assume 7k-1 is divisible by 6 for some arbitrary integer greater than one, k," right?

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
Re: The Toothfairy Problem
« Reply #6 on: October 29, 2006, 09:15:49 pm »
Another way to do this, which does not require knowledge of modular arithmetic or number theory, is using the polynomial combinatorics whatever theorem:




« Last Edit: October 29, 2006, 09:19:02 pm by Ender »

Offline rabbit

  • x86
  • Hero Member
  • *****
  • Posts: 8092
  • I speak for the entire clan (except Joe)
    • View Profile
Re: The Toothfairy Problem
« Reply #7 on: October 29, 2006, 09:42:23 pm »
While that may not require knowledge of modular arithmetic and number theory, it does require either (A) set theory (I think) or (B) basic discrete concepts.

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
Re: The Toothfairy Problem
« Reply #8 on: October 31, 2006, 08:29:45 pm »
2 + 2 requires knowledge of set theory =p

but yeah it requires knowledge of basic combinatorics

Offline rabbit

  • x86
  • Hero Member
  • *****
  • Posts: 8092
  • I speak for the entire clan (except Joe)
    • View Profile
Re: The Toothfairy Problem
« Reply #9 on: November 01, 2006, 04:34:03 pm »
Which is Discrete, vis a vis same level as NT :P

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
Re: The Toothfairy Problem
« Reply #10 on: November 01, 2006, 07:36:26 pm »
Discrete math is much more common to high school math curricula* than number theory is, but yeah, there's no restriction to what math you can use in these problems.

* Grammar Policed on behalf of Sidoh's (pedantic) request
« Last Edit: November 01, 2006, 08:16:55 pm by Ender »

Offline Sidoh

  • Moderator
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: The Toothfairy Problem
« Reply #11 on: November 01, 2006, 07:48:19 pm »

Offline rabbit

  • x86
  • Hero Member
  • *****
  • Posts: 8092
  • I speak for the entire clan (except Joe)
    • View Profile
Re: The Toothfairy Problem
« Reply #12 on: November 01, 2006, 08:55:53 pm »
Discrete math is much more common to high school math curricula* than number theory is, but yeah, there's no restriction to what math you can use in these problems.

* Grammar Policed on behalf of Sidoh's (pedantic) request
Hmmm....that means I can use my made up math!

Offline Sidoh

  • Moderator
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: The Toothfairy Problem
« Reply #13 on: November 01, 2006, 09:23:04 pm »
* Grammar Policed on behalf of Sidoh's (pedantic) request

If it's truely pedantic, why did you go through the effort of fixing it?
« Last Edit: November 01, 2006, 09:24:38 pm by Sidoh »

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
Re: The Toothfairy Problem
« Reply #14 on: November 01, 2006, 09:40:42 pm »
I just wanted to use the word pedantic because I rarely get to use it and it's really fun to say.