C*****x
发帖数: 109 | 1 show that for any N>=1,there exists an integer with n digits from {1,2} that
is divisible by 2^n.For example,for n=4,2112 is a four-digit number with
digits from {1,2} that is divisible by 2^4.
谢谢！ | c******r
发帖数: 300 | 2 First, there are 2^n such numbers, now it's sufficient to show that none of
them have the same remainder when divided by 2^n, i.e., the difference
between any two of them is not divislbe by 2^n, however, this is apparent
since otherwise the difference must contain n 0s (to prove this, consider
the last digit of the difference, it must be zero if n>=1, and then consider
the second last digit, which must be zero if n>=2, etc), which leads to a
contradiction.
that
【在 C*****x 的大作中提到】
: show that for any N>=1,there exists an integer with n digits from {1,2} that
: is divisible by 2^n.For example,for n=4,2112 is a four-digit number with
: digits from {1,2} that is divisible by 2^4.
: 谢谢！
| C*****x
发帖数: 109 | | M********t
发帖数: 163 | 4 This point is very smart but I dont quite agree this proof,
especially this part" the difference
between any two of them is not divislbe by 2^n, however, this is apparent
since otherwise the difference must contain n 0s (to prove this, consider
the last digit of the difference, it must be zero if n>=1, and then consider
the second last digit, which must be zero if n>=2, etc)"
How is it "must be zeor" ? How about some 3-digit-number minus 3-digit-
number equal to 8? In other words you assume the number satisfies this
condition is uniqueHow to prove it for any N?
Actually this number is unique and we can prove it by induction.
Firstly, trivial for n=1. and unique.
FACT:
1 If we already have this number K for "n", then K/2^(n+1) is either
divisible or with a remainder 2^n, since 2K is divisible by 2^(n+1).
2 We claim 20....0 (with n zeros) is divisible by 2^(n+1), and 10....0 (with
n zeros) divided by 2^(n+1) with a remainder 2^n.
Combine 2 facts, if K/2^(n+1) is either divisible we choose 10....0 + K.
Otherwise choose 20....0 + K. And unique.
of
consider
【在 c******r 的大作中提到】
: First, there are 2^n such numbers, now it's sufficient to show that none of
: them have the same remainder when divided by 2^n, i.e., the difference
: between any two of them is not divislbe by 2^n, however, this is apparent
: since otherwise the difference must contain n 0s (to prove this, consider
: the last digit of the difference, it must be zero if n>=1, and then consider
: the second last digit, which must be zero if n>=2, etc), which leads to a
: contradiction.
:
: that
| c******r
发帖数: 300 | 5 I think I didn't make the argument quite clear. Since the number consists of
only 1 or 2, the last digit of the difference can only be 0,1 or 9. So I
don't think you can get an 8 as the difference. Correct me if I made a
mistake here, thanks.
consider
【在 M********t 的大作中提到】
: This point is very smart but I dont quite agree this proof,
: especially this part" the difference
: between any two of them is not divislbe by 2^n, however, this is apparent
: since otherwise the difference must contain n 0s (to prove this, consider
: the last digit of the difference, it must be zero if n>=1, and then consider
: the second last digit, which must be zero if n>=2, etc)"
: How is it "must be zeor" ? How about some 3-digit-number minus 3-digit-
: number equal to 8? In other words you assume the number satisfies this
: condition is uniqueHow to prove it for any N?
: Actually this number is unique and we can prove it by induction.
| n****e
发帖数: 629 | 6
that
归纳法，假设n成立，然后利用10^n mod 2^n+1=2^n 可知，n+1下第一位取1 or 2 必有
一个可以成立
【在 C*****x 的大作中提到】
: show that for any N>=1,there exists an integer with n digits from {1,2} that
: is divisible by 2^n.For example,for n=4,2112 is a four-digit number with
: digits from {1,2} that is divisible by 2^4.
: 谢谢！
| n****e
发帖数: 629 | 7 好像这样还能证明这个数唯一
【在 n****e 的大作中提到】
:
: that
: 归纳法，假设n成立，然后利用10^n mod 2^n+1=2^n 可知，n+1下第一位取1 or 2 必有
: 一个可以成立
| M********t
发帖数: 163 | 8 yeah right, but how about you get a 32?
I think you cant just say you cant get a 32.
of
【在 c******r 的大作中提到】
: I think I didn't make the argument quite clear. Since the number consists of
: only 1 or 2, the last digit of the difference can only be 0,1 or 9. So I
: don't think you can get an 8 as the difference. Correct me if I made a
: mistake here, thanks.
:
: consider
| M********t
发帖数: 163 | 9 恩，我就是这样证的。
【在 n****e 的大作中提到】
: 好像这样还能证明这个数唯一
| M********t
发帖数: 163 | 10 Let's consider this situation. n=5, Is it possible that 5 digit number
MINUS 5 digit number = 32? These two numbers only have 1 or 2, but how can
you prove its not possible to get 32 or even 512? I did not say it is not
true, but how can you verify this for any large number N? I just feel like
it is not a strict argument, please let me know if I misunderstand. Thanks.
of
【在 c******r 的大作中提到】
: I think I didn't make the argument quite clear. Since the number consists of
: only 1 or 2, the last digit of the difference can only be 0,1 or 9. So I
: don't think you can get an 8 as the difference. Correct me if I made a
: mistake here, thanks.
:
: consider
| c*m
发帖数: 1114 | 11 详细描述下Chop的证明。
对于n=5,假设差值为abcde.
假设abcde能被2^5整除，那么因为差值的最后一位只能是0,1,9,要被2^1整除，只能为e
=0 (2-2, 或者1-1).
现在考虑差值的最后第二位，因为abc00含2^2的因子，所以自动被2^2整除，因为前面e
是有2-2或者1-1得来的，所以d只能同样是0,1,9.同时要想abcd0被2^2整除，d只能是为
0,同时也是由2-2或者1-1得来的。
依次类推，a=b=c=d=e=0,从而证明两个不同的只由1或者2组成的5位数，不可能差值是2
^5的倍数。
【在 M********t 的大作中提到】
: Let's consider this situation. n=5, Is it possible that 5 digit number
: MINUS 5 digit number = 32? These two numbers only have 1 or 2, but how can
: you prove its not possible to get 32 or even 512? I did not say it is not
: true, but how can you verify this for any large number N? I just feel like
: it is not a strict argument, please let me know if I misunderstand. Thanks.
:
: of
| c******r
发帖数: 300 | 12 Thanks for filling in for me, I was too busy to come here and didn't realize
there was a discussion regarding the proof I had before.
为e
面e
是2
【在 c*m 的大作中提到】
: 详细描述下Chop的证明。
: 对于n=5,假设差值为abcde.
: 假设abcde能被2^5整除，那么因为差值的最后一位只能是0,1,9,要被2^1整除，只能为e
: =0 (2-2, 或者1-1).
: 现在考虑差值的最后第二位，因为abc00含2^2的因子，所以自动被2^2整除，因为前面e
: 是有2-2或者1-1得来的，所以d只能同样是0,1,9.同时要想abcd0被2^2整除，d只能是为
: 0,同时也是由2-2或者1-1得来的。
: 依次类推，a=b=c=d=e=0,从而证明两个不同的只由1或者2组成的5位数，不可能差值是2
: ^5的倍数。
| c******r
发帖数: 300 | 13 Please refer to cem's post, sorry I didn't spell out the necessary details
in the old post.
【在 M********t 的大作中提到】
: Let's consider this situation. n=5, Is it possible that 5 digit number
: MINUS 5 digit number = 32? These two numbers only have 1 or 2, but how can
: you prove its not possible to get 32 or even 512? I did not say it is not
: true, but how can you verify this for any large number N? I just feel like
: it is not a strict argument, please let me know if I misunderstand. Thanks.
:
: of
|
|
